Reducing the domination number of graphs via edge contractions and vertex deletions
Published in:
 Discrete Mathematics.  2021, vol. 344, no. 1, p. 112169
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 NPhard (resp. coNPhard). We further prove that for k = 1, the problem is W[1]hard parameterized by domination number plus the mimwidth of the input graph, and that it remains NPhard 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 coNPhard on subcubic clawfree graphs, subcubic planar graphs and on 2P3free graphs. On the positive side, we show that for any k ≥ 1, the problem is polynomialtime solvable on (P5 +pK1)free graphs for any p ≥ 0 and that it can be solved in FPTtime and XPtime when parameterized by treewidth and mimwidth, 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 Hfree graphs.

Faculty
 Faculté des sciences économiques et sociales et du management

Department
 Département d'informatique

Language


Classification

Computer science

License

License undefined

Identifiers


Persistent URL

https://folia.unifr.ch/unifr/documents/309004
Statistics
Document views: 20
File downloads:
 blockerdomination.pdf: 11