Faculté des sciences économiques et sociales

Reducing the Domination Number of Graphs via Edge Contractions

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

In: 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019), 2014, no. 41, p. 1-13

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... More

Add to personal list
    Summary
    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 P9-free graphs, bipartite graphs and {C3, . . . ,Cl}-free graphs for any l>= 3. Finally, we show that for any k >=1, the problem is polynomial- time solvable for P5-free graphs and that it can be solved in FPT-time and XP-time when parameterized by tree-width and mim-width, respectively.