A 4 k 2 kernel for feedback vertex set

Abstract

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² 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¹¹) kernel of Burrage et al., and a more recent cubic kernel of Bodlaender. This problem was communicated by Fellows.