Groshaus, Marina; Hell, Pavol; Klein, Sulamita; Nogueira, Loana Tito; Protti, Fabio Cycle transversals in bounded degree graphs. (English) Zbl 1283.68155 Discrete Math. Theor. Comput. Sci. 13, No. 1, 45-66 (2011). Summary: 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\geq 3\). For graphs of maximum degree at most three, we prove that this problem is polynomial-time solvable when \(k\leq 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\geq 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. Cited in 1 Document MSC: 68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) 68W25 Approximation algorithms 05C85 Graph algorithms (graph-theoretic aspects) 05C38 Paths and cycles Keywords:approximation algorithms; cycle-transversals; transversals PDFBibTeX XMLCite \textit{M. Groshaus} et al., Discrete Math. Theor. Comput. Sci. 13, No. 1, 45--66 (2011; Zbl 1283.68155) Full Text: Link