2026-08-16T12:04:58Z https://drops.dagstuhl.de/oai
oai:drops-oai.dagstuhl.de:13327 2024-03-06T10:51:42Z ddc:004 open_access
On the Parameterized Complexity of Reconfiguration of Connected Dominating Sets Lokshtanov, Daniel Mouawad, Amer E. Panolan, Fahad Siebertz, Sebastian reconfiguration parameterized complexity connected dominating set graph structure theory 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. Schloss Dagstuhl – Leibniz-Zentrum fΓΌr Informatik Daniel Lokshtanov and Amer E. Mouawad and Fahad Panolan and Sebastian Siebertz 2020 Is Part Of LIPIcs, Volume 180, 15th International Symposium on Parameterized and Exact Computation (IPEC 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2020.24 urn:nbn:de:0030-drops-133276 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2020.24 eng https://creativecommons.org/licenses/by/3.0/legalcode