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.