Conference paper (in proceedings)

Blocking Dominating Sets for H-Free Graphs via Edge Contractions

    2019
Published in:
  • 30th International Symposium on Algorithms and Computation (ISAAC) - Leibniz International Proceedings in Informatics / Pinyan Lu and Guochuan Zhang. - Schloss Dagstuhl – Leibniz-Zentrum für Informatik. - 2019, vol. 149, no. 21, p. 1-14
English In this paper, we consider the following problem: given a connected graph G, can we reduce the domination number of G by one by using only one edge contraction? We show that the problem is NP-hard when restricted to {P6, P4 + P2}-free graphs and that it is coNP-hard when restricted to subcubic claw-free graphs and 2P3-free graphs. As a consequence, we are able to establish a complexity dichotomy for the problem on H-free graphs when H is connected.
Faculty
Faculté des sciences économiques et sociales
Department
Département d'informatique
Language
  • English
Classification
Computer science
License
License undefined
Identifiers
Persistent URL
https://folia.unifr.ch/unifr/documents/308270
Statistics

Document views: 7 File downloads:
  • lipics-isaac-2019-21.pdf: 2