On the Parameterized Complexity of Reconfiguration of Connected Dominating Sets
In a reconfiguration version of a decision problem $$\mathcal {Q}$$ Q the input is an instance of $$\mathcal {Q}$$ 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 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}$$ K d , d as a subgraph, for some constant $$d \ge 1$$ 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+\ell $$ 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.