A Quadratic Kernel for Feedback Vertex Set - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2009

A Quadratic Kernel for Feedback Vertex Set

Stéphan Thomassé

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].
Fichier principal
Vignette du fichier
kernelFVS.pdf (160.99 Ko) Télécharger le fichier
Origin Files produced by the author(s)
Loading...

Dates and versions

lirmm-00394595 , version 1 (31-08-2010)

Identifiers

  • HAL Id : lirmm-00394595 , version 1

Cite

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⟩
166 View
329 Download

Share

Gmail Mastodon Facebook X LinkedIn More