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 {sc Feedback Arc Set} problem asks whether thegiven digraph has a set of $k$ arcs whose removal results in an acyclicdigraph. The {sc Feedback Arc Set} problem restricted to tournaments is knownas the {sc $k$-Feedback Arc Set in Tournaments ($k$-FAST)} problem. In thispaper we obtain a linear vertex kernel for FAST{}. That is, we give apolynomial time algorithm which given an input instance $T$ to FAST{} obtains an equivalent instance $T\u27$ 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 forFAST{}. Our kernelization algorithm solves the problem on a subclass of tournaments in polynomial time and uses a known polynomial time approximation scheme for FAST