Conflict Packing yields linear vertex-kernels for Rooted Triplet Inconsistency and other problems

Details Conflict Packing yields linear vertex-kernels for Rooted Triplet Inconsistency and other problems Conflict Packing yields linear vertex-kernels for Rooted Triplet Inconsistency and other problems

2011-01-24

arxiv.org/abs/1101.4491v1

Computer Science

Data Structures and Algorithms

Scientific paper

We develop a technique that we call Conflict Packing in the context of kernelization. We illustrate this technique on several well-studied problems: Feedback Arc Set in Tournaments, Dense Rooted Triplet Inconsistency and Betweenness in Tournaments. For the former, one is given a tournament T = (V,A) and seeks a set of at most k arcs whose reversal in T leads to an acyclic tournament. While a linear vertex-kernel is already known for this problem [6], using the Conflict Packing allows us to find a so-called safe partition, the central tool of the kernelization algorithm in [6], with simpler arguments. Regarding the Dense Rooted Triplet Inconsistency problem, one is given a set of vertices V and a dense collection R of rooted binary trees over three vertices of V and seeks a rooted tree over V containing all but at most k triplets from R. Using again the Conflict Packing, we prove that the Dense Rooted Triplet Inconsistency problem admits a linear vertex-kernel. This result improves the best known bound of O(k^2) vertices for this problem [19]. Finally, we use this technique to obtain a linear vertex-kernel for Betweenness in Tournaments, where one is given a set of vertices V and a dense collection R of betweenness triplets and seeks an ordering containing all but at most k triplets from R. To the best of our knowledge this result constitutes the rst polynomial kernel for the problem.

Affiliated with

Also associated with

No associations

Rating

Conflict Packing yields linear vertex-kernels for Rooted Triplet Inconsistency and other problems 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 Conflict Packing yields linear vertex-kernels for Rooted Triplet Inconsistency and other problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Conflict Packing yields linear vertex-kernels for Rooted Triplet Inconsistency and other problems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-636658