A 4k(2) Kernel for Feedback Vertex Set
We prove that given an undirected graph G on n vertices and an integer k, one can compute, in polynomial time in n, a graph G' with at most 4k(2) vertices and an integer k' such that G has a feedback vertex set of size at most k iff G' has a feedback vertex set of size at most k'. This result improves a previous O(k(11)) kernel of Burrage et al., and a more recent cubic kernel of Bodlaender. This problem was communicated by Fellows.
kernelization feedback vertex set algorithms matching fixed parameter tractability