Authors: Marina Groshaus ¹; Pavol Hell ^2,3; Sulamita Klein ⁴; Loana Tito Nogueira ⁵; Fábio Protti ⁵

• 1 Departamento de Computación [Buenos Aires]
• 2 Simon Fraser University
• 3 Simon Fraser University = Université Simon Fraser [SFU.ca]
• 4 Instituto de Matemática da Universidade Federal do Rio de Janeiro
• 5 Fluminense Federal University [Niterói]

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.