Conference paper (in proceedings)
Blocking Dominating Sets for H-Free Graphs via Edge Contractions
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
-
-
Classification
-
Computer science and technology
-
License
-
License undefined
-
Identifiers
-
-
Persistent URL
-
https://folia.unifr.ch/unifr/documents/308270
Statistics
Document views: 34
File downloads:
- lipics-isaac-2019-21.pdf: 74