### Cycle transversals in bounded degree graphs

*Marina Groshaus, Pavol Hell, Sulamita Klein, Loana Tito Nogueira, Fabio Protti*

#### 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 ≥3. For graphs of maximum degree at most three, we prove that this problem is polynomial-time solvable when k ≤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 ≥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.Full Text: PDF PostScript