All Ternary Permutation Constraint Satisfaction Problems Parameterized Above Average Have Kernels with Quadratic Numbers of VariablesAlgebra & Discrete Mathematics
|Speaker:||Matthias Mnich, International Computer Science Institute|
|Start time:||Fri, Jan 21 2011, 2:10PM|
A ternary Permutation-CSP is specified by a subset Pi of the symmetric group S_3. 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 \alpha of V that maximizes the number of triples whose ordering (under \alpha) follows a permutation in Pi. We prove that all ternary Permutation-CSPs parameterized above average have kernels with quadratic numbers of variables.