Reducing the domination number of graphs via edge contractions and vertex deletions

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

doi:10.1016/j.disc.2020.112169

Back

Journal article

Reducing the domination number of graphs via edge contractions and vertex deletions

Galby, Esther University of Fribourg, Switzerland
Lima, Paloma T. University of Bergen, Norway
Ries, Bernard University of Fribourg, Switzerland

2021

Published in:

Discrete Mathematics. - 2021, vol. 344, no. 1, p. 112169

Theoretical Computer Science

Discrete Mathematics and Combinatorics

English In this work, we study the following problem: given a connected graph G, can we reduce the domination number of G by at least one using k edge contractions, for some fixed integer k > 0? We show that for k = 1 (resp. k = 2), the problem is NP-hard (resp. coNP-hard). We further prove that for k = 1, the problem is W[1]-hard parameterized by domination number plus the mim-width of the input graph, and that it remains NP-hard when restricted to chordal {P6, P4 + P2}-free graphs, bipartite graphs and {C3, . . . , Cℓ}- free graphs for any ℓ ≥ 3. We also show that for k = 1, the problem is coNP-hard on subcubic claw-free graphs, subcubic planar graphs and on 2P3-free graphs. On the positive side, we show that for any k ≥ 1, the problem is polynomial-time solvable on (P5 +pK1)-free graphs for any p ≥ 0 and that it can be solved in FPT-time and XP-time when parameterized by treewidth and mim-width, respectively. Finally, we start the study of the problem of reducing the domination number of a graph via vertex deletions and edge additions and, in this case, present a complexity dichotomy on H-free graphs.

Faculty

Faculté des sciences économiques et sociales et du management

Department

Département d'informatique

Language