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

Gutin, Gregory Z.; Iersel, Leo van; Mnich, Matthias; Yeo, Anders

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

Publikationstyp

Journal Article

Publikationsdatum

2012-01

Sprache

English

Author

TORE-URI

http://hdl.handle.net/11420/4570

Enthalten in

Journal of computer and system sciences

Volume

78

Start Page

151

End Page

163

Citation

Journal of Computer and System Sciences (2012)

Publisher DOI

10.1016/j.jcss.2011.01.004

Publisher

Elsevier

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.

DDC Class

004: Informatik

Options

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