Skip to Main content Skip to Navigation
Conference papers

A Quadratic Kernel for Feedback Vertex Set

Stéphan Thomassé 1 
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
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 5k2 + 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(k11) kernel of Burrage et al. [6], and a more recent cubic kernel of Bodlaender [3]. This problem was communicated by Fellows in [5].
Document type :
Conference papers
Complete list of metadata

Cited literature [18 references]  Display  Hide  Download
Contributor : Stephan Thomasse Connect in order to contact the contributor
Submitted on : Tuesday, August 31, 2010 - 3:16:51 PM
Last modification on : Tuesday, September 6, 2022 - 4:55:59 PM
Long-term archiving on: : Wednesday, December 1, 2010 - 2:22:59 AM


Files produced by the author(s)


  • HAL Id : lirmm-00394595, version 1



Stéphan Thomassé. A Quadratic Kernel for Feedback Vertex Set. SODA'09: Symposium on Discrete Algorithms, New York, United States. pp.115-119. ⟨lirmm-00394595⟩



Record views


Files downloads