Return to Colloquia & Seminar listing
All Ternary Permutation Constraint Satisfaction Problems Parameterized Above Average Have Kernels with Quadratic Numbers of Variables
Algebra & Discrete Mathematics| Speaker: | Matthias Mnich, International Computer Science Institute |
| Location: | 1147 MSB |
| 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.