Kernels for feedback arc set in tournaments (Q657916): Difference between revisions

From the abstract: ``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^{{\prime}}\) 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.''