UC Davis Mathematics

Mathematics Colloquia and Seminars

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.