A Quadratic Kernel for Feedback Vertex Set - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Communication Dans Un Congrès Année : 2009

A Quadratic Kernel for Feedback Vertex Set

Stéphan Thomassé

Résumé

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
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

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

Identifiants

  • HAL Id : lirmm-00394595 , version 1

Citer

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⟩
163 Consultations
320 Téléchargements

Partager

Gmail Facebook X LinkedIn More