×

Cycle transversals in bounded degree graphs. (English) Zbl 1283.68155

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.

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
PDFBibTeX XMLCite
Full Text: Link