On the Parameterized Complexity of Reconfiguration of Connected Dominating Sets

DOI10.1007/S00453-021-00909-5MaRDI QIDQ6326351arXivFDO

Authors Daniel Lokshtanov, Amer E. Mouawad, Fahad Panolan, Sebastian Siebertz

Publication date 1 October 2019

Published in arXiv

Full work available at URL https://doi.org/10.1007/S00453-021-00909-5

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10)

arXiv classification

cs.CCcs.DMcs.DSmath.CO

Abstract: In a reconfiguration version of an optimization problem $mathcalQ$ the input is an instance of $mathcalQ$ 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 extsc{Connected Dominating Set Reconfiguration} problem ( extsc{CDS-R)}. It was shown in previous work that the extsc{Dominating Set Reconfiguration} problem ( extsc{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 $dgeq1$. We show that the additional connectivity constraint makes the problem much harder, namely, that extsc{CDS-R} is extsf{W}$[1]$-hard parameterized by $k+ell$, 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 extsc{CDS-R} parameterized by $k$ is fixed-parameter tractable, and in fact admits a polynomial kernel on planar graphs.

This page was built for publication: On the Parameterized Complexity of Reconfiguration of Connected Dominating Sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6326351)