A 4k2 kernel for feedback vertex set
S Thomassé - ACM Transactions on Algorithms (TALG), 2010 - dl.acm.org
ACM Transactions on Algorithms (TALG), 2010•dl.acm.org
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.
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.
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 4k2 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(k11) kernel of Burrage et al., and a more recent cubic kernel of Bodlaender. This problem was communicated by Fellows.