On the kernelization of ranking <i>r</i>-CSPs: Linear vertex-kernels for generalizations of FEEDBACK ARC SET and BETWEENNESS in tournaments

作     者：Perez, Anthony 

作者机构：Univ Orleans INSA Ctr Val Loire LIFO EA 4022 F-45067 Orleans France 

出 版 物：《DISCRETE APPLIED MATHEMATICS》 (离散应用数学)

年 卷 期：2015年第186卷第1期

页      面：214-225页

核心收录：

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

基　　金：AGAPE project [ANR-09-BLAN-0159] 

主　　题：Kernelization algorithms Parameterized complexity Ranking CSP Dense instances 

摘      要：An instance of a RANKING r-CONSTRAINT SATISFACTION PROBLEM (ranking r-CSP for short) consists of a ground set of vertices V, an arity r = 2, a parameter k is an element of N and a constraint system c, where c is a function which maps rankings of r-sized sets S subset of V to {0,1}. The objective is to decide if there exists a ranking a of the vertices satisfying all but at most k constraints (i.e Sigma(S subset of V, vertical bar S vertical bar=r) C(sigma(S)) = k). We mainly focus on dense instances, that is instances where the constraint system is defined for every r-sized subset S subset of V. Famous dense ranking r-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 p(r)-simply characterized ranking r-CSPs admit linear vertex-kernels whenever they admit constant-factor approximation algorithms. This implies that r-DENSE BETWEENNESS and r-DENSE TRANSITIVE FEEDBACK ARC SET, WO 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. (C) 2015 Elsevier B.V. All rights reserved.