All Ternary Permutation Constraint Satisfaction Problems Parameterized Above Average Have Kernels with Quadratic Numbers of Variables

Gregory Gutin, Leo van Iersel, Matthias Mnich +1

A ternary Permutation-CSP is specified by a subset $\Pi$ of the symmetric group ${\mathcal{S}}_3$. An instance of such a problem consists of a set of variables $V$ and a multiset of con…