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

Publikationstyp
Conference Paper
Date Issued
2010-11-19
Sprache
English
Author(s)
Gutin, Gregory Z.  
Iersel, Leo van  
Mnich, Matthias  
Yeo, Anders  
TORE-URI
http://hdl.handle.net/11420/7625
First published in
Lecture notes in computer science  
Number in series
6346 LNCS
Issue
PART 1
Start Page
326
End Page
337
Citation
18th Annual European Symposium on Algorithms (ESA 2010)
Contribution to Conference
18th Annual European Symposium on Algorithms (ESA 2010)  
Publisher DOI
10.1007/978-3-642-15775-2_28
Scopus ID
2-s2.0-78249260335
Publisher
Springer
A 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.
DDC Class
004: Informatik