On the kernelization of ranking rr-CSPs: Linear vertex-kernels for generalizations of Feedback Arc Set and Betweenness in tournaments

An instance of a rankingrr-constraint satisfaction problem (ranking rr-CSP for short) consists of a ground set of vertices VV, an arity r⩾2r⩾2, a parameter k∈Nk∈N and a constraint system  cc, where cc is a function which maps rankings of rr-sized sets S⊆VS⊆V to {0,1}{0,1}. The objective is to decide if there exists a ranking σσ of the vertices satisfying all but at most kk constraints (i.e ∑S⊆V,|S|=rc(σ(S))⩽k∑S⊆V,|S|=rc(σ(S))⩽k). We mainly focus on dense instances, that is instances where the constraint system is defined for every  rr-sized subset S⊆VS⊆V. Famous dense ranking rr-CSPs include Feedback Arc Set and Betweenness in tournaments, two well-studied problems (Alon et al., 2009; Bessy et al., 2011; Karpinski and Schudy, 2010, 2011; Paul et al., 2011). We consider such problems from the kernelization viewpoint (Niedermeier, 2006). We prove that so-called prpr-simply characterized   ranking rr-CSPs admit linear vertex-kernels whenever they admit constant-factor approximation algorithms. This implies that rr-Dense Betweenness and rr-Dense Transitive Feedback Arc Set, two natural generalizations of the previously mentioned problems (Karpinski and Schudy, 2010, 2011), admit linear vertex-kernels. Moreover, we introduce another generalization of Feedback Arc Set in Tournaments, which does not fit the aforementioned framework. Based on techniques from Coppersmith (2006) we obtain a 5-approximation, and then provide a linear vertex-kernel for this problem as well.