2026-07-23T21:03:20Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10985 2024-03-06T10:46:59Z ddc:004 open_access

Reducing the Domination Number of Graphs via Edge Contractions Galby, Esther Lima, Paloma T. Ries, Bernard domination number blocker problem graph classes 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Esther Galby and Paloma T. Lima and Bernard Ries 2019 Is Part Of LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2019.41 urn:nbn:de:0030-drops-109856 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.41 eng https://creativecommons.org/licenses/by/3.0/legalcode