Linear-Time Kernelization for Feedback Vertex Set

In this paper, we give an algorithm that, given an undirected graph G of m edges and an integer k, computes a graph G\u27 and an integer k\u27 in O(k^4 m) time such that (1) the size of the graph G\u27 is O(k^2), (2) k\u27 leq k, and (3) G has a feedback vertex set of size at most k if and only if G\u27 has a feedback vertex set of size at most k\u27. This is the first linear-time polynomial-size kernel for Feedback Vertex Set. The size of our kernel is 2k^2+k vertices and 4k^2 edges, which is smaller than the previous best of 4k^2 vertices and 8k^2 edges. Thus, we improve the size and the running time simultaneously. We note that under the assumption of NP notsubseteq coNP/poly, Feedback Vertex Set does not admit an O(k^{2-epsilon})-size kernel for any epsilon>0. Our kernel exploits k-submodular relaxation, which is a recently developed technique for obtaining efficient FPT algorithms for various problems. The dual of k-submodular relaxation of Feedback Vertex Set can be seen as a half-integral variant of A-path packing, and to obtain the linear-time complexity, we give an efficient augmenting-path algorithm for this problem. We believe that this combinatorial algorithm is of independent interest. A solver based on the proposed method won first place in the 1st Parameterized Algorithms and Computational Experiments (PACE) challenge