Kernels for feedback arc set in tournaments
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 epsilon > 0, the kernelized instance has at most (2 + epsilon)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. (C) 2010 Elsevier Inc. All rights reserved.
kernelization feedback arc set tournaments parameterized algorithms graph algorithms