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 a of V that maximizes the number of triples whose rearrangement (under a) follows a permutation in ¿. We prove that all ternary Permutation-CSPs parameterized above average have kernels with quadratic numbers of variables.
|Title of host publication||Algorithms - ESA 2010 (18th Annual European Symposium, Liverpool, UK, September 6-8, 2010. Proceedings, Part I)|
|Editors||M. Berg, de, U. Meyer|
|Place of Publication||Berlin|
|Publication status||Published - 2010|
|Name||Lecture Notes in Computer Science|