A quadratic kernel for feedback vertex set
Stéphan Thomassé · 2009
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 5k 2 +k 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. [6], and a more recent cubic kernel of Bodlaender [3]. This problem was communicated by Fellows in [5]. 1