Galby, Esther Lima, Paloma T. Ries, Bernard 2021 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. application/pdf https://folia.unifr.ch/global/documents/309004 https://folia.unifr.ch/documents/309004/files/blocker-domination.pdf eng info:eu-repo/semantics/altIdentifier/doi/10.1016/j.disc.2020.112169 info:eu-repo/semantics/openAccess License undefined Discrete Mathematics. - 2021, vol. 344, no. 1, p. 112169 Theoretical Computer Science Discrete Mathematics and Combinatorics info:eu-repo/classification/udc/004 Reducing the domination number of graphs via edge contractions and vertex deletions http://purl.org/coar/resource_type/c_6501