A 4 k 2 kernel for feedback vertex set
Stéphan Thomassé · ACM Transactions on Algorithms · 2010
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 4 k 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.