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].
Type de document :
Communication dans un congrès
SODA'09: Symposium on Discrete Algorithms, New York, United States. pp.115-119, 2009, 〈http://www.siam.org/meetings/da09/〉
Liste complète des métadonnées

Littérature citée [18 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00394595
Contributeur : Stephan Thomasse <>
Soumis le : mardi 31 août 2010 - 15:16:51
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13
Document(s) archivé(s) le : mercredi 1 décembre 2010 - 02:22:59

Fichier

kernelFVS.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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, 2009, 〈http://www.siam.org/meetings/da09/〉. 〈lirmm-00394595〉

Partager

Métriques

Consultations de la notice

162

Téléchargements de fichiers

112