Reducing the Domination Number of Graphs via Edge Contractions
- Galby, Esther University of Fribourg, Switzerland
- Lima, Paloma T. University of Bergen, Norway
- Ries, Bernard University of Fribourg, Switzerland
-
2019
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.
- Faculty
- Faculté des sciences économiques et sociales et du management
- Department
- Département d'informatique
- Language
-
- English
- Classification
- Computer science and technology
- License
- License undefined
- Identifiers
-
- RERO DOC 327277
- DOI 10.4230/LIPIcs.MFCS.2019.41
- Persistent URL
- https://folia.unifr.ch/unifr/documents/308092
Statistics
Document views: 58
File downloads:
- BLOCKER.pdf: 140