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

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00394595
Contributor : Stephan Thomasse <>
Submitted on : Tuesday, August 31, 2010 - 3:16:51 PM
Last modification on : Thursday, February 7, 2019 - 2:48:59 PM
Long-term archiving on: : Wednesday, December 1, 2010 - 2:22:59 AM

File

kernelFVS.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : lirmm-00394595, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

275

Files downloads

322