Abstract
A ternary permutation-csp is specified by a subset p of the symmetric group s3. 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 p. We prove that every ternary permutation-csp parameterized above average has a kernel with a quadratic number of variables.
Original language | English |
---|---|
Pages (from-to) | 151-163 |
Journal | Journal of Computer and System Sciences |
Volume | 78 |
Issue number | 1 |
DOIs | |
Publication status | Published - 2012 |
Externally published | Yes |