On the Parameterized Complexity of Reconfiguration of Connected Dominating Sets

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