Blocking Dominating Sets for H-Free Graphs via Edge Contractions
- Galby, Esther University of Fribourg, Switzerland
- Lima, Paloma T. University of Bergen, Norway
- Ries, Bernard University of Fribourg, Switzerland
-
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 et du management
- Department
- Département d'informatique
- Language
-
- English
- Classification
- Computer science and technology
- License
- License undefined
- Identifiers
-
- RERO DOC 327934
- DOI 10.4230/LIPIcs.ISAAC.2019.21
- Persistent URL
- https://folia.unifr.ch/unifr/documents/308270
Statistics
Document views: 34
File downloads:
- lipics-isaac-2019-21.pdf: 74