License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2020.24
URN: urn:nbn:de:0030-drops-133276
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/13327/
Lokshtanov, Daniel ;
Mouawad, Amer E. ;
Panolan, Fahad ;
Siebertz, Sebastian
On the Parameterized Complexity of Reconfiguration of Connected Dominating Sets
Abstract
In a reconfiguration version of a decision problem ? the input is an instance of ? and two feasible solutions S and T. The objective is to determine whether there exists a step-by-step transformation between S and T such that all intermediate steps also constitute feasible solutions. In this work, we study the parameterized complexity of the Connected Dominating Set Reconfiguration problem (CDS-R). It was shown in previous work that the Dominating Set Reconfiguration problem (DS-R) parameterized by k, the maximum allowed size of a dominating set in a reconfiguration sequence, is fixed-parameter tractable on all graphs that exclude a biclique K_{d,d} as a subgraph, for some constant d ≥ 1. We show that the additional connectivity constraint makes the problem much harder, namely, that CDS-R is W[1]-hard parameterized by k+?, the maximum allowed size of a dominating set plus the length of the reconfiguration sequence, already on 5-degenerate graphs. On the positive side, we show that CDS-R parameterized by k is fixed-parameter tractable, and in fact admits a polynomial kernel on planar graphs.
BibTeX - Entry
@InProceedings{lokshtanov_et_al:LIPIcs:2020:13327,
author = {Daniel Lokshtanov and Amer E. Mouawad and Fahad Panolan and Sebastian Siebertz},
title = {{On the Parameterized Complexity of Reconfiguration of Connected Dominating Sets}},
booktitle = {15th International Symposium on Parameterized and Exact Computation (IPEC 2020)},
pages = {24:1--24:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-172-6},
ISSN = {1868-8969},
year = {2020},
volume = {180},
editor = {Yixin Cao and Marcin Pilipczuk},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/13327},
URN = {urn:nbn:de:0030-drops-133276},
doi = {10.4230/LIPIcs.IPEC.2020.24},
annote = {Keywords: reconfiguration, parameterized complexity, connected dominating set, graph structure theory}
}
|
Keywords: |
|
reconfiguration, parameterized complexity, connected dominating set, graph structure theory |
|
Collection: |
|
15th International Symposium on Parameterized and Exact Computation (IPEC 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
04.12.2020 |
