All ternary permutation constraint satisfaction problems parameterized above average have kernels with quadratic numbers of variables

Gutin, Gregory Z.Gregory Z.GutinIersel, Leo vanLeo vanIerselMnich, MatthiasMatthiasMnichYeo, AndersAndersYeo2020-10-212020-10-212010-11-1918th Annual European Symposium on Algorithms (ESA 2010)http://hdl.handle.net/11420/7625A ternary Permutation-CSP is specified by a subset Π 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 α of V that maximizes the number of triples whose rearrangement (under α) follows a permutation in Π. We prove that all ternary Permutation-CSPs parameterized above average have kernels with quadratic numbers of variables.enInformatikAll ternary permutation constraint satisfaction problems parameterized above average have kernels with quadratic numbers of variablesConference Paper10.1007/978-3-642-15775-2_28Other