摘要：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 = 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.
