Every ternary permutation constraint satisfaction problems parameterized above average has a kernel with a quadratic number of variables

A ternary Permutation-CSP is specified by a subset ¿ of the symmetric group . 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 a of V that maximizes the number of triples whose rearrangement (under a) follows a permutation in ¿. We prove that every ternary Permutation-CSP parameterized above average has a kernel with a quadratic number of variables.