Blocking Dominating Sets for H-Free Graphs via Edge Contractions

Galby, Esther; Lima, Paloma T.; Ries, Bernard

doi:10.4230/LIPIcs.ISAAC.2019.21

Back

Conference paper (in proceedings)

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