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 Ck-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
C3-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