A Quadratic Kernel for Feedback Vertex Set - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
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

Citer

Stéphan Thomassé. A Quadratic Kernel for Feedback Vertex Set. SODA 2009 - 20th ACM/SIAM Symposium on Discrete Algorithms, Jan 2009, New York, United States. pp.115-119, ⟨10.1137/1.9781611973068.13⟩. ⟨lirmm-00394595⟩
183 Consultations
356 Téléchargements

Altmetric

Partager

More