In: Discrete Mathematics, 2021, vol. 344, no. 1, p. 112169
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...
|
In: 30th International Symposium on Algorithms and Computation (ISAAC) - Leibniz International Proceedings in Informatics, 2019, vol. 149, no. 21, p. 1-14
In this paper, we consider the following problem: given a connected graph G, can we reduce the domination number of G by one by using only one edge contraction? We show that the problem is NP-hard when restricted to {P6, P4 + P2}-free graphs and that it is coNP-hard when restricted to subcubic claw-free graphs and 2P3-free graphs. As a consequence, we are able to establish a complexity dichotomy...
|
In: 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019) - LIPICS Vol. 138, 2019, p. 41:1-41: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 that...
|
