Skip to Main content Skip to Navigation
Journal articles

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.
Document type :
Journal articles
Complete list of metadata

Cited literature [13 references]  Display  Hide  Download

https://hal.inria.fr/hal-00990477
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Submitted on : Tuesday, May 13, 2014 - 3:39:01 PM
Last modification on : Monday, October 19, 2020 - 2:34:03 PM
Long-term archiving on: : Monday, April 10, 2017 - 10:26:07 PM

File

1534-5918-2-PB.pdf
Files produced by the author(s)

Identifiers

  • 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⟩

Share

Metrics

Record views

262

Files downloads

1743