کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
418931 681727 2015 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On the kernelization of ranking rr-CSPs: Linear vertex-kernels for generalizations of Feedback Arc Set and Betweenness in tournaments
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 186, 11 May 2015, Pages 214–225
نویسندگان
,