Kernels for Feedback Arc Set In Tournaments

Details Kernels for Feedback Arc Set In Tournaments Kernels for Feedback Arc Set In Tournaments

2009-07-13

arxiv.org/abs/0907.2165v2

Computer Science

Data Structures and Algorithms

Scientific paper

A tournament T=(V,A) is a directed graph in which there is exactly one arc between every pair of distinct vertices. Given a digraph on n vertices and an integer parameter k, the Feedback Arc Set problem asks whether the given digraph has a set of k arcs whose removal results in an acyclic digraph. The Feedback Arc Set problem restricted to tournaments is known as the k-Feedback Arc Set in Tournaments (k-FAST) problem. In this paper we obtain a linear vertex kernel for k-FAST. That is, we give a polynomial time algorithm which given an input instance T to k-FAST obtains an equivalent instance T' on O(k) vertices. In fact, given any fixed e>0, the kernelized instance has at most (2+e)k vertices. Our result improves the previous known bound of O(k^2) on the kernel size for k-FAST. Our kernelization algorithm solves the problem on a subclass of tournaments in polynomial time and uses a known polynomial time approximation scheme for k-FAST.

Affiliated with

Also associated with

No associations

Rating

Kernels for Feedback Arc Set 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 Kernels for Feedback Arc Set In Tournaments, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Kernels for Feedback Arc Set In Tournaments will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-100896