Galby, Esther Lima, Paloma T. Ries, Bernard 2019 In this paper, 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 <= 2, the problem is coNP-hard. We further prove that for k=1, the problem is W[1]-hard parameterized by the size of a minimum dominating set plus the mim-width of the input graph, and that it remains NP-hard when restricted to P_9-free graphs, bipartite graphs and {C_3,...,C_{l}}-free graphs for any l >= 3. Finally, we show that for any k >= 1, the problem is polynomial-time solvable for P_5-free graphs and that it can be solved in FPT-time and XP-time when parameterized by tree-width and mim-width, respectively. application/pdf https://folia.unifr.ch/global/documents/308092 https://folia.unifr.ch/documents/308092/files/BLOCKER.pdf eng info:eu-repo/semantics/altIdentifier/doi/10.4230/LIPIcs.MFCS.2019.41 info:eu-repo/semantics/openAccess License undefined 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019) - LIPICS Vol. 138 / Rossmanith, Peter ; Heggernes, Pinar ; Katoen,Joost-Pieter. - Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH. - 2019, p. 41:1-41:13 domination number blocker problem graph classes info:eu-repo/classification/udc/004 Reducing the Domination Number of Graphs via Edge Contractions http://purl.org/coar/resource_type/c_5794