2010/03/01 by Stéphan Thomassé · 201 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Limits and Structures in Graph Theory #Combinatorics #Feedback vertex set #Vertex (graph theory) #Polynomial kernel #Mathematics #Graph #Kernelization #Integer (computer science) #Kernel (algebra) #Feedback arc set #Neighbourhood (mathematics) #Discrete mathematics #Kernel method #Computer science #Line graph #Voltage graph
paper · doi:10.1145/1721837.1721848
published in ACM Transactions on Algorithms 6(2), 1-8 (Association for Computing Machinery)
openalex publication_date 2010/03/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/22
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.