Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables

Journal article (2012)

Authors

L.J.J. van Iersel University of Canterbury
Affiliation
External organisation
More Info
expand_more

Published Date

2012

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Affiliation

External organisation

Abstract

A ternary Permutation-CSP is specified by a subset Π of the symmetric group . An instance of such a problem consists of a set of variables V and a multiset of constraints, which are ordered triples of distinct variables of V. The objective is to find a linear ordering α of V that maximizes the number of triples whose rearrangement (under α) follows a permutation in Π. We prove that every ternary Permutation-CSP parameterized above average has a kernel with a quadratic number of variables.