Marina Groshaus ; Pavol Hell ; Sulamita Klein ; Loana Tito Nogueira ; Fábio Protti - Cycle transversals in bounded degree graphs

dmtcs:533 - Discrete Mathematics & Theoretical Computer Science, March 4, 2011, Vol. 13 no. 1 - https://doi.org/10.46298/dmtcs.533
Cycle transversals in bounded degree graphs

Authors: Marina Groshaus 1; Pavol Hell 2; Sulamita Klein 3; Loana Tito Nogueira 4; Fábio Protti 4

  • 1 Departamento de Computación [Buenos Aires]
  • 2 Simon Fraser University
  • 3 Instituto de Matemática da Universidade Federal do Rio de Janeiro
  • 4 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.


Volume: Vol. 13 no. 1
Section: Graph and Algorithms
Published on: March 4, 2011
Accepted on: June 9, 2015
Submitted on: July 12, 2010
Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

Linked publications - datasets - softwares

Source : ScholeXplorer IsRelatedTo DOI 10.1145/800133.804355
  • 10.1145/800133.804355
Node-and edge-deletion NP-complete problems

Consultation statistics

This page has been seen 299 times.
This article's PDF has been downloaded 205 times.