Cycle transversals in bounded degree graphs

Abstract : In this work we investigate the algorithmic complexity of computing a minimum C(k)-transversal, i.e., a subset of vertices that intersects all the chordless cycles with k vertices of the input graph, for a fixed k \textgreater= 3. For graphs of maximum degree at most three, we prove that this problem is polynomial-time solvable when k \textless= 4, and NP-hard otherwise. For graphs of maximum degree at most four, we prove that this problem is NP-hard for any fixed k \textgreater= 3. We also discuss polynomial-time approximation algorithms for computing C(3)-transversals in graphs of maximum degree at most four, based on a new decomposition theorem for such graphs that leads to useful reduction rules.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2011, Vol. 13 no. 1 (1), pp.45--66
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00990477
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : mardi 13 mai 2014 - 15:39:01
Dernière modification le : mercredi 22 août 2018 - 12:24:01
Document(s) archivé(s) le : lundi 10 avril 2017 - 22:26:07

Fichier

1534-5918-2-PB.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00990477, version 1

Collections

Citation

Marina Groshaus, Pavol Hell, Sulamita Klein, Loana Tito Nogueira, Fábio Protti. Cycle transversals in bounded degree graphs. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2011, Vol. 13 no. 1 (1), pp.45--66. 〈hal-00990477〉

Partager

Métriques

Consultations de la notice

129

Téléchargements de fichiers

311