Conference paper (in proceedings)

Reducing the Domination Number of Graphs via Edge Contractions

Published in:
  • 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
English 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.
Faculté des sciences économiques et sociales et du management
Département d'informatique
  • English
Computer science and technology
License undefined
Persistent URL

Document views: 40 File downloads:
  • BLOCKER.pdf: 73