On the kernelization of ranking r-CSP in tournaments

Details On the kernelization of ranking r-CSP in tournaments On the kernelization of ranking r-CSP in tournaments

2012-03-16

arxiv.org/abs/1203.3727v2

Computer Science

Discrete Mathematics

Scientific paper

A Ranking r-Constraint Satisfaction Problem (ranking r-CSP) consists of a ground set of vertices V, an arity r > 2, a parameter k and a constraint system c, where c is a function which maps rankings of r-sized subsets of V to {0,1}. The objective is to decide if there exists a ranking of the vertices satisfying all but at most k constraints. Famous ranking r-CSP include the Feedback Arc Set in Tournaments and Betweenness in Tournaments problems. We consider these problems from the kernelization viewpoint. We prove that so-called l_r-simply characterized ranking r-CSP admit linear vertex-kernels whenever they admit constant-factor approximation algorithms. This implies that r-Betweenness in Tournaments and r-Transitive Feedback Arc Set In Tournaments admit linear vertex-kernels. Finally, we consider another generalization of Feedback Arc Set in Tournaments, which does not fit the aforementioned framework. We obtain a constant-factor approximation and a linear vertex-kernel for this problem.

Affiliated with

Also associated with

No associations

Rating

On the kernelization of ranking r-CSP in tournaments does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the kernelization of ranking r-CSP in tournaments, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the kernelization of ranking r-CSP in tournaments will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-352019