University of California Santa Barbara, Santa Barbara<EMAIL_ADDRESS>Department of Computer Science, American University of Beirut,
<EMAIL_ADDRESS>Department of Computer Science and Engineering, IIT
Hyderabad<EMAIL_ADDRESS>University of Bremen, Germanysiebertz@uni-
bremen.de Daniel Lokshtanov, Amer E. Mouawad, Fahad Panolan, Sebastian
Siebertz

###### Acknowledgements.

John Q. Open and Joan R. Access 2 2020

# On the Parameterized Complexity of Reconfiguration of Connected Dominating
Sets

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

###### Abstract.

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 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\geq 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$, 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.

###### Key words and phrases:

reconfiguration, parameterized complexity, connected dominating set, graph
structure theory

###### 1991 Mathematics Subject Classification:

CCS $\rightarrow$ Theory of computation $\rightarrow$ Design and analysis of
algorithms $\rightarrow$ Parameterized complexity and exact algorithms

###### category:

##  1\. Introduction

In an optimization problem $\mathcal{Q}$, we are usually asked to determine
the existence of a feasible solution for an instance $\mathcal{I}$ of
$\mathcal{Q}$. In a _reconfiguration version_ of $\mathcal{Q}$, we are instead
given a source feasible solution $S$ and a target feasible solution $T$ and we
are asked to determine whether it is possible to transform $S$ into $T$ by a
sequence of step-by-step transformations such that after each intermediate
step we also maintain feasible solutions. Formally, we consider a graph,
called the _reconfiguration graph_ , that has one vertex for each feasible
solution and where two vertices are connected by an edge if we allow the
transformation between the two corresponding solutions. We are then asked to
determine whether $S$ and $T$ are connected in the reconfiguration graph, or
even to compute a shortest path between them. Historically, the study of
reconfiguration questions predates the field of computer science, as many
classic one-player games can be formulated as such reachability questions [16,
18], e.g., the $15$-puzzle and Rubik’s cube. More recently, reconfiguration
problems have emerged from computational problems in different areas such as
graph theory [1, 14, 15], constraint satisfaction [11, 23] and computational
geometry [4, 17, 21], and even quantum complexity theory [10]. Reconfiguration
problems have been receiving considerable attention in recent literature, we
refer the reader to [26, 30, 22] for an extensive overview.

In this work, we consider the Connected Dominating Set Reconfiguration problem
(CDS-R) in undirected graphs. A _dominating set_ in a graph $G$ is a set
$D\subseteq V(G)$ such that every vertex of $G$ lies either in $D$ or is
adjacent to a vertex in $D$. A dominating set $D$ is a _connected dominating
set_ if the graph induced by $D$ is connected. The Dominating Set problem and
its connected variant have many applications, including the modeling of
facility location problems, routing problems, and many more.

We study CDS-R under the _Token Addition/Removal_ model (TAR model). Suppose
we are given a connected dominating set $D$ of a graph $G$, and imagine that a
token/pebble is placed on each vertex in $D$. The TAR rule allows either the
addition or removal of a single token/pebble at a time from $D$, if this
results in a connected dominating set of size at most a given bound $k\geq 1$.
A sequence $D_{1},\ldots,D_{\ell}$ of connected dominating sets of a graph $G$
is called a _reconfiguration sequence_ between $D_{1}$ and $D_{\ell}$ under
TAR if the change from $D_{i}$ to $D_{i+1}$ respects the TAR rule, for $1\leq
i<\ell$. The _length_ of the reconfiguration sequence is $\ell-1$. The
(Connected) Dominating Set Reconfiguration problem for TAR gets as input a
graph $G$, two (connected) dominating sets $S$ and $T$ and an integer $k\geq
1$, and the task is to decide whether there exists a reconfiguration sequence
between $S$ and $T$ under TAR using at most $k$ tokens/pebbles.

Structural properties of the reconfiguration graph for $k$-dominating sets
were studied in [13, 29]. The Dominating Set Reconfiguration problem was shown
to be PSPACE-complete in [24], even on split graphs, bipartite graphs, planar
graphs and graphs of bounded bandwidth. Both pathwidth and treewidth of a
graph are bounded by its bandwidth, hence the Dominating Set Reconfiguration
problem is PSPACE-complete on graphs of bounded pathwidth and treewidth. These
hardness results motivated the study of the parameterized complexity of the
problem. It was shown in [24] that the Dominating Set Reconfiguration problem
is $\textsf{W}[2]$-hard when parameterized by $k+\ell$, where $k$ is the bound
on the number of tokens and $\ell$ is the length of the reconfiguration
sequence. However, the problem becomes fixed-parameter tractable on graphs
that exclude a fixed complete bipartite graph $K_{d,d}$ as a subgraph, as
shown in [20]. Such so-called _biclique-free_ classes are very general sparse
graph classes, including in particular the planar graphs, which are
$K_{3,3}$-free.

In this work we study the complexity of CDS-R. The standard reduction from
Dominating Set to Connected Dominating Set shows that also CDS-R is PSPACE-
complete, even on graphs of bounded pathwidth (Figure 1).

$G$$G$$V(G)$$V(G)$$k+1$$H$ Figure 1. A graph $G$ with a minimum dominating set
of size $k=2$ marked in dark blue and the graph $H$ obtained in the standard
reduction from Dominating Set to Connected Dominating Set. $G$ has a
dominating set of size $k$ if and only if $H$ has a connected dominating set
of size $k+1$. If $p$ is equal to the pathwidth of $G$ then the pathwidth of
$H$ is bounded by $2p+1$.

We hence turn our attention to the parameterized complexity of the problem. We
first show that the additional connectivity constraint makes the problem much
harder, namely, that CDS-R parameterized by $k+\ell$ is W$[1]$-hard already on
$5$-degenerate graphs. As $5$-degenerate graphs exclude the biclique $K_{6,6}$
as a subgraph, Dominating Set Reconfiguration is fixed-parameter tractable on
much more general graph classes than its connected variant. To prove hardness
we first introduce an auxiliary problem that we believe is of independent
interest. In the Colored Connected Subgraph problem we are given a graph $G$,
an integer $k$, and a coloring $c\colon V(G)\rightarrow C$, for some color set
$C$ with $|C|\leq k$. The question is whether $G$ contains a vertex subset $H$
on at most $k$ vertices such that $G[H]$ is connected and $H$ contains at
least one vertex of every color in $C$ (i.e., $c(V(H))=C$). The
reconfiguration variant Colored Connected Subgraph Reconfiguration (CCS-R) is
defined as expected. We first prove that CCS-R reduces to CDS-R by a parameter
preserving reduction (where $k+\ell$ is the parameter) and the degeneracy of
the reduced graph is at most the degeneracy of the input graph plus one. We
then prove that the known $\textsf{W}[1]$-hard problem Multicolored Clique
reduces to CCS-R on $4$-degenerate graphs. The last reduction has the
additional property that for an input $(G,c,k)$ of Multicolored Clique the
resulting instance of CCS-R admits either a reconfiguration sequence of length
$\mathcal{O}(k^{3})$, or no reconfiguration sequence at all. Hence, we derive
that both CDS-R and CCS-R are $\textsf{W}[1]$-hard parameterized by $k+\ell$
on $5$-degenerate and $4$-degenerate graphs, respectively.

fpt withparameter $k+\ell$W$[1]$-hard withparameter $k+\ell$fpt withparameter
$k$nowhere densebiclique-freeboundedVC-dimensionbounded
degreeexcludedtopologicalminorbounded expansiondegenerateplanarexcluded
minorboundedpathwidthbounded treewidthbounded cliquewidth Figure 2. The map of
tractability for Connected Dominating Set Reconfiguration. The classes colored
in dark green admit an fpt algorithm with parameter $k$, the classes colored
in light green admit an FPT algorithm with parameter $k+\ell$. On the classes
colored in red the problem is $\mathsf{W}[1]$-hard with respect to the
parameter $k+\ell$.

The existence of a reconfiguration sequence of length at most $\ell$ with
connected dominating sets of size at most $k$ can be expressed by a first-
order formula of length depending only on $k$ and $\ell$. It follows from [12]
that the problem is fixed-parameter tractable parameterized by $k+\ell$ on
every nowhere dense graph class and the same is implied by [2] for every class
of bounded cliquewidth. Nowhere dense graph classes are very general classes
of uniformly sparse graphs, in particular the class of planar graphs is
nowhere dense. Nowhere dense classes are themselves biclique-free, but are not
necessarily degenerate. Hence, our hardness result on degenerate graphs
essentially settles the question of fixed-parameter tractability for the
parameter $k+\ell$ on sparse graph classes. It remains an interesting open
problem to find dense graph classes beyond classes of bounded cliquewidth on
which the problem is fixed-parameter tractable.

We then turn our attention to the smaller parameter $k$ alone. We show that
CDS-R parameterized by $k$ is fixed-parameter tractable on the class of planar
graphs. Our approach is as follows. We first compute a small _domination core_
for $G$, a set of vertices that captures exactly the domination properties of
$G$ for dominating sets of sizes not larger than $k$. The notion of a
domination core was introduced in the study of the Distance-$r$ Dominating Set
problem on nowhere dense graph classes [3]. While the classification of
interactions with the domination core would suffice to solve Dominating Set
Reconfiguration on nowhere dense classes, additional difficulties arise for
the connected variant. In a second step we use planarity to identify large
subgraphs that have very simple interactions with the domination core and
prove that they can be replaced by constant size gadgets such that the
reconfiguration properties of $G$ are preserved.

Observe that CDS-R parameterized by $k$ is trivially fixed-parameter tractable
on every class of bounded degree. The existence of a connected dominating set
of size $k$ implies that the diameter of $G$ is bounded by $k+2$, which in
every bounded degree class implies a bound on the size of the graph depending
only on the degree and $k$. We conjecture that CDS-R is fixed-parameter
tractable parameterized by $k$ on every nowhere dense graph class. However,
resolving this conjecture remains open for future work (see Figure 2).

The rest of the paper is organized as follows. We give background on graph
theory and fix our notation in Section 2. We show hardness of CDS-R on
degenerate graphs in Section 3 and finally show how to handle the planar case
in Section 4. Due to space constraints proofs of results marked with a $\star$
are deferred to the appendix.

##  2\. Preliminaries

We denote the set of natural numbers by $\mathbb{N}$. For $n\in\mathbb{N}$, we
let $[n]=\\{1,2,\dots,n\\}$. We assume that each graph $G$ is finite, simple,
and undirected. We let $V(G)$ and $E(G)$ denote the vertex set and edge set of
$G$, respectively. An edge between two vertices $u$ and $v$ in a graph is
denoted by $\\{u,v\\}$ or $uv$. The open neighborhood of a vertex $v$ is
denoted by $N_{G}(v)=\\{u\mid\\{u,v\\}\in E(G)\\}$ and the closed neighborhood
by $N_{G}[v]=N_{G}(v)\cup\\{v\\}$. The degree of a vertex $v$, denoted
$d_{G}(v)$, is $|N_{G}(v)|$. For a set of vertices $S\subseteq V(G)$, we
define $N_{G}(S)=\\{v\not\in S\mid\\{u,v\\}\in E(G),u\in S\\}$ and
$N_{G}[S]=N_{G}(S)\cup S$. The subgraph of $G$ induced by $S$ is denoted by
$G[S]$, where $G[S]$ has vertex set $S$ and edge set $\\{\\{u,v\\}\in E(G)\mid
u,v\in S\\}$. We let $G-S=G[V(G)\setminus S]$. A graph $G$ is $d$-degenerate
if every subgraph $H\subseteq G$ has a vertex of degree at most $d$. For a set
$C$, we use $K[C]$ to denote the complete graph on vertex set $C$. For an
integer $r\in{\mathbb{N}}$, an $r$-independent set in a graph $G$ is a subset
$U\subseteq V(G)$ such that for any two distinct vertices $u,v\in U$, the
distance between $u$ and $v$ in $G$ is more than $r$. An independent set in a
graph is a $1$-independent set. A subset of vertices $U$ in $G$ is called a
separator in $G$ if $G-U$ is has more than one connected component. For
$s,t\in V(G)$, we say that a subset of vertices $U$ in $G$ is an
$(s,t)$-separator in $G$ if there is no path from $s$ to $t$ in $G-U$.

##  3\. Hardness on degenerate graphs

In this section we prove that CDS-R and CCS-R are W$[1]$-hard when
parameterized by $k+\ell$ even on $5$-degenerate and $4$-degenerate graphs,
respectively. Towards that, we first give a polynomial-time reduction from the
$\textsf{W}[1]$-hard Multicolored Clique problem to CCS-R on $4$-degenerate
graphs with the property that for an input $(G,c,k)$ of Multicolored Clique
the resulting instance of CCS-R admits either a reconfiguration sequence of
length $\mathcal{O}(k^{3})$ or no reconfiguration sequence at all. As a
result, we conclude that CCS-R is W$[1]$-hard when parameterized by $k+\ell$
on $4$-degenerate graphs. Then, we give a parameter-preserving polynomial-time
reduction from CCS-R to CDS-R. Let us first formally define the CCS problem.

Colored Connected Subgraph (CCS) Parameter: $k$ Input: A graph $G$,
$k\in\mathbb{N}$, and a vertex-coloring $c\colon V(G)\rightarrow C$, where
$|C|\leq k$ Question: Is there a vertex subset $S\subseteq V(G)$ of at most
$k$ vertices with at least one vertex from every color class such that $G[S]$
is connected?

#### Reduction from Multicolored Clique to CCS-R.

We now present the reduction from Multicolored Clique to CCS-R, which we
believe to be of independent interest. We can assume, without loss of
generality, that for an input $(G,c,k)$ of Multicolored Clique, $G$ is
connected and $c$ is a proper vertex-coloring, i.e., for any two distinct
vertices $u,v\in V(G)$ with $c(u)=c(v)$ we have $\\{u,v\\}\notin E(G)$. Before
we proceed let us define a graph operation.

######  Definition 3.1.

Let $G$ be a graph and let $c\colon V(G)\rightarrow\\{1,\ldots,k\\}$ be a
proper vertex coloring of $V(G)$. Let $H$ be a graph on the vertex set
$\\{1,\ldots,k\\}$. We define the graph $G\upharpoonright_{c}H$ as follows. We
remove all edges $\\{u,v\\}\in E(G)$ such that $c(u)=i$ and $c(v)=j$ and
$\\{i,j\\}\not\in E(H)$. We subdivide every remaining edge, i.e. for every
remaining edge $\\{u,v\\}$ we introduce a new vertex $s_{uv}$, remove the edge
$\\{u,v\\}$ and introduce instead the two edges $\\{u,s_{uv}\\}$ and
$\\{v,s_{uv}\\}$. We write $W(G\upharpoonright_{c}H)$ for the set of all
subdivision vertices $s_{uv}$ (see Figure 3).

$\bullet$$\bullet$$u$$\bullet$$\bullet$$v$$\bullet$$\bullet$$\bullet$$\bullet$$1$$2$$3$$4$
(a) A graph $G$ and a proper coloring $c\colon
V(G)\rightarrow\\{1,\ldots,4\\}$

$\bullet$$\bullet$$\bullet$$\bullet$$1$$2$$3$$4$ (b) A graph $H$ on the vertex
set $\\{1,\ldots,4\\}$

$\bullet$$\bullet$$u$$\bullet$$\bullet$$v$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$s_{uv}=w_{1}$$w_{2}$$w_{3}$$w_{4}$$w_{5}$
(c) The graph $G\upharpoonright_{c}H$. Here,
$W(G\upharpoonright_{c}H)=\\{w_{1},\ldots,w_{5}\\}$

Figure 3. Construction of $G\upharpoonright_{c}H$.

Let $(G,c,k)$ be the input instance of Multicolored Clique, where $G$ is a
connected graph and $c$ is a proper $k$-vertex-coloring of $G$. We construct
an instance $(H,\widehat{c}\colon V(H)\mapsto[k+1],Q_{s},Q_{t},2k)$ of CCS-R.

We first construct a routing gadget. For $1\leq i\leq k$, let $T^{i}$ be the
star with vertex set $\\{1,\ldots,k\\}$ having vertex $i$ as the center. For
any $1\leq i\leq k$ and $1\leq r\leq 20k$, we let $H^{(i,r)}$ be a copy of the
graph $G\upharpoonright_{c}T^{i}$. We let $c_{(i,r)}$ be the the partial
vertex-coloring of $H^{(i,r)}$ that is naturally inherited from $G$. For an
illustration, consider the input instance $(G,c,k)$ of Multicolored Clique
depicted in Figure 3(a). Then, $T^{2}$ is identical to the graph $H$ in Figure
3(b) and Figure 3(c) represents $H^{(2,r)}=G\upharpoonright_{c}T^{2}$, for any
$1\leq r\leq 20k$. Now, for $1\leq i\leq k$ we define a graph $H^{i}$ as
follows. We use $W(H^{(i,r)})$ to denote the set of subdivision vertices in
$H^{(i,r)}$. For $1\leq r<20k$ and all vertices $u,v$ in
$V(H^{(i,r)})\setminus W(H^{(i,r)})$, we connect the copy of the subdivision
vertex $s_{uv}$ in $H^{(i,r)}$ (if it exists) with the copies of the vertices
$u$ and $v$ in $H^{(i,r+1)}$ (see Figure 4 for an illustration of a portion of
$H^{1}$). We use $W(H^{i})$ to denote the set of subdivision vertices
$\bigcup_{r\in[20k]}W(H^{(i,r)})$.

For each $1\leq i\leq k$, we use $c_{i}$ to denote a coloring on $V(H^{i})$
that is a union of $c_{(i,1)},c_{(i,2)},\ldots,c_{(i,20k)}$ and we color all
the copies of the subdivision vertices using a new color $k+1$. In other
words, we know that for each $u\in V(H^{i})$ we have $u\in V(H^{(i,r)})$, for
some $r\in\\{1,\ldots,20k\\}$. Hence, if $u\in V(H^{(i,r)})\setminus
W(H^{(i,r)})$ then we set $c_{i}(u)=c_{(i,r)}(u)$. For all $s_{uv}\in
W(H^{i})$, we set $c_{i}(s_{uv})=k+1$.

$H^{(1,1)}$$H^{(1,2)}$$H^{(1,3)}$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$
Figure 4. Construction of $H^{1}$ from the instance $(G,c)$ depicted in Figure
3(a). The red edges are some of the “crossing” edges but not all of them.

Now, define a graph $R$, which is super graph of $H^{1}\cup\ldots\cup H^{k}$,
as follows. For $1\leq i<k$ and all vertices $u$ and $v$, we connect the copy
of the subdivision vertex $s_{uv}$ in $H^{(i,20k)}$ (if it exists) with the
copies of the vertices $u$ and $v$ in $H^{(i+1,1)}$ (see Figure 5 for an
illustration).

$H^{(2,20k)}$$H^{(3,1)}$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$
Figure 5. Illustration of the subgraph of $R$ induced on $V(H^{(2,20k)})\cup
V(H^{3,1})$ constructed from the instance $(G,c,k)$ depicted in Figure 3(a).
The red edge are some of the “crossing edges”.

We additionally introduce two subgraphs $H^{0}$ and $H^{k+1}$. The graph
$H^{0}$ is obtained by subdividing each edge of a star on vertex set
$\\{v_{1},\ldots,v_{k}\\}$ centered at $v_{1}$. Here we use
$w_{2},\ldots,w_{k}$ to denote the subdivision vertices. Similarly, the graph
$H^{k+1}$ is obtained by subdividing each edge of star on
$\\{x_{1},\ldots,x_{k}\\}$ centered at $x_{k}$. Here $y_{1},\ldots,y_{k-1}$
denote the subdivision vertices. Let $c_{0}$ and $c_{k+1}$ be the colorings on
$\\{v_{1},\ldots,v_{k},w_{2},\ldots,w_{k}\\}$ and
$\\{x_{1},\ldots,x_{k},y_{1},\ldots,y_{k-1}\\}$, respectively, defined as
follows. For all $1\leq i\leq k$, $c_{0}(v_{i})=i$ and $c_{k+1}(x_{i})=i$. For
all $2\leq i\leq k$, $c_{0}(w_{i})=k+1$ and for all $1\leq i\leq k-1$,
$c_{k+1}(y_{i})=k+1$. Observe that we may interpret $H^{0}$ as
$K[\\{v_{1},\ldots,v_{k}\\}]\upharpoonright_{c_{0}}T^{0}$ and $H^{k+1}$ as
$K[\\{x_{1},\ldots,x_{k}\\}]\upharpoonright_{c_{k+1}}T^{k+1}$, where $T^{0}$
and $T^{k+1}$ are two trees on vertex set $\\{1,\ldots,k\\}$, with
$E(T^{0})=\\{\\{1,i\\}\colon 2\leq i\leq k\\}$ and
$E(T^{k+1})=\\{\\{k,i\\}\colon 1\leq i\leq k-1\\}$.

Finally, for each $2\leq i\leq k$, we connect the “subdivision vertex” $w_{i}$
(adjacent to $v_{1}$ and $v_{i}$) to all vertices $v\in V(H^{(1,1)})$ colored
$1$ or $i$, i.e., with $c_{(1,1)}(v)\in\\{1,i\\}$. For each subdivision vertex
$s_{ab}\in W(H^{(k,20k)})$, we connect $s_{ab}$ to $x_{k}$ and $x_{i}$, where
$k=c_{k}(a)=c_{(k,20k)}(a)$ and $i=c_{k}(b)=c_{(k,20k)}(b)$. Recall that
$s_{ab}$ is adjacent a vertex of color $k$ and a vertex of color $i$, for some
$i<k$. This completes the construction of $H$ (see Figure 6). We define
$\widehat{c}\colon V(H)\mapsto[k+1]$ to be the union of
$c_{0},\ldots,c_{k+1}$.

$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$v_{1}$$v_{2}$$v_{3}$$v_{4}$$w_{2}$$w_{3}$$w_{4}$$H^{(1,1)}$$H^{(4,20k)}$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$x_{1}$$x_{2}$$x_{3}$$x_{4}$$y_{1}$$y_{2}$$y_{3}$
Figure 6. Illustration of connection between $H^{0}$ and $R$, and $H^{k+1}$
and $R$ from the instance $(G,c,k)$ depicted in Figure 3(a). The red edge are
some of the “crossing edges” between $H^{0}$ and $H^{1}$, and $H^{k}$ and
$H^{k+1}$.

######  Observation 3.2.

The sets $\\{v_{1},\ldots,v_{k},w_{2},\ldots,w_{k}\\}$ and
$\\{x_{1},\ldots,x_{k}$, $y_{1},\ldots,y_{k-1}\\}$ are solutions of size
$2k-1$ of the CCS instance $(H,\widehat{c},2k)$.

We define the starting configuration $Q_{s}$ as the set
$\\{v_{1},\ldots,v_{k},w_{2},\ldots,w_{k}\\}$ and the target configuration
$Q_{t}$ as the set $\\{x_{1},\ldots,x_{k}$, $y_{1},\ldots,y_{k-1}\\}$. We now
consider the instance $(H,\widehat{c},Q_{s},Q_{t},2k)$ of the CCS-R problem.
That is, the bound on the sizes of the solutions in the reconfiguration
sequence is at most $2k$. Before we analyze the reconfiguration properties of
$H$, let us verify that $H$ is $4$-degenerate.

######  Lemma 3.3 ($\star$).

The graph $H$ is $4$-degenerate.

######  Lemma 3.4 ($\star$).

if there exists a $k$-colored clique in $G$ then there is reconfiguration
sequence of length $\mathcal{O}(k^{3})$ from $Q_{s}$ to $Q_{t}$ in
$(H,\widehat{c},2k)$.

######  Proof 3.5 (Proof sketch).

We aim to shift the connected vertices of $Q_{s}$ through the subgraphs
$H^{1},\ldots,H^{k}$ (in that order) to maintain connectivity and eventually
shift all the tokens to $Q_{t}$. For each $u_{i}\in V(G)$, $1\leq j\leq k$ and
$1\leq r\leq 20k$, we use $u_{i}^{(j,r)}$ to denote the copy of $u_{i}$ in
$H^{(j,r)}$. Let $C=\\{u_{1},\ldots,u_{k}\\}$ be a $k$-colored clique in $G$
such that $c(u_{i})=i$, for all $1\leq i\leq k$. To prove the lemma, we need
to define a reconfiguration sequence starting from $Q_{s}$ and ending at
$Q_{t}$ such that the cardinality of any solution in the sequence is at most
$2k$. First we define $k$ “colored” trees
$\widehat{T}_{1},\ldots,\widehat{T}_{k}$ each on $2k-1$ vertices, and then
prove that there are reconfiguration sequences from $Q_{s}$ to
$V(\widehat{T}_{1})$, $V(\widehat{T}_{i})$ to $V(\widehat{T}_{i+1})$ for all
$1\leq i<k$, and $V(\widehat{T}_{k})$ to $Q_{t}$.

We start by defining $\widehat{T}_{1},\ldots,\widehat{T}_{k}$. For each $1\leq
i\leq k$, $C_{i}=\\{u^{(i,1)}_{1},\ldots,u_{k}^{(i,1)}\\}$ and $S_{i}=\\{z\in
V(H^{(i,1)})\colon N_{H^{(i,1)}}(z)\cap C_{i}=2\\}$. That is, for each $1\leq
j\leq k$ and $j\neq i$, $s_{u_{i}^{(i,1)}u_{j}^{(i,1)}}\in S_{i}$ (the
subdivision vertex on the edge $u_{i}^{(i,1)}u_{j}^{(i,1)}$ is in $S_{i}$),
and $|S_{i}|=k-1$. In other words, $C_{i}$ contains the copies of the vertices
of the clique $C$ in $H^{(i,1)}$ and $S_{i}$ contains subdivision vertices
corresponding to $k-1$ edges in the clique incident on the $i$th colored
vertex of the clique, such that $H[C_{i}\cup S_{i}]$ is a tree. Now, define
$\widehat{T}_{i}=H[C_{i}\cup S_{i}]$. It is easy to verify that
$\widehat{c}(C_{i}\cup S_{i})=\\{1,\ldots,k+1\\}$ and hence $C_{i}\cup
S_{i}=V(\widehat{T}_{i})$ is a solution to the CCS instance
$(H,\widehat{c},2k)$. Let $T_{s}=H[Q_{s}]$ and $T_{t}=H[Q_{t}]$. Note that
$T_{s}$ and $T_{t}$ are trees on $2k-1$ vertices.

Case 1: Reconfiguration from $Q_{s}$ to $V(\widehat{T}_{1})$. Informally, we
move to $\widehat{T}_{1}$ by adding a token on $u_{i}^{(1,1)}$ and then
removing tokens from $v_{i}$ for $i$ in the order $2,\ldots,k,1$ (for a total
of $2k$ token additions/removals). Finally, we move the tokens from
$\\{w_{2},\ldots,w_{k-1}\\}$ to $S_{1}$ in $2(k-1)$ steps. The length of the
reconfiguration sequence is $2k+2(k-1)=4k-2$.

Case 2: Reconfiguration from $V(\widehat{T}_{i})$ to $V(\widehat{T}_{i+1})$.
First we define $20k$ trees $P_{1},\ldots P_{20k}$, each on $2k-1$ vertices
such that for all $1\leq r\leq 20k$, $(i)$ $V(P_{r})\subseteq V(H^{(i,r)})$,
and $(ii)$ $\widehat{T}_{i}=P_{1}$. Then we give a reconfiguration sequence
from $V(P_{r})$ to $V(P_{r+1})$ for all $r\in[20k-1]$ and a reconfiguration
sequence from $V(P_{20k})$ to $V(\widehat{T}_{i+1})$.

Recall that $C=\\{u_{1},\ldots,u_{k}\\}$ is a $k$-colored clique in $G$ such
that $c(u_{i})=i$ for all $1\leq i\leq k$. For $1\leq r\leq 20k$, let
$C_{i}^{r}=\\{u^{(i,r)}_{1},\ldots,u_{k}^{(i,r)}\\}$ and $S_{i}^{r}=\\{z\in
V(H^{(i,r)})\colon N_{H^{(i,r)}}(z)\cap C_{i}^{r}=2\\}$. That is, for each
$1\leq j\leq k$ and $j\neq i$, $s_{u_{i}^{(i,r)}u_{j}^{(i,r)}}\in S_{i}^{r}$
(i.e, the subdivision vertex on the edge $u_{i}^{(i,r)}u_{j}^{(i,r)}$ is in
$S_{i}^{r}$) and $|S_{i}^{r}|=k-1$. Let $P_{r}=H[C_{i}^{r}\cup S^{r}_{i}]$.
Notice that for all $r\in[20k]$, $P_{r}$ is a tree on $2k-1$ vertices.
Moreover, for each $1\leq r\leq 20k$, $V(P_{r})$ is a solution to the CCS
instance $(H,\widehat{c},2k)$. By arguments similar to those given for Case
$1$, one can prove that there is a reconfiguration sequence of length $4k-2$
from $V(P_{r})$ to $V(P_{r+1})$, for all $1\leq r<20k$.

For the reconfiguration sequence from $V(P_{20k})$ to $V(\widehat{T}_{i+1})$
we refer the reader to the complete proof in the appendix.

Case 3: Reconfiguration from $V(\widehat{T}_{k})$ to $V({T}_{t})$. The
arguments for this case are similar to those given in Case 1, we therefore
omit the details.

######  Lemma 3.6 ($\star$).

If there is a reconfiguration sequence from $Q_{s}$ to $Q_{t}$ then there is a
$k$-colored clique in $G$.

######  Theorem 3.7.

CCS-R parameterized by $k+\ell$ is $\mathsf{W}[1]$-hard on $4$-degenerate
graphs.

#### Reduction from CCS-R to CDS-R.

We give a polynomial-time parameter-preserving reduction from CCS-R to CDS-R
that is fairly straightforward. Let $(G,c,S,T,k)$ be an instance of CCS-R. Let
$c\colon V(G)\mapsto\\{1,\ldots,k^{\prime}\\}$, where $k^{\prime}\leq k$. We
construct a graph $H$ as follows. For each $1\leq i\leq k^{\prime}$, we add a
vertex $d_{i}$ and connect $d_{i}$ to all the vertices in $c^{-1}(i)$. Next,
for each $1\leq i\leq k^{\prime}$, we add $2k+1$ pendent vertices to $d_{i}$.
That is, we add vertices $\\{x_{i,j}\colon 1\leq i\leq k^{\prime},1\leq j\leq
2k+1\\}$ and edges $\\{\\{x_{i,j},d_{i}\\}\colon 1\leq i\leq k^{\prime},1\leq
j\leq 2k+1\\}$. Let $D=\\{d_{1},\ldots,d_{k^{\prime}}\\}$. We output $(H,S\cup
D,T\cup D,k+k^{\prime})$ as the new CDS-R instance.

######  Lemma 3.8.

If $G$ is a $d$-degenerate graph then $H$ is a $(d+1)$-degenerate graph.

######  Proof 3.9.

For each vertex $v\in V(G)$, $d_{H}(v)=d_{G}(v)+1$. Thus, after removing
$V(G)$ and $\\{x_{i,j}\colon 1\leq i\leq k^{\prime},1\leq j\leq 2k+1\\}$, the
remaining graph is edgeless.

It is easy to verify that for any reconfiguration sequence
$S=S_{1},\ldots,S_{\ell}=T$ of $(G,c,S,T,k)$, $S\cup D=S_{1}\cup
D,\ldots,S_{\ell}\cup D=T\cup D$ is a reconfiguration sequence of $(H,S\cup
D,T\cup D,k+k^{\prime})$. Now we prove the reverse direction.

######  Lemma 3.10.

If $(H,S\cup D,T\cup D,k+k^{\prime})$ is a yes-instance then $(G,c,S,T,k)$ is
a yes-instance.

######  Proof 3.11.

Let $Z$ be a dominating set in $H$ of size at most $k+k^{\prime}$. Then
$D\subseteq H$. Moreover for any minimal connected dominating set $Z$ in $H$,
$Z\cap\\{x_{i,j}\colon 1\leq i\leq k^{\prime},1\leq j\leq 2k+1\\}=\emptyset$,
$H[Z\setminus D]$ is connected, and $Z\setminus D$ contains a vertex from
$c^{-1}(i)$ for all $1\leq i\leq k^{\prime}$ (recall that $G$ is a subgraph of
$H$). Therefore, by deleting $D$ from each set in a reconfiguration sequence
of $(H,S\cup D,T\cup D,k+k^{\prime})$, we get a valid reconfiguration sequence
of $(G,c,S,T,k)$. This completes the proof.

Thus, by Theorem 3.7, we have the following theorem.

######  Theorem 3.12.

CDS-R parameterized by $k+\ell$ is $\mathsf{W}[1]$-hard on $5$-degenerate
graphs.

##  4\. Fixed-parameter tractability on planar graphs

This section is devoted to proving that CDS-R under TAR parameterized by $k$
is fixed-parameter tractable on planar graphs. In fact, we show that the
problem admits a polynomial kernel. Recall that a kernel for a parameterized
problem $\mathcal{Q}$ is a polynomial-time algorithm that computes for each
instance $(I,k)$ of $\mathcal{Q}$ an equivalent instance
$(I^{\prime},k^{\prime})$ with $|I^{\prime}|+k^{\prime}\leq f(k)$ for some
computable function $f$. The kernel is polynomial if the function $f$ is
polynomial. We prove that for every instance $(G,S,T,k)$ of CDS-R, with $G$
planar, we can compute in polynomial time an instance $(G^{\prime},S,T,k)$
where $|V(G^{\prime})|\leq p(k)$ for some polynomial $p$, $G^{\prime}$ planar,
and where there exists a reconfiguration sequence under TAR from $S$ to $T$ in
$G$ (using at most $k$ tokens) if and only if such a sequence exists in
$G^{\prime}$.

Our approach is as follows. We first compute a small _domination core_ for
$G$, that is, a set of vertices that captures exactly the domination
properties of $G$ for dominating sets of sizes not larger than $k$. While the
classification of interactions with the domination core would suffice to solve
Dominating Set Reconfiguration, additional difficulties arise for the
connected variant. In a second step we use planarity to identify large
subgraphs that have very simple interactions with the domination core and
prove that they can be replaced by constant size gadgets such that the
reconfiguration properties of $G$ are preserved.

###  4.1. Domination cores

######  Definition 4.1.

Let $G$ be a graph and let $k\geq 1$ be an integer. A _$k$ -domination core_
is a subset $C\subseteq V(G)$ of vertices such that every set $X\subseteq
V(G)$ of size at most $k$ that dominates $C$ also dominates $G$.

It is not difficult to see that Dominating Set is fixed-parameter tractable on
all graphs that admit a $k$-domination core of size at most $f(k)$ that is
computable in time $g(k)\cdot n^{c}$, for any computable functions $f,g$ and
constant $c$. This approach was first used (implicitly) in [3] to solve
Distance-$r$ Dominating Set on nowhere dense graph classes. In case $k$ is the
size of a minimum (distance-$r$) dominating set, one can establish the
existence of a linear size $k$-domination core on classes of bounded expansion
[5] (including the class of planar graphs) and a polynomial size (in fact an
almost linear size) $k$-domination core on nowhere dense graph classes [19,
7]. If $k$ is not minimum, there exist classes of bounded expansion such that
a $k$-domination core must have at least quadratic size [6]. The most general
graph classes that admit $k$-domination cores are given in [8]. Moreover,
Dominating Set Reconfiguration and Distance-$r$ Dominating Set Reconfiguration
are fixed-parameter tractable on all graphs that admit small (distance-$r$)
$k$-domination cores [20, 28].

######  Lemma 4.2.

There exists a polynomial $p$ such that for all $k\geq 1$, every planar graph
$G$ admits a polynomial-time computable $k$-domination core of size at most
$p(k)$.

The lemma is implied by Theorem 1.6 of [19] by the fact that planar graphs are
nowhere dense. We want to stress again that the polynomial size of the
$k$-domination core results from the fact that $k$ may not be the size of a
minimum dominating set, if $k$ is minimum we can find a linear size core.
Explicit bounds on the degree of the polynomial can be derived from [25, 27],
but we refrain from doing so to not disturb the flow of ideas.

The following lemma is immediate from the definition of a $k$-domination core.

######  Lemma 4.3.

If $D$ is a dominating set of size at most $k$ that contains a vertex set
$W\subset D$ such that $N[D]\cap C=N[D\setminus W]\cap C=C$, then $D\setminus
W$ is also a dominating set.

######  Definition 4.4.

Let $G$ be a graph and let $A\subseteq V(G)$. The _projection_ of a vertex
$v\in V(G)\setminus A$ into $A$ is the set $N(v)\cap A$. If two vertices $u,v$
have the same projection into $A$ we write $u\sim_{A}v$.

Obviously, the relation $\sim_{A}$ is an equivalence relation. The following
lemma is folklore, one possible reference is [9].

######  Lemma 4.5.

Let $G$ be a planar graph and let $A\subseteq V(G)$. Then there exists a
constant $c$ such that there are at most $c\cdot|A|$ different projections to
$A$, that is, the equivalence relation $\sim_{A}$ has at most $c\cdot|A|$
equivalence classes.

###  4.2. Reduction rules

Let $G$ be an embedded planar graph. We say that a vertex $v$ _touches_ a face
$f$ if $v$ is drawn inside $f$ or belongs to the boundary of $f$ or is
adjacent to a vertex on the boundary of $f$. We fix two connected dominating
sets $S$ and $T$ of size at most $k$. We will present a sequence of lemmas,
each of which implies a polynomial-time computable reduction rule that allows
to transform $G$ to a planar graph $G^{\prime}$ that inherits its embedding
from $G$, with $S,T\subseteq V(G^{\prime})$ and that has the same
reconfiguration properties with respect to $S$ and $T$ as $G$. To not overload
notation, after stating a lemma with a reduction rule, we assume that the
reduction rule is applied until this is no longer possible and call the
resulting graph again $G$. We also assume that whenever one or more of our
reduction rules are applicable, then they are applied in the order presented.
We will guarantee that $S$ and $T$ will always be connected dominating sets of
size at most $k$, hence, after each application of a reduction rule, we can
recompute a $k$-domination core in polynomial time. This yields only
polynomial overhead and allows us to assume that we always have marked a
$k$-domination core $C$ of size at most $p\coloneqq p(k)$ as described in
Lemma 4.2. This allows us to state the lemmas as if $G$ and $C$ were fixed.
Without loss of generality we assume that $C$ contains $S$ and $T$.

######  Definition 4.6.

A set $W\subseteq V(G)\setminus C$ of vertices is _irrelevant_ if there is a
reconfiguration sequence from $S$ to $T$ in $G$ if and only if there is a
reconfiguration sequence from $S$ to $T$ in $G-W$.

######  Definition 4.7.

Let $u,v\in V(G)$ be non-equal vertices. We call the set
$D(u,v)\coloneqq(N(u)\cap N(v))\cup\\{u,v\\}$ the _diamond_ induced by $u$ and
$v$. We call $|N(u)\cap N(v)|$ the _thickness_ of $D(u,v)$.

######  Lemma 4.8.

If $G$ contains a diamond $D(u,v)$ of thickness greater than $3k$, then at
least one of $u$ or $v$ must be pebbled in every reconfiguration sequence from
$S$ to $T$.

######  Proof 4.9.

Assume $S=S_{1},\ldots,S_{t}=T$ is a reconfiguration sequence from $S$ to $T$
and $u,v\not\in S_{i}$ for some $1\leq i\leq t$. Then every $s\in S_{i}$ can
dominate at most $3$ vertices of $N(u)\cap N(v)$: otherwise $u,v,s$ together
with $3$ vertices of $N(u)\cap N(v)$ different from $u,v$ and $s$ would form a
complete bipartite graph $K_{3,3}$.

$\bullet$$u$$\bullet$$v$$s$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$
Figure 7. A vertex $s\in S_{i}$ can dominate at most $3$ vertices of $N(u)\cap
N(v)$.

######  Lemma 4.10.

If $G$ contains a diamond $D(u,v)$ of thickness greater than $3k$, then we can
remove all internal edges in $D(u,v)$, i.e., edges with both endpoints in
$N(u)\cap N(v)$.

######  Proof 4.11.

Assume $S=S_{1},\ldots,S_{t}=T$ is a reconfiguration sequence from $S$ to $T$.
According to Lemma 4.8, for each $1\leq i\leq t$,
$S_{i}\cap\\{u,v\\}\neq\emptyset$. Hence all vertices of $N(u)\cap N(v)$ are
always dominated by at least one of $u$ or $v$, say by $u$. Moreover, pebbling
more than one vertex of $N(u)\cap N(v)$ will never create connectivity via
internal edges that is not already there via edges incident on $u$. In other
words, for any connected dominating set $S$ of $G$, if an edge $yz$ is used
for connectivity, where $y,z\in N(u)\cap N(v)$, then this edge can be replaced
by either the path $yuz$ or the path $yvz$ (depending on which of $u$ or $v$
is in $S$).

As described earlier, we now apply the reduction rule of Lemma 4.10 until this
is no longer possible, and name the resulting graph again $G$. As we did not
make use of the properties of a $k$-domination core in the lemma, it is
sufficient to recompute a $k$-domination core $C$ after applying the reduction
rule exhaustively. In the following it may be necessary to recompute it after
each application of a reduction rule. We will not mention these steps
explicitly anymore in the following.

######  Lemma 4.12 ($\star$).

If $G$ contains a diamond $D(u,v)$ of thickness greater than $4|C|+3k+1$ then
$G$ contains an irrelevant vertex.

We may in the following assume that $G$ does not contain diamonds of thickness
greater than $4|C|+3k+1$.

######  Corollary 4.13.

If a vertex $v\in V(G)$ has degree greater than $(4|C|+3k+1)\cdot k$, then the
token on $v$ is never lifted throughout a reconfiguration sequence.

######  Proof 4.14.

Assume $S=S_{1},\ldots,S_{t}=T$ is a reconfiguration sequence from $S$ to $T$
in $G$ and assume there is $S_{i}$ with $v\not\in S_{i}$. The dominating set
$S_{i}$ has at most $k$ vertices and must dominate $N(v)$. Hence, there must
be one vertex $u\in S_{i}$ that dominates at least a $1/k$ fraction of $N(v)$,
which is larger than $4|C|+3k+1$. Then there is a diamond $D(u,v)$ of
thickness greater than $4|C|+3k+1$, which does not exist after application of
the reduction rule of Lemma 4.12.

According to Corollary 4.13, the only vertices that can have high degree after
applying the reduction rules are vertices that are never lifted throughout a
reconfiguration sequence. This gives rise to another reduction rule that is
similar to the rule of Lemma 4.10.

######  Lemma 4.15.

Assume $v$ is a vertex of degree greater than $(4|C|+3k+1)\cdot k$. Then we
may remove all edges with both endpoints in $N(v)$.

######  Proof 4.16.

Let $G^{\prime}$ be the graph obtained from $G$ by removing all edges with
both endpoints in $N(v)$. We claim that reconfiguration between $S$ and $T$ is
possible in $G$ if and only if it is possible in $G^{\prime}$. The fact that
$S$ and $T$ are in fact connected dominating sets in $G^{\prime}$ is implied
by the argument below.

Assume $S=S_{1},\ldots,S_{t}=T$ is a reconfiguration sequence from $S$ to $T$
in $G$. We claim that the same sequence is a reconfiguration sequence in
$G^{\prime}$. According to Corollary 4.13, $v\in S_{i}$ for all $1\leq i\leq
t$. This implies that $S_{i}$ is connected in $G^{\prime}$ for all $1\leq
i\leq t$, as all $x,y\in S_{i}$ that are no longer connected by an edge in
$G^{\prime}$ but were connected in $G$ are connected via a path of length $2$
using the vertex $v$. It is also easy to see that $S_{i}$ is a dominating set
in $G^{\prime}$, as all vertices that are no longer dominated by $s\in S_{i}$
in $G$ are still dominated by $v$. Observe that this in particular implies
that $S$ and $T$ are connected dominating sets in $G^{\prime}$. Vice versa, if
$S=S_{1},\ldots,S_{t}=T$ is a reconfiguration sequence from $S$ to $T$ in
$G^{\prime}$, this is trivially also a reconfiguration sequence in $G$.

The following reduction rule is obvious.

######  Lemma 4.17.

If a vertex $v$ has more than $k+1$ pendant neighbours, i.e., neighbors of
degree exactly one, then it suffices to retain exactly $k+1$ of them in the
graph.

######  Lemma 4.18.

There are at most $c|C|\cdot(4|C|+3k+1)$ vertices of $V(G)\setminus C$ that
have $2$ neighbours in $C$, where $c$ is the constant of Lemma 4.5.

######  Proof 4.19.

According to Lemma 4.5 there are at most $c|C|$ different projections to $C$.
Each projection class that has at least $3$ representatives has size at most
$2$, as otherwise we would find a $K_{3,3}$ as a subgraph, contradicting the
planarity of $G$. Consider a class with a projection of size $2$ into $C$.
Denote these two vertices of $C$ by $u$ and $v$. If this class has more than
$4|C|+3k+1$ representatives, then $D(u,v)$ is a diamond of thickness greater
than $4|C|+3k+1$, which cannot not exist after exhaustive application of the
reduction rule of Lemma 4.12.

We now come to the description of our final reduction rule. Let $D$ denote the
set of vertices containing both $C$ and all vertices of $V(G)\setminus C$
having at least two neighbors in $C$. In other words, $D$ contains all those
vertices in $V(G)\setminus C$ that have exactly one neighbor in $C$. According
to Lemma 4.18 at most $c|C|\cdot(4|C|+3k+1)$ vertices have two neighbors in
$C$, hence $|D|\leq c|C|\cdot(4|C|+3k+1)+|C|\eqqcolon p$.

######  Lemma 4.20 ($\star$).

Assume there are two vertices $u$ and $v$ with degree greater than
$4p+(4|C|+3k+1)\cdot k+1$. Let $\mathcal{P}$ be a maximum set of vertex-
disjoint paths of length at least $2$ that run between $u$ and $v$ using only
vertices in $V(G)\setminus D$. If $|\mathcal{P}|>4p+(4|C|+3k+1)\cdot k+1$,
then there is $G^{\prime}$ such that the instances $(G,S,T,k)$ and
$(G^{\prime},S,T,k)$ are equivalent, $G^{\prime}$ is planar, and
$|V(G^{\prime})|<|V(G)|$.

We are ready to state the final result.

######  Theorem 4.21.

CDS-R under TAR parameterized by $k$ admits a polynomial kernel on planar
graphs.

######  Proof 4.22.

Our kernelization algorithm starts by computing (in polynomial time) a
$k$-domination core $C$ of size at most $p\coloneqq p(k)$ as described in
Lemma 4.2. Without loss of generality we assume that $C$ contains $S$ and $T$.
After each application of a reduction rule, we recompute the core, giving a
polynomial blow-up of the running time. We are left to prove that each
reduction rule can be implemented in polynomial time and that we end up with a
polynomial number of vertices.

It is clear that the reduction rules of Lemma 4.12, Lemma 4.15 and Lemma 4.17
can easily be implemented in polynomial time. The reduction rule of Lemma 4.20
is slightly more involved, however, we can use a standard maximum-flow
algorithm to compute in polynomial time a maximum set of vertex-disjoint paths
in a subgraph of $G$.

It remains to bound the size of $G$. Recall that we call $D$ the set of all
vertices $C$ and of all vertices of $V(G)\setminus C$ that have at least $2$
neighbors in $C$. It follows from Lemma 4.18 that $D$ has size at most
$c|C|\cdot(4|C|+3k+1)+|C|\eqqcolon p$, where $c$ is the constant of Lemma 4.5.
We are left to bound the number of vertices in $V(G)\setminus C$ having
exactly one neighbour in $C$ (recall that each vertex in $V(G)\setminus C$ has
at least one neighbour in $S\cup T\subseteq C$).

Let $p^{\prime}=(4p+(4|C|+3k+1)\cdot k+1)\cdot(4|C|+3k+1)\cdot k+k+1$, which
is still a polynomial in $k$. Towards a contradiction, assume that there
exists an equivalence class $Q$ in $\sim_{C}$ with a projection of size one
containing more than $p^{\prime}$ vertices. Let $u\in C$ denote the projection
of the aforementioned class. Due to Lemma 4.17, we know that at most $k+1$ of
the vertices in $Q$ are pendant, i.e., adjacent to only $u$ in $G$. Since we
cannot apply the reduction rule of Lemma 4.15 any more, we know that there are
no edges with both endpoints in $Q$. Hence, all but $k+1$ vertices of $Q$ must
be adjacent to at least one other vertex in $V(G)\setminus C$. Let
$R=N_{G}(Q)\setminus\\{u\\}$ denote this set of neighbours. No vertex in $R$
can be adjacent to more than $4|C|+3k+1$ vertices of $Q$, as we cannot apply
the reduction rule of Lemma 4.12. The vertices of $R$ must be dominated by
$S$, and cannot be dominated by $u$, as otherwise two neighbours of $u$ would
be connected. Hence, there is $v\in S$ different from $u$ that dominates at
least a $1/k$ fraction of $R$. This implies the existence of at least
$4p+(4|C|+3k+1)\cdot k+1$ vertex-disjoint paths of length at least $2$ that
run between $u$ and $v$. But in this case, the reduction rule of Lemma 4.20 is
applicable. Therefore, we conclude that $Q$ cannot exist, obtaining a bound on
the size of all equivalence classes of $\sim_{C}$, as needed.

## References

  * [1] Luis Cereceda, Jan van den Heuvel, and Matthew Johnson.  Connectedness of the graph of vertex-colourings.  Discrete Mathematics, 308(56):913–919, 2008.
  * [2] Bruno Courcelle, Johann A Makowsky, and Udi Rotics.  Linear time solvable optimization problems on graphs of bounded clique-width.  Theory of Computing Systems, 33(2):125–150, 2000.
  * [3] Anuj Dawar and Stephan Kreutzer.  Domination problems in nowhere-dense classes.  In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2009, pages 157–168, 2009\.
  * [4] Erik D. Demaine and Joseph O’Rourke.  Geometric folding algorithms - linkages, origami, polyhedra.  Cambridge University Press, 2007.
  * [5] Pål Grønås Drange, Markus Sortland Dregi, Fedor V. Fomin, Stephan Kreutzer, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Felix Reidl, Fernando Sánchez Villaamil, Saket Saurabh, Sebastian Siebertz, and Somnath Sikdar.  Kernelization and sparseness: the case of dominating set.  In 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016, pages 31:1–31:14, 2016.
  * [6] Eduard Eiben, Mithilesh Kumar, Amer E. Mouawad, Fahad Panolan, and Sebastian Siebertz.  Lossy kernels for connected dominating set on sparse graphs.  In 35th Symposium on Theoretical Aspects of Computer Science, STACS 2018, pages 29:1–29:15, 2018.
  * [7] Kord Eickmeyer, Archontia C. Giannopoulou, Stephan Kreutzer, O-joung Kwon, Michal Pilipczuk, Roman Rabinovich, and Sebastian Siebertz.  Neighborhood complexity and kernelization for nowhere dense classes of graphs.  In 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, pages 63:1–63:14, 2017.
  * [8] Grzegorz Fabianski, Michal Pilipczuk, Sebastian Siebertz, and Szymon Toruńczyk.  Progressive algorithms for domination and independence.  In 36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019, pages 27:1–27:16, 2019.
  * [9] Jakub Gajarský, Petr Hlinený, Jan Obdrzálek, Sebastian Ordyniak, Felix Reidl, Peter Rossmanith, Fernando Sánchez Villaamil, and Somnath Sikdar.  Kernelization using structural parameters on sparse graph classes.  J. Comput. Syst. Sci., 84:219–242, 2017.
  * [10] Sevag Gharibian and Jamie Sikora.  Ground state connectivity of local hamiltonians.  In Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming, ICALP 2015, pages 617–628, 2015.
  * [11] Parikshit Gopalan, Phokion G. Kolaitis, Elitza N. Maneva, and Christos H. Papadimitriou.  The connectivity of Boolean satisfiability: computational and structural dichotomies.  SIAM Journal on Computing, 38(6):2330–2355, 2009.
  * [12] Martin Grohe, Stephan Kreutzer, and Sebastian Siebertz.  Deciding first-order properties of nowhere dense graphs.  Journal of the ACM (JACM), 64(3):17, 2017.
  * [13] Ruth Haas and Karen Seyffarth.  The k-dominating graph.  Graphs and Combinatorics, 30(3):609–617, 2014.
  * [14] Takehiro Ito, Erik D. Demaine, Nicholas J. A. Harvey, Christos H. Papadimitriou, Martha Sideri, Ryuhei Uehara, and Yushi Uno.  On the complexity of reconfiguration problems.  Theoretical Computer Science, 412(12-14):1054–1065, 2011.
  * [15] Takehiro Ito, Marcin Kamiński, and Erik D. Demaine.  Reconfiguration of list edge-colorings in a graph.  Discrete Applied Mathematics, 160(15):2199–2207, 2012.
  * [16] Wm. Woolsey Johnson and William E. Story.  Notes on the “15” puzzle.  American Journal of Mathematics, 2(4):397–404, 1879.
  * [17] Iyad A. Kanj and Ge Xia.  Flip distance is in FPT time o(n+ k * c^k).  In 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015, pages 500–512, 2015.
  * [18] Graham Kendall, Andrew J. Parkes, and Kristian Spoerer.  A survey of NP-complete puzzles.  ICGA Journal, pages 13–34, 2008.
  * [19] Stephan Kreutzer, Roman Rabinovich, and Sebastian Siebertz.  Polynomial kernels and wideness properties of nowhere dense graph classes.  In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, pages 1533–1545, 2017.
  * [20] Daniel Lokshtanov, Amer E. Mouawad, Fahad Panolan, M. S. Ramanujan, and Saket Saurabh.  Reconfiguration on sparse graphs.  J. Comput. Syst. Sci., 95:122–131, 2018.
  * [21] Anna Lubiw and Vinayak Pathak.  Flip distance between two triangulations of a point set is NP-complete.  Comput. Geom., 49:17–23, 2015.
  * [22] Amer E. Mouawad.  On reconfiguration problems: Structure and tractability.  2015\.
  * [23] Amer E. Mouawad, Naomi Nishimura, Vinayak Pathak, and Venkatesh Raman.  Shortest reconfiguration paths in the solution space of boolean formulas.  In Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I, pages 985–996, 2015.
  * [24] Amer E. Mouawad, Naomi Nishimura, Venkatesh Raman, Narges Simjour, and Akira Suzuki.  On the parameterized complexity of reconfiguration problems.  Algorithmica, 78(1):274–297, 2017.
  * [25] Wojciech Nadara, Marcin Pilipczuk, Roman Rabinovich, Felix Reidl, and Sebastian Siebertz.  Empirical evaluation of approximation algorithms for generalized graph coloring and uniform quasi-wideness.  In 17th International Symposium on Experimental Algorithms, SEA 2018, pages 14:1–14:16, 2018.
  * [26] Naomi Nishimura.  Introduction to reconfiguration.  Algorithms, 11(4):52, 2018.
  * [27] Michał Pilipczuk, Sebastian Siebertz, and Szymon Toruńczyk.  On the number of types in sparse graphs.  In Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, pages 799–808. ACM, 2018.
  * [28] Sebastian Siebertz.  Reconfiguration on nowhere dense graph classes.  Electr. J. Comb., 25(3):P3.24, 2018.
  * [29] Akira Suzuki, Amer E. Mouawad, and Naomi Nishimura.  Reconfiguration of dominating sets.  Journal of Combinatorial Optimization, 32(4):1182–1195, 2016.
  * [30] Jan van den Heuvel.  The complexity of change.  Surveys in combinatorics, 409(2013):127–160, 2013.

##  Appendix A Details omitted from Section 3

We need the following lemma to prove Lemma 3.4.

######  Lemma A.1.

Let $T_{1},T_{2}$ be two trees on vertex set $\\{1,\ldots,k\\}$ and let
$f_{1},\ldots f_{k-1}$ be an ordering of the edges in $T_{2}$. Then, in
polynomial time, we can find an ordering $e_{1},\ldots,e_{k-1}$ of the edges
in $T_{1}$ such that the following holds. In the sequence of graphs
$T_{0}^{\prime},T_{1}^{\prime},\ldots,T_{k-1}^{\prime}$ on vertex set
$\\{1,\ldots,k\\}$, where for each $0\leq i\leq k-2$,
$T_{i+1}^{\prime}=T_{i}^{\prime}+f_{i}-e_{i}$ and $T_{0}^{\prime}=T_{1}$, we
have that $T_{i}^{\prime}$ is a tree, for all $i\in[k-1]$, and
$T_{k-1}^{\prime}=T_{2}$.

######  Proof A.2.

We proceed by induction on $\ell=|E(T_{1})\setminus E(T_{2})|$. In the base
case, we have $\ell=0$ and $E(T_{1})=E(T_{2})$. In this case $f_{1},\ldots
f_{k-1}$ is also the required ordering of the edges in $T_{1}$ (note that the
sequence of graphs consists of only $T_{1}=T_{2}$ in this case).

Now consider the induction step, $\ell>1$. Let $j$ be the first index in
$\\{1,\ldots,k-1\\}$ such that $f_{j}\notin E(T_{1})$. We add $f_{j}$ to
$T_{1}$ and this creates a cycle in $T_{1}$. Hence, there exists an edge
$e_{j}\in E(T_{1})\setminus E(T_{2})$ whose removal results in a tree. That
is, $T_{1}^{\prime}=T_{1}+f_{j}-e_{j}$ is a tree. Notice that
$|E(T_{1}^{\prime})\setminus E(T_{2})|=\ell-1$. By the induction hypothesis,
there is a sequence $g_{1},\ldots,g_{k-1}$ of edges in $E(T_{1}^{\prime})$
such that for the sequence of graphs
$T_{1}^{\prime}=T_{0}^{\prime\prime},T_{1}^{\prime\prime},\ldots,T_{k-1}^{\prime\prime}$
on vertex set $\\{1,\ldots,k\\}$, we have
$T_{i+1}^{\prime\prime}=T_{i}^{\prime\prime}+f_{i}-g_{i}$, each
$T_{i}^{\prime\prime}$ is a tree, and $T_{2}=T_{k-1}^{\prime\prime}$, $0\leq
i<k$. Since $j$ is the first index in $\\{1,\ldots,k-1\\}$ such that
$f_{j}\notin E(T_{1})$, $T_{1}^{\prime}=T_{1}+f_{j}-e_{j}$, and
$T_{0}^{\prime\prime},T_{1}^{\prime\prime},\ldots,T_{k-1}^{\prime\prime}$ are
trees, we have that $g_{i}=f_{i}$ for all $i<j$. Notice that $f_{j}\in
E(T_{1}^{\prime})$ and
$E(T_{1})=(E(T_{1}^{\prime})\setminus\\{f_{j}\\})\cup\\{e_{j}\\}$.

We claim that $e_{1},\ldots,e_{j-1},e_{j},e_{j+1},\ldots,e_{k-1}$, where
$e_{i}=g_{i}$ for all $i<j$, is the required sequence of edges in $T_{1}$. Let
$T_{0}^{\prime},T_{1}^{\prime},\ldots,T_{k-1}^{\prime}$ be the sequence where,
for each $0\leq i\leq k-2$, $T_{i+1}^{\prime}=T_{i}^{\prime}+f_{i}-e_{i}$ and
$T_{0}^{\prime}=T_{1}$. Since $g_{i}=f_{i}=e_{i}$ for all $i<j$, we have that
$T_{1}=T_{0}^{\prime}=T_{1}^{\prime}=\ldots=T_{j-1}^{\prime}$. Moreover,
$T_{j}^{\prime}=T_{1}+\\{f_{1},\ldots,f_{j}\\}-\\{e_{1},\ldots,e_{j}\\}=T_{1}+\\{f_{1},\ldots,f_{j}\\}-\\{g_{1},\ldots,g_{j}\\}=T_{j}^{\prime\prime}$
because $E(T_{1})=(E(T_{1}^{\prime})\setminus\\{f_{j}\\})\cup\\{e_{j}\\}$ and
$e_{i}=g_{i}$ for all $i<j$. Then, the sequence
$T_{j}^{\prime},\ldots,T^{\prime}_{k-1}$ is the same as the sequence
$T_{j}^{\prime\prime},\ldots,T^{\prime\prime}_{k-1}$. Therefore, the sequence
$e_{1},\ldots,e_{j-1},e_{j},e_{j+1},\ldots,e_{k-1}$ of edges in $T_{1}$
satisfies the conditions of the lemma.

### Proof of Lemma 3.3

######  Proof A.3.

We iteratively remove minimum degree vertices and show that we can always
remove a vertex of degree at most $4$ in each step.

  * •

Every subdivision vertex $w\in W(H^{i})$ for $1\leq i\leq k$ has degree at
most $4$; it has $4$ neighbors in $V(H^{i})\cup V(H^{i+1})$.

  * •

After removal of all subdivision vertices the degree of the remaining vertices
of each $H^{i}$ is at most one. That is, a vertex in $H^{(1,1)}$ may have a
neighbor in $\\{w_{2},\ldots,w_{k}\\}$.

  * •

After the removal of $V(H^{1})\cup\ldots V(H^{k})$, the degree of all vertices
except $v_{1}$ and $x_{k}$ is at most $2$.

  * •

Finally we remove $v_{1}$ and $x_{k}$.

### Proof of Lemma 3.4

######  Proof A.4.

We aim to shift the connected vertices of $Q_{s}$ through the subgraphs
$H^{1},\ldots,H^{k}$ (in that order) to maintain connectivity and eventually
shift to $Q_{t}$. For each $u_{i}\in V(G)$, $1\leq j\leq k$ and $1\leq r\leq
20k$, we use $u_{i}^{(j,r)}$ to denote the copy of $u_{i}$ in $H^{(j,r)}$.

Let $C=\\{u_{1},\ldots,u_{k}\\}$ be a $k$-colored clique in $G$ such that
$c(u_{i})=i$, for all $1\leq i\leq k$. To prove the lemma, we need to define a
reconfiguration sequence starting from $Q_{s}$ and ending at $Q_{t}$ such that
the cardinality of any solution in the sequence is at most $2k$. First we
define $k$ “colored” trees $\widehat{T}_{1},\ldots,\widehat{T}_{k}$ each on
$2k-1$ vertices, and then prove that there are reconfiguration sequences from
$Q_{s}$ to $V(\widehat{T}_{1})$, $V(\widehat{T}_{i})$ to
$V(\widehat{T}_{i+1})$ for all $1\leq i<k$, and $V(\widehat{T}_{k})$ to
$Q_{t}$.

We start by defining $\widehat{T}_{1},\ldots,\widehat{T}_{k}$. For each $1\leq
i\leq k$, $C_{i}=\\{u^{(i,1)}_{1},\ldots,u_{k}^{(i,1)}\\}$ and $S_{i}=\\{z\in
V(H^{(i,1)})\colon N_{H^{(i,1)}}(z)\cap C_{i}=2\\}$. That is, for each $1\leq
j\leq k$ and $j\neq i$, $s_{u_{i}^{(i,1)}u_{j}^{(i,1)}}\in S_{i}$ (the
subdivision vertex on the edge $u_{i}^{(i,1)}u_{j}^{(i,1)}$ is in $S_{i}$),
and $|S_{i}|=k-1$. In other words, $C_{i}$ contains the copies of the vertices
of the clique $C$ in $H^{(i,1)}$ and $S_{i}$ contains subdivision vertices
corresponding to $k-1$ edges in the clique incident on the $i$th colored
vertex of the clique, such that $H[C_{i}\cup S_{i}]$ is a tree. Now, define
$\widehat{T}_{i}=H[C_{i}\cup S_{i}]$. It is easy to verify that
$\widehat{c}(C_{i}\cup S_{i})=\\{1,\ldots,k+1\\}$ and hence $C_{i}\cup
S_{i}=V(\widehat{T}_{i})$ is a solution to the CCS instance
$(H,\widehat{c},2k)$. Let $T_{s}=H[Q_{s}]$ and $T_{t}=H[Q_{t}]$. Note that
$T_{s}$ and $T_{t}$ are trees on $2k-1$ vertices each.

Case 1: Reconfiguration from $Q_{s}$ to $V(\widehat{T}_{1})$. Informally, we
move to $\widehat{T}_{1}$ by adding a token on $u_{i}^{(1,1)}$ and then
removing tokens from $v_{i}$ for $i$ in the order $2,\ldots,k,1$ (for a total
of $2k$ token additions/removals). Finally, we move the tokens from
$\\{w_{2},\ldots,w_{k-1}\\}$ to $S_{1}$ in $2(k-1)$ steps. The length of the
reconfiguration sequence is $2k+2(k-1)=4k-2$.

Formally, we define $Z_{0}=Q_{s}$ and for each $1\leq j\leq k-1$,
$Z_{2j-1}=Z_{2j-2}\cup\\{u_{j+1}^{(1,1)}\\}$ and
$Z_{2j}=Z_{2j-1}\setminus\\{v_{j+1}\\}$. That is, for each $1\leq j\leq k-1$,

$\displaystyle Z_{2j-1}$ $\displaystyle=$
$\displaystyle\\{u_{2}^{(1,1)},\ldots,u^{(1,1)}_{j+1}\\}\cup\\{v_{j+1}\ldots,v_{k},v_{1}\\}\cup\\{w_{1},\ldots,w_{k-1}\\},\mbox{
and }$ $\displaystyle Z_{2j}$ $\displaystyle=$
$\displaystyle\\{u_{2}^{(1,1)},\ldots,u^{(1,1)}_{j+1}\\}\cup\\{v_{j+2}\ldots,v_{k},v_{1}\\}\cup\\{w_{1},\ldots,w_{k-1}\\}.$

Next, we define $Z_{2k-1}$ and $Z_{2k}$ as

$\displaystyle Z_{2k-1}$ $\displaystyle=$
$\displaystyle\\{u_{2}^{(1,1)},\ldots,u^{(1,1)}_{k},u_{1}^{(1,1)}\\}\cup\\{v_{1}\\}\cup\\{w_{1},\ldots,w_{k-1}\\},\mbox{
and }$ $\displaystyle Z_{2k}$ $\displaystyle=$
$\displaystyle\\{u_{2}^{(1,1)},\ldots,u^{(1,1)}_{k},u_{1}^{(1,1)}\\}\cup\\{w_{1},\ldots,w_{k-1}\\}.$

It is easy to verify that $Z_{1},\ldots Z_{2k}$ are solutions to the CCS
instance $(H,\widehat{c},2k)$. Thus, we now have a reconfiguration sequence
$Z_{0},Z_{1},\ldots,Z_{2k}$, where $Z_{0}=Q_{s}$.

Next, we explain how to get a reconfiguration sequence from $Z_{2k}$ to
$V(\widehat{T}_{1})$. Recall that $Z_{2k}=C_{1}\cup\\{w_{1},\ldots,w_{k-1}\\}$
and $V(\widehat{T}_{1})=C_{1}\cup S_{1}$. Let
$s_{j}=s_{u_{1}^{(1,1)}u_{j}^{(1,1)}}$, for all $2\leq j\leq k$. Notice that
$S_{1}=\\{s_{2},\ldots,s_{k}\\}$. To obtain a reconfiguration sequence from
$Z_{2k}$ to $V(\widehat{T}_{1})$, we add $s_{j}$ and then remove $w_{j}$ for
$j$ in the order $2,\ldots,k$. Since $w_{j}$ and $s_{j}$ connect the same two
vertices from $C_{1}$, this reconfiguration sequence will maintain
connectivity. Moreover, it is easy to verify that each set in the
reconfiguration sequence uses all the colors $\\{1,\ldots,k\\}$. Therefore,
there exists a reconfiguration sequence of length $4k-2$ from $Q_{s}$ to
$V(\widehat{T}_{1})$.

Case 2: Reconfiguration from $V(\widehat{T}_{i})$ to $V(\widehat{T}_{i+1})$.
First we define $20k$ trees $P_{1},\ldots P_{20k}$, each on $2k-1$ vertices
such that for all $1\leq r\leq 20k$, $(i)$ $V(P_{r})\subseteq V(H^{(i,r)})$,
and $(ii)$ $\widehat{T}_{i}=P_{1}$. Then we give a reconfiguration sequence
from $V(P_{r})$ to $V(P_{r+1})$ for all $r\in[20k-1]$ and a reconfiguration
sequence from $V(P_{20k})$ to $V(\widehat{T}_{i+1})$.

Recall that $C=\\{u_{1},\ldots,u_{k}\\}$ is a $k$-colored clique in $G$ such
that $c(u_{i})=i$ for all $1\leq i\leq k$. For each $1\leq r\leq 20k$, let
$C_{i}^{r}=\\{u^{(i,r)}_{1},\ldots,u_{k}^{(i,r)}\\}$ and $S_{i}^{r}=\\{z\in
V(H^{(i,r)})\colon N_{H^{(i,r)}}(z)\cap C_{i}^{r}=2\\}$. That is, for each
$1\leq j\leq k$ and $j\neq i$, $s_{u_{i}^{(i,r)}u_{j}^{(i,r)}}\in S_{i}^{r}$
(i.e, the subdivision vertex on the edge $u_{i}^{(i,r)}u_{j}^{(i,r)}$ is in
$S_{i}^{r}$) and $|S_{i}^{r}|=k-1$. Let $P_{r}=H[C_{i}^{r}\cup S^{r}_{i}]$.
Notice that for all $r\in[20k]$, $P_{r}$ is a tree on $2k-1$ vertices.
Moreover, for each $1\leq r\leq 20k$, $V(P_{r})$ is a solution to the CCS
instance $(H,\widehat{c},2k)$.

Case 2(a): Reconfiguration from $V(P_{r})$ to $V(P_{r+1})$. By arguments
similar to those given for Case $1$, one can prove that there is a
reconfiguration sequence of length $4k-2$ from $V(P_{r})$ to $V(P_{r+1})$, for
all $1\leq r<20k$. For completeness we give the details here. Fix an integer
$1\leq r<20k$. Let $s_{j}=s_{u_{i}^{i,r}u_{j}^{(i,r)}}$ and
$s^{\prime}_{j}=s_{u_{i}^{(i,r+1)}u_{j}^{(i,r+1)}}$ for all
$j\in\\{1,\ldots,k\\}\setminus\\{i\\}$. Notice that $S_{i}^{r}=\\{s_{j}\colon
j\in\\{1,\ldots,k\\}\setminus\\{i\\}\\}$ and
$S_{i}^{r+1}=\\{s^{\prime}_{j}\colon j\in\\{1,\ldots,k\\}\setminus\\{i\\}\\}$.
Now we define $Z_{0}=V(P_{r})=C_{i}^{r}\cup S_{i}^{r}$ and for each $1\leq
j\leq i-1$, $Z_{2j-1}=Z_{2j-2}\cup\\{u_{j}^{(i,r+1)}\\}$ and
$Z_{2j}=Z_{2j-1}\setminus\\{u_{j}^{(1,r)}\\}$. That is, for each $1\leq j\leq
i-1$,

$\displaystyle Z_{2j-1}$ $\displaystyle=$
$\displaystyle\\{u_{1}^{(i,r+1)},\ldots,u^{(i,r+1)}_{j}\\}\cup\\{u_{j}^{(i,r)}\ldots,u_{k}^{(i,r)}\\}\cup
S_{i}^{r},\mbox{ and }$ $\displaystyle Z_{2j}$ $\displaystyle=$
$\displaystyle\\{u_{1}^{(1,1)},\ldots,u^{(1,1)}_{j}\\}\cup\\{u_{j+1}^{(i,r)}\ldots,u_{k}^{(i,r)}\\}\cup
S_{i}^{r}.$

For each $i\leq j\leq k-1$, $Z_{2j-1}=Z_{2j-2}\cup\\{u_{j+1}^{(i,r+1)}\\}$ and
$Z_{2j}=Z_{2j-1}\setminus\\{u_{j+1}^{(1,r)}\\}$. That is, for each $i\leq
j\leq k-1$,

$\displaystyle Z_{2j-1}$ $\displaystyle=$
$\displaystyle\\{u_{1}^{(i,r+1)},\ldots,u^{(i,r+1)}_{i-1},u^{(i,r+1)}_{i+1},\ldots,u^{(i,r+1)}_{j+1}\\}\cup\\{u_{j+1}^{(i,r)}\ldots,u_{k}^{(i,r)},u_{i}^{(i,r)}\\}\cup
S_{i}^{r},\mbox{ and }$ $\displaystyle Z_{2j}$ $\displaystyle=$
$\displaystyle\\{u_{1}^{(i,r+1)},\ldots,u^{(i,r+1)}_{i-1},u^{(i,r+1)}_{i+1},\ldots,u^{(i,r+1)}_{j+1}\\}\cup\\{u_{j+2}^{(i,r)}\ldots,u_{k}^{(i,r)},u_{i}^{(i,r)}\\}\cup
S_{i}^{r}.$

Next, we define $Z_{2k-1}$ and $Z_{2k}$ as

$\displaystyle Z_{2k-1}$ $\displaystyle=$
$\displaystyle\\{u_{1}^{(i,r+1)},\ldots,u^{(i,r+1)}_{k}\\}\cup\\{u_{i}^{(i,r)}\\}\cup
S_{i}^{r},\mbox{ and }$ $\displaystyle Z_{2k}$ $\displaystyle=$
$\displaystyle\\{u_{1}^{(i,r+1)},\ldots,u^{(i,r+1)}_{k}\\}\cup S_{i}^{r}.$

Next, for each $1\leq j\leq k-1$, let
$Z_{2k+2j-1}=Z_{2k+2j-2}\cup\\{s_{j}^{\prime}\\}$ and
$Z_{2k+2j}=Z_{2k+2j-1}\setminus\\{s_{j}\\}$. It is easy to verify that
$Z_{1},\ldots Z_{4k-2}$ are solutions to the CCS instance $(H,\widehat{c},2k)$
and $Z_{0},\ldots,Z_{4k-2}$ is a reconfiguration sequence where
$Z_{0}=V(P_{r})$ and $Z_{4k-2}=V(P_{r+1})$.

Case 2(b): Reconfiguration from $V(P_{20k})$ to $V(\widehat{T}_{i+1})$. Next,
we explain how to get a reconfiguration sequence from $V(P_{20k})$ to
$V(\widehat{T}_{i+1})$ using Lemma A.1. Recall that
$C_{i}^{20k}=\\{u^{(i,20k)}_{1},\ldots,u_{k}^{(i,20k)}\\}$ and
$S_{i}^{20k}=\\{z\in V(H^{(i,20k)})\colon N_{H^{(i,20k)}}(z)\cap
C_{i}^{20k}=2\\}$. Let $C_{i+1}=\\{u^{(i+1,1}_{1},\ldots,u_{k}^{(i+1,1)}\\}$
and $S_{i+1}=\\{z\in V(H^{(i+1,1)})\colon N_{H^{(i+1,1)}}(z)\cap
C_{i+1}=2\\}$. For ease of presentation, let
$s_{j}=s_{u_{i}^{(i,20k)}u_{j}^{(i,20k)}}$ for all
$j\in\\{1,\ldots,k\\}\setminus\\{i\\}$. Also, let
$s_{j}^{\prime}=s_{u_{i}^{(i+1,1)}u_{j}^{(i+1,1)}}$ for all
$j\in\\{1,\ldots,k\\}\setminus\\{i+1\\}$. That is, $S_{i}^{20k}=\\{s_{j}\colon
j\in\\{1,\ldots,k\\}\setminus\\{i\\}\\}$ and $S_{i+1}=\\{s^{\prime}_{j}\colon
j\in\\{1,\ldots,k\\}\setminus\\{i+1\\}\\}$. Notice that
$V(P_{20k})=C_{i}^{20k}\cup S_{i}^{20k}$ and $V(\widehat{T}_{i+1})=C_{i+1}\cup
S_{i+1}$.

Towards proving the required reconfiguration sequence, we give a
reconfiguration sequence from $C_{i}^{20k}\cup S_{i}^{20k}$ to $C_{i+1}\cup
S_{i}^{20k}$ and then from $C_{i+1}\cup S_{i}^{20k}$ to $C_{i+1}\cup S_{i+1}$.
The reconfiguration sequence from $C_{i}^{20k}\cup S_{i}^{20k}$ to
$C_{i+1}\cup S_{i}^{20k}$ is similar to the one in Case 1. That is, we add
$u_{j}^{(i+1,1)}$ and delete $u_{j}^{(i,20k)}$ for $j$ in the order
$1,\ldots,i-1,i+1,\ldots,k,i$. This gives a reconfiguration sequence from
$C_{i}^{20k}\cup S_{i}^{20k}$ to $Z=C_{i+1}\cup S_{i}^{20k}$ of length $2k$.

Next we explain how to get a reconfiguration sequence from $Z=C_{i+1}\cup
S_{i}^{20k}$ to $C_{i+1}\cup S_{i+1}$. Notice that $H[Z]$ and
$\widehat{T}_{i+1}=H[C_{i+1}\cup S_{i+1}]$ are trees. Recall that $T^{i}$ is
the star on $\\{1,\ldots,k\\}$ with vertex $i$ being the center, and $T^{i+1}$
is is the star on $\\{1,\ldots,k\\}$ with vertex $i$ being the center. Also,
$c_{j}$ is a coloring on $H^{j}$ which is inherited from the coloring $c$ of
$G$. That is, $c_{i+1}(u_{j}^{(i+1,1)})=j$ for all $1\leq j\leq k$. Then,
$H[Z]=K[C_{i+1}]\upharpoonright_{c_{i+1}}T^{i}$ and
$\widehat{T}_{i+1}=H[C_{i+1}\cup
S_{i+1}]=K[C_{i+1}]\upharpoonright_{c_{i+1}}T^{i+1}$.

Let $e_{1}^{i+1},\ldots,e_{k-1}^{i+1}$ be an arbitrary ordering of the the
edges in $T^{i+1}$. By Lemma A.1, we have a sequence
$e_{1}^{i},\ldots,e_{k-1}^{i}$ of edges in $T^{i}$ such that for the sequence
$T^{i}_{0},T^{i}_{1},\ldots,T^{i}_{k-1}$ on vertex set $\\{1,\ldots,k\\}$,
where for each $0\leq j\leq k-2$,
$T^{i}_{j+1}=T_{j}^{i}+e_{j}^{i+1}-e_{j}^{i}$ and $T^{i}_{0}=T^{i}$, the
following holds.

  * (i)

$T_{j}^{i}$ is a tree for all $0\leq j\leq k-1$, and

  * (ii)

$T^{i}_{k-1}=T^{i+1}$.

This implies that, from the sequences $e_{1}^{i},\ldots,e_{k-1}^{i}$ and
$e_{1}^{i+1},\ldots,e_{k-1}^{i+1}$, we get a sequence
$f_{1},\ldots,f_{k-1}^{\prime}$ on $S_{i}^{20k}$ and a sequence
$f^{\prime}_{1},\ldots,f^{\prime}_{k-1}$ on $S_{i+1}$ such that the for the
sequence $L_{0},\ldots,L_{2(k-1)}$, where
$L_{0}=C_{i+1}\cup\\{f_{1},\ldots,f_{k-1}\\}$ and for all $1\leq j\leq k-1$
$L_{2j-1}=(L_{2j-2}\cup\\{f^{\prime}_{i}\\})$,
$L_{2j}=L_{2j-1}\setminus\\{f_{i}\\}$ the following holds.

  * (1)

$H[L_{i}]$ is connected for all $0\leq i\leq k-1$, and

  * (2)

$L_{k-1}=S_{i+1}\cup C_{i+1}$.

Here, conditions $(1)$ and $(2)$ follow from conditions $(i)$ and $(ii)$,
respectively. Moreover, $\widehat{c}(L_{i})=[k+1]$ for all $0\leq i\leq
2(k-1)$ and $L_{0}=Z$. Thus, $L_{0},\ldots,L_{2(k-1)}$ is a valid
reconfiguration sequence from $Z$ to $V(\widehat{T}_{i+1})$. Note that the
ordering on the edges implies an ordering by which we can move the subdivision
vertices from $S_{i}$ to $S_{i+1}$ without violating connectivity. This
implies that there is a reconfiguration sequence from $V(P_{20k})$ to
$V(\widehat{T}_{i+1})$, of length $4k-2$. Therefore, we have a reconfiguration
sequence from $V(\widehat{T}_{i})$ to $V(\widehat{T}_{i+1})$ of length
$\mathcal{O}(k^{2})$.

Case 3: Reconfiguration from $V(\widehat{T}_{k})$ to $V({T}_{t})$. The
arguments for this case are similar to those given in Case 1, we therefore
omit the details. By summing up the lengths of reconfiguration sequences, we
get that if $(G,c,k)$ is a yes-instance of Multicolored Clique then there is a
reconfiguration sequence from $Q_{s}$ to $Q_{t}$, of length
$\mathcal{O}(k^{3})$.

### Proof of Lemma 3.6

######  Proof A.5.

For each $1\leq i\leq k+1$, let $Q_{i}$ be the set of vertices colored by the
color $i$. That is, $Q_{i}=\widehat{c}^{-1}(i)$. First, we prove some
auxiliary claims. The proofs of the following two claims follow from the
construction of $H$ and the definition of $\widehat{c}$.

######  Claim 1.

(i) $Q_{1}\cup\ldots\cup Q_{k}$ is an independent set in $H$, and $(ii)$ every
vertex in $Q_{k+1}$ is connected to vertices of at most two distinct colors.

######  Claim 2.

Let $v,w\in V(H)\setminus(V(H^{0})\cup V(H^{k+1}))$ be two distinct vertices
such that $\widehat{c}(v)=\widehat{c}(w)$ and
$\widehat{c}(v)\in\\{1,\ldots,k\\}$. If $v$ and $w$ have a common neighbor in
$V(H)\setminus V(H^{0})$, then $v$ and $w$ are copies of same vertex $z\in
V(G)$.

######  Claim 3.

Let $Y\subseteq V(H)$ be a vertex subset such that
$\widehat{c}(Y)=\\{1,\ldots,k+1\\}$ and $H[Y]$ is connected. Then, $|Y|\geq
2k-1$.

######  Proof A.6.

Let $B=Y\setminus\widehat{c}^{-1}(k+1)=Y\cap(Q_{1}\cup\ldots\cup Q_{k})$.
Since $\widehat{c}(Y)=\\{1,\ldots,k+1\\}$, $|B|\geq k$ and by Claim 1$(i)$,
$B$ is an independent set in $H$. By Claim 1$(ii)$, each vertex in $Q_{i+1}$
is connected to vertices of at most two distinct colors. Thus, since $H[Y]$ is
connected, the claim follows.

Suppose $(H,\widehat{c},Q_{s},Q_{t},2k)$ is a yes-instance of CCS-R. Then,
there is a reconfiguration sequence $D_{1},\ldots,D_{\ell}$ for
$\ell\in{\mathbb{N}}$, where $D_{1}=Q_{s}$ and $D_{\ell}=Q_{t}$. Without loss
of generality, we assume that the sequence $D_{1},\ldots,D_{\ell}$ is a
minimal reconfiguration sequence. Then, by Claim 3, for each $i\in[\ell]$,
$2k-1\leq|D_{i}|\leq 2k$.

Moreover, since $|D_{1}|=|D_{\ell}|=2k-1$, we have that for each even $i$,
$D_{i}$ is obtained from $D_{i-1}$ by a token addition, and for each odd $i$,
$D_{i}$ is obtained from $D_{i-1}$ by a token removal. This also implies that
for each even $i$, $|D_{i}|=2k$, for each odd $i$, $|D_{i}|=2k-1$, and $\ell$
is odd.

######  Claim 4.

Let $i\in[\ell]$ and $|D_{i}|=2k-1$. Then, for all $1\leq j\leq k$,
$|D_{i}\cap Q_{j}|=1$, and $|D_{i}\cap Q_{k+1}|=k-1$. Moreover, each vertex in
$D_{i}\cap Q_{k+1}$ will be adjacent to exactly two vertices in $H[D_{i}]$ and
these vertices will be of different colors from $\\{1,\ldots,k\\}$.

######  Proof A.7.

By Claim 1, $Q_{1}\cup\ldots\cup Q_{k}$ is independent and every vertex of
$Q_{k+1}$ is adjacent to vertices of at most two different color classes.
Hence, we need at least $k-1$ vertices from $Q_{k+1}$ that make the
connections between the vertices of $D_{i}$ colored with $\\{1,\ldots,k\\}$.
The above statement along with the assumption $|D_{i}|=2k-1$ imply the claim.

######  Claim 5.

Let $i\in\\{2,\ldots\ell-1\\}$. Let $v\in D_{i}$ and $w\in D_{i+1}$ such that
$v,w\notin V(H^{0})\cup V(H^{k+1})$, at most one vertex in $\\{v,w\\}$ is in
$V(H^{(1,1)})$, and $\widehat{c}(v)=\widehat{c}(w)\in\\{1,\ldots,k\\}$. Then,
$v$ and $w$ are copies of the same vertex in $G$. Moreover, $v,w\in
V(H^{j})\cup V(H^{j+1})$ for some $j\in[k-1]$.

######  Proof A.8.

Suppose $v$ and $w$ are not copies of the same vertex $z\in V(G)$. We know
that $|D_{i}|=2k-1$ or $|D_{i}|=2k$.

Case 1: $|D_{i}|=2k-1$. Since $D_{i}$ is a solution, $D_{i}$ induces a
connected subgraph in $H$. By Claim 4, $|D_{i}\cap Q_{j}|=1$ for all
$j\in\\{1,\ldots,k\\}$ and $|D_{i}\cap Q_{k+1}|=k-1$. Also, by Claim 1, $(i)$
$Q_{1}\cup\ldots\cup Q_{k}$ is an independent set in $H$, and $(ii)$ every
vertex in $Q_{k+1}$ is connected to vertices of at most two distinct colors.
Statements $(i)$ and $(ii)$, and the fact that $|D_{i}|=2k-1$ imply that
$(iii)$ $H[D_{i}]$ is a tree and each vertex in $D_{i}\cap Q_{k+1}$ is
incident to exactly two vertices in $D_{i}$. Since $|D_{i+1}|=|D_{i}|+1$, in
reconfiguration step $i+1$, we add a vertex to obtain $D_{i+1}$. We know that
$v\in D_{i}$. Since, for any color $q\in[k]$, there is exactly one vertex in
$D_{i}$ of color $q$ (i.e., $|D_{i}\cap Q_{q}|=1$), we have that
$D_{i+1}=D_{i}\cup\\{w\\}$. Moreover, in step $i+2$, the vertex removed from
$D_{i+1}$ will be from $\\{v,w\\}$ and that vertex will be $v$ (because of the
minimality assumption of the length of the reconfiguration sequence). That is,
$D_{i+2}=(D_{i}\cup\\{w\\})\setminus\\{v\\}$. Notice that
$|D_{i}|=|D_{i+2}|=2k-1$. Let $b$ a vertex in $D_{i+2}$ which is adjacent to
$w$ in $H[D_{i+2}]$. Since $Q_{k+1}\cap D_{i}=Q_{k+1}\cap D_{i+2}$ and
$|D_{i}|=|D_{i+2}|=2k-1$, by Claim 1, the neighbors of $b$ in $H[D_{i}]$ and
$H[D_{i+2}]$ are of the same color. This implies that $b$ is adjacent to $v$
in $H[D_{i}]$. Thus, we proved that $\\{b,w\\},\\{b,v\\}\in E(H)$. If $b\in
V(H^{0})$, then $v,w\in V(H^{(1,1)})$ which is a contradiction to the
assumption. Otherwise, by Claim 2, we conclude that $v$ and $w$ are copies of
same vertex.

Case 2: $|D_{i}|=2k$.  In this case $D_{i+1}$ is obtained by removing a vertex
from $D_{i}$. Moreover, $i\geq 3$, because we have two vertices in $D_{i}$
from $V(H)\setminus D_{1}$. Since $|D_{i+1}|=2k-1$, because of Claim 4,
$D_{i+1}$ is obtained by removing the vertex $v$ from $D_{i}$. That is,
$D_{i+1}=D_{i}\setminus\\{v\\}$ and $v,w\in D_{i}$. Then, again by Claim 4,
there is $v^{\prime}\in\\{v,w\\}$ such that
$D_{i-1}\uplus\\{v^{\prime}\\}=D_{i}$. Let
$w^{\prime}=\\{v,w\\}\setminus\\{v^{\prime}\\}$. Since $i\geq 3$, we now apply
Case 1 with respect to $w^{\prime}\in D_{i-1}$ and $v^{\prime}\in D_{i}$ to
complete the proof.

######  Claim 6.

For any index $j\in\\{1,\ldots,k\\}$ and color $q\in\\{1,\ldots,k\\}$, there
exist an odd $i\in\\{3,\ldots,\ell\\}$ and $r\in\\{5k,\ldots,15k\\}$ such that
$D_{i}$ contains a vertex of color $q$ from $V(H^{j,r})$.

######  Proof A.9.

Without loss of generality, assume that $k\geq 2$. Moreover, for any odd
$i\in[\ell-2]$, there is a vertex common in $D_{i}$ and $D_{i+2}$ (since
$k\geq 2$). This implies that $H[D_{1}\cup D_{3}\ldots D_{\ell}]$ is a
connected subgraph of $H$. Notice that for any $j\in\\{1,\ldots,k\\}$ and
$r\in[20k]$, $V(H^{(j,r)})$ is a $(v_{1},x_{1})$-separator in $H$. Therefore,
since $H[D_{1}\cup D_{3}\ldots D_{\ell}]$ is connected and $v_{1},x_{1}\in
D_{1}\cup D_{\ell}$, $(i)$ for any $j\in[k]$ and $r\in[20k]$, there is an odd
$i\in[\ell]$ such that $D_{i}$ contains a vertex from $V(H^{(j,r)})$. Now fix
an index $j\in\\{1,\ldots,k\\}$ and a color $q\in\\{1,\ldots,k\\}$. By
statement $(i)$, there is an odd $i\in\\{1,\ldots,\ell\\}$ such that $D_{i}$
contains a vertex from $V(H^{(j,10k)})$. Since $H[D_{i}]$ is connected,
$|D_{i}|=2k-1$, $D_{i}\cap V(H^{(j,10k)})\neq\emptyset$, and any vertex in
$V(H)\setminus\bigcup_{r=5k}^{15k}V(H^{(j,r)})$ is at distance more that $5k$
(by the construction of $H$), we have that all the vertices in $D_{i}$ belong
to $\bigcup_{r=5k}^{15k}V(H^{(j,r)})$. Moreover, by Claim 4, $D_{i}$ contains
a vertex colored $q$ and that will also be present in
$\bigcup_{r=5k}^{15k}V(H^{(j,r)})$. This completes the proof of the claim.

######  Claim 7.

For any color $q\in\\{1,\ldots,k\\}$, the vertices of color $q$ from
$\bigcup_{i=2}^{k}V(H^{i})$ used in the reconfiguration sequence
$D_{1},\ldots,D_{\ell}$ are copies of the same vertex $z\in V(G)$. Moreover,
exactly one vertex from $V(H^{j})$ of color $q$ is used in the reconfiguration
for all $2\leq j\leq k$.

######  Proof A.10.

Fix a color $q\in\\{1,\ldots,k\\}$. By Claim 6, there are vertices of color
$q$ from $V(H^{j})$ for all $j$ is used in the reconfiguration sequence. By
Claim 5, all these vertices are copies of the same vertex $z\in V(G)$.

Now we define a $k$-size vertex subset $C\subseteq V(G)$ and prove that $C$ is
a clique in $G$. We let $C=\\{a_{i}\in V(G)\colon 1\leq i\leq k,c(a_{i})=i$,
and the copy of $a_{i}$ in $V(H^{2})$ is used in $D_{1},\ldots,D_{\ell}\\}$.
Because of Claim 7, we have that $|C|=k$ and $C$ contains a vertex of each
color in $c$. $C=\\{a_{1},\ldots,a_{k}\\}\subseteq V(G)$ and for each
$q\in[k]$, $c(a_{q})=q$. We now prove that $C$ is indeed a clique in $G$.
Towards that, we need to prove that for each $1\leq q<j\leq k$,
$\\{a_{q},a_{j}\\}\in E(G)$.

######  Claim 8.

Let $1\leq q<j\leq k$. Then, $\\{a_{q},a_{j}\\}\in E(G)$.

######  Proof A.11.

By Claim 6, we know that there exist an odd $i\in[\ell]$ and
$r\in\\{5k,\ldots,15k\\}$ such that $D_{i}$ contains a vertex of color $q$ in
$V(H^{(j,r)})$. Thus, by Claim 7, a copy of $a_{j}$ and a copy of $a_{q}$ are
present in $D_{i}$. Let $u_{j}$ and $u_{q}$ be the vertices in $D_{i}$ colored
with $j$ and $q$, respectively. By Claim 7, $u_{j}$ is a copy of $a_{j}$ and
$u_{q}$ is a copy of $a_{q}$. Any vertex $b$ in $V(H^{j})$ colored $k+1$ is
adjacent to vertices of exactly two colors, out of which one color is $j$.
Moreover, by the construction of $H$, $(a)$ if $b$ is adjacent to $x$ and $y$
in $V(H^{j})$, and $x$ and $y$ are copies of $x^{\prime}$ and $y^{\prime}$ in
$G$, respectively, then $\\{x^{\prime},y^{\prime}\\}\in E(G)$. We know that
$H[D_{i}]$ is connected, $|Q_{s}\cap D_{i}|=1$ for all $1\leq s\leq k$,
$D_{i}\setminus Q_{k+1}$ is an independent set in $H$, and each vertex in
$D_{i}$ colored with $k+1$ is adjacent to exactly two vertices in
$D_{i}\setminus Q_{k+1}$ with one of them being $u_{j}$ (see Claims 1 and 4).
This implies that there is common neighbor $b$ for $u_{q}$ and $u_{j}$ and
hence $\\{a_{q},a_{j}\\}\in E(G)$, by statement $(a)$ above. This completes
the proof of the claim.

This completes the proof of the lemma.

##  Appendix B Details omitted from Section 4

### Proof of Lemma 4.12

######  Proof B.1.

Let $H$ be the subgraph of $G$ induced by $D(u,v)$. We enumerate the vertices
of $N(u)\cap N(v)$ consecutively as $x_{1},\ldots,x_{t}$ for some
$t>4|C|+3k+1$. We let $X=\\{x_{1},\ldots,x_{t}\\}$. Note that since we have
$t$ vertex-disjoint paths between $u$ and $v$ in $H$, these paths define the
boundaries of $t$ faces in the plane embedding of $H$ (after applying the
reduction rule of Lemma 4.10, $H$ has all the edges $\\{u,x\\}$ and
$\\{v,x\\}$ for $x\in N(u)\cap N(v)$ and no other edges). Each vertex in
$C\setminus\\{u,v\\}$ can be adjacent in $H$ to at most two vertices in $X$,
say with $y$ and $z$, and these two vertices $y$ and $z$ can touch at most $3$
faces of $H$.

$\bullet$$u$$\bullet$$v$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$c_{1}$$\bullet$$c_{2}$$\bullet$$f$$g$$x_{1}$$x_{3}$$x_{2}$
Figure 8. Every vertex of $C\setminus\\{u,v\\}$ can touch at most $3$ faces of
$H$. In the figure we assume the vertices $c_{1}$ and $c_{2}$ are in
$C\setminus\\{u,v\\}$. The faces that are touched by $c_{1}$ or $c_{2}$ are
colored in blue. The uncolored faces $f$ and $g$ are not touched by vertices
of $C\setminus\\{u,v\\}$.

This leaves $|C|+3k+1>|C|+1$ faces of $H$ that are not touched by a vertex of
$C\setminus\\{u,v\\}$. By the pidgeonhole principle we can find $2$ adjacent
faces $f$ and $g$ of $H$ that are not touched by a vertex of
$C\setminus\\{u,v\\}$.

We let $x_{1}$ and $x_{2}$ denote the two vertices on the boundary of face $f$
different from $u$ and $v$ and we let $x_{2}$ and $x_{3}$ denote the two
vertices on the boundary of face $g$ different from $u$ and $v$. Recall that,
due to Lemma 4.10, we know that there are no edges between those three
vertices. Let $W$ denote the set of all vertices contained in the face of the
cycle $u,x_{1},v,x_{3},u$. In particular, $W$ contains $x_{2}$. We claim that
the vertices of $W$ can be removed from $G$ without changing the
reconfiguration properties of $G$, i.e., $W$ is a set of irrelevant vertices.
Let $G^{\prime}=G-W$. First observe that $W\cap(S\cup T)=\emptyset$, hence
$S,T\subseteq V(G^{\prime})$. We show that reconfiguration from $S$ to $T$ is
possible in $G$ if and only if reconfiguration from $S$ to $T$ is possible in
$G^{\prime}$.

Assume $S=S_{1},\ldots,S_{t}=T$ is a reconfiguration sequence from $S$ to $T$
in $G$. Let $S_{1}^{\prime},\ldots,S_{t}^{\prime}$, where for $1\leq i\leq t$,
$S_{i}^{\prime}\coloneqq S_{i}$ if $S_{i}$ does not contain a vertex of $W$
and $S_{i}^{\prime}\coloneqq(S_{i}\setminus W)\cup\\{x_{1}\\}$ otherwise. Note
that this modification leaves $S$ and $T$ unchanged, hence,
$S_{1}^{\prime}=S_{1}$ and $S_{t}^{\prime}=S_{t}$. We claim that
$S_{1}^{\prime},\ldots,S_{t}^{\prime}$ is a reconfiguration sequence from $S$
to $T$ in $G^{\prime}$.

######  Claim 9.

For $1\leq i\leq t$, $S_{i}^{\prime}$ is a dominating set of $G$, and hence
also of $G^{\prime}$.

######  Proof B.2.

No vertex of $W$ is adjacent to a vertex of $C\setminus\\{u,v\\}$ and $W\cap
C=\emptyset$ by construction. Hence, the only vertices of $C$ that are
possibly adjacent to a vertex of $W$ are the vertices $u$ and $v$. Whenever
$S_{i}$ contains a vertex of $W$, we have $x_{1}\in S_{i}^{\prime}$, which
dominates both $u$ and $v$. Hence, $S_{i}^{\prime}$ dominates at least the
vertices of $C$ that $S_{i}$ dominates. We use Lemma 4.3 to conclude that
$S_{i}^{\prime}$ is a dominating set of $G$.

######  Claim 10.

For $1\leq i\leq t$, $S_{i}^{\prime}$ is connected.

######  Proof B.3.

Let $s_{1},s_{2}\in S_{i}\setminus W$ and let $P$ be a shortest path between
$s_{1}$ and $s_{2}$ in $G[S_{i}]$. We have to show that there exists a path
between $s_{1}$ and $s_{2}$ in $G[S_{i}^{\prime}]$. If $P$ does not use a
vertex of $W$, then there is nothing to show. Hence, assume $P$ uses a vertex
of $W$. By definition of $W$, both $s_{1}$ and $s_{2}$ lie outside the face
$h$ of the cycle $u,x_{1},v,x_{3}$ that contains $x_{2}$. Hence, $P$ must
enter and leave the face $h$, and as $P$ is a shortest path, it must enter and
leave via opposite vertices, i.e., via $u$ and $v$, or via $x_{1}$ and $x_{3}$
(as all other pairs are linked by an edge and we could find a shorter path).
If $P$ contains $u$ and $v$, then we can replace the vertices of $W$ on $P$ by
$x_{1}$ and we are done.

Hence, assume $P$ uses $x_{1}$ and $x_{3}$. As $D(u,v)$ is a diamond of
thickness greater than $4p+3k+1>3k$, according to Lemma 4.8 at least one of
the vertices $u$ and $v$, say $u$, is contained in $S_{i}$, and by definition
also in $S_{i}^{\prime}$. Then we can replace the vertices of $W$ on $P$ by
$u$ and we are again done.

Finally, the following claim is immediate from the definition of each
$S_{i}^{\prime}$. Combining Claim 1, 2, and 3, we conclude that
$S_{1}^{\prime},\ldots,S_{t}^{\prime}$ is a reconfiguration sequence from $S$
to $T$ in $G^{\prime}$.

######  Claim 11.

$S_{i+1}^{\prime}$ is obtained from $S_{i}^{\prime}$ by the addition or
removal of a single token for all $1\leq i<t$.

To prove the opposite direction, assume
$S=S_{1}^{\prime},\ldots,S_{t}^{\prime}=T$ is a reconfiguration sequence from
$S$ to $T$ in $G^{\prime}$. We claim that this is also a reconfiguration
sequence from $S$ to $T$ in $G$. All we have to show is that $S_{i}^{\prime}$
is a dominating set of $G$ for all $1\leq i\leq t$. This follows immediately
from the fact that $S_{i}^{\prime}$ is a dominating set of $G^{\prime}$, and
hence, as $W$ is not adjacent to $C\setminus\\{u,v\\}$ and $W\cap
C=\emptyset$, also a dominating set of $C$ in $G$. Then according to Lemma
4.3, $S_{i}^{\prime}$ also dominates $G$. We conclude that there is a
reconfiguration sequence from $S$ to $T$ in $G$ if and only if there is a
reconfiguration sequence from $S$ to $T$ in $G^{\prime}=G-W$.

### Proof of Lemma 4.20

######  Proof B.4.

We first show that we can essentially establish the situation depicted in
Figure 9. We may assume that the paths of $\mathcal{P}$ are induced paths,
otherwise we may replace them by induced paths. Let $H$ be the graph induced
on $u,v$ and the vertices of $\mathcal{P}$ that contains exactly the edges of
the paths in $\mathcal{P}$. In the figure, the paths of $\mathcal{P}$ are
depicted by thick edges, while the diagonal edges do not belong to the paths.
This situation is similar to the situation in the proof of Lemma 4.12. Just as
in the proof of Lemma 4.12, we find two adjacent faces $f,g$ of $H$ that do
not touch a vertex of $D\setminus\\{u,v\\}$.

$\bullet$$u$$\bullet$$v$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$x_{f}$$y_{f}$$z_{u}$$z_{v}$$x_{g}$$y_{g}$$\Rightarrow$$\bullet$$u$$\bullet$$v$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$
Figure 9. An exemplary situation handled by Lemma 4.20.

######  Claim 12.

The paths bounding $f$ and $g$ have length $3$, i.e., they have exactly two
inner vertices.

######  Proof B.5.

First observe that $P\in\mathcal{P}$ cannot have length exactly $2$, as then
$P$ contains a vertex adjacent to both $u$ and $v$. However, the vertices with
this property lie in $D$, and hence by construction not on $P$.

Assume there is $P\in\mathcal{P}$ of length greater than $3$. Let $M(u)$
denote the neighbors of $u$ that are in $V(G)\setminus D$ and are only
adjacent to $u$ and to no other vertex of $C$. Similarly, let $M(v)$ denote
the neighbors of $v$ that are in $V(G)\setminus D$ and are only adjacent to
$v$ and to no other vertex of $C$. By construction, the faces $f$ and $g$ do
not contain vertices of $D\setminus\\{u,v\\}$. Furthermore, $P$ contains
exactly one vertex of $M(u)$ and exactly one vertex of $M(v)$. It cannot
contain two vertices of one of these sets, as otherwise $P$ is not an induced
path. Hence, assume that $P$ contains another vertex $x$ that is not in
$M(u)\cup M(v)$. Then $x$ must be dominated by a vertex different from $u$ and
from $v$. However, by construction, the faces $f$ and $g$ do not touch a
vertex of $D\setminus\\{u,v\\}\supseteq(S\cup T)\setminus\\{u,v\\}$, a
contradiction.

Denote by $x_{f},y_{f}$ the two vertices that lie on the boundary of $f$ and
not on the boundary of $g$ and by $x_{g},y_{g}$ the two vertices that lie on
the boundary of $g$ and not on the boundary of $f$. Assume that
$x_{f},x_{g}\in M(u)$ and $y_{f},y_{g}\in M(v)$. Denote by $z_{u},z_{v}$ the
vertices shared by $f$ and $g$ different from $u$ and $v$ that are adjacent to
$u$ and $v$, respectively. Denote by $W$ the set of all vertices that lie
inside the face $h$ of the cycle $u,x_{f},y_{f},v,y_{g},x_{g},u$ that contains
the vertices $z_{u}$ and $z_{v}$. Hence $W$ contains at least the vertices
$z_{u}$ and $z_{v}$. By Corollary 4.13, we know that $u,v\in S_{i}$, for all
$1\leq i\leq t$ (both $u$ and $v$ can never be lifted). Consequently, by Lemma
4.15, we know that there are no edges with both endpoints in $N(v)$ nor edges
with both endpoints in $N(u)$. Combining the previous fact with the fact that
all vertices of $W$ are adjacent to either $u$ or $v$ (but not both) and to no
other vertex of $C\supseteq S\cup T$, we conclude that $W$ consists of exactly
the two vertices $z_{u}$ and $z_{v}$ and that there are no edges between
$z_{u}$ and $x_{g},x_{f}$ and no edges between $z_{v}$ and $y_{g},y_{f}$. Note
that we can safely assume that none of the degree-one neighbors of $u$ or $v$
are inside $W$. We claim that the vertices $z_{u}$ and $z_{v}$ are irrelevant
and can be removed after possibly introducing an additional edge to the graph.
Recall that $S$ and $T$ do not contain the vertices $z_{u}$ and $z_{v}$. We
define $G^{\prime}$ as follows.

  * •

If $\\{u,v\\}\not\in E(G)$ and ($\\{x_{f},z_{v}\\}\in E(G)$ or
$\\{y_{f},z_{u}\\}\in E(G)$) and ($\\{x_{g},z_{v}\\}\in E(G)$ or
$\\{y_{g},z_{u}\\}\in E(G)$) then $G^{\prime}$ is obtained from $G$ by
deleting $z_{u}$ and $z_{v}$ and introducing the edge $\\{x_{f},y_{g}\\}$.

  * •

Otherwise, $G^{\prime}$ is obtained from $G$ by simply deleting $z_{u}$ and
$z_{v}$.

We claim that $(G,S,T,k)$ and $(G^{\prime},S,T,k)$ are equivalent instances of
CDS-R. Assume first that there exists a reconfiguration sequence
$S=S_{1},\ldots,S_{t}=T$ in $G$. We distinguish two cases. First assume that
$\\{u,v\\}\in E(G)$. Hence, $G^{\prime}$ is obtained from $G$ by simply
deleting $z_{u}$ and $z_{v}$. Let $S_{1}^{\prime},\ldots,S_{t}^{\prime}$,
where for $1\leq i\leq t$, $S_{i}^{\prime}=S_{i}\setminus\\{z_{u},z_{v}\\}$.
We claim that $S_{1}^{\prime},\ldots,S_{t}^{\prime}$ is a reconfiguration
sequence from $S$ to $T$ in $G^{\prime}$.

######  Claim 13.

For $1\leq i\leq t$, $S_{i}^{\prime}$ is a dominating set of $G$, and hence
also of $G^{\prime}$.

######  Proof B.6.

The vertices $z_{u}$ and $z_{v}$ are not adjacent to a vertex of
$C\setminus\\{u,v\\}$ and $\\{z_{u},z_{v}\\}\cap C=\emptyset$. Hence, the only
vertices of $C$ that are possibly adjacent to $z_{u}$ or $z_{v}$ are the
vertices $u$ and $v$. According to Lemma 4.13, $u,v\in S_{i}$, and moreover
$u,v\in S_{i}^{\prime}$, for all $1\leq i\leq t$. Hence, $S_{i}^{\prime}$
dominates at least the vertices of $C$ that $S_{i}$ dominates. We use Lemma
4.3 to conclude that $S_{i}^{\prime}$ is a dominating set of $G$.

######  Claim 14.

For $1\leq i\leq t$, $S_{i}^{\prime}$ is connected.

######  Proof B.7.

Let $s_{1},s_{2}\in S_{i}\setminus\\{z_{u},z_{v}\\}$ and let $P$ be a shortest
path between $s_{1}$ and $s_{2}$ in $G[S_{i}]$. We have to show that there
exists a path between $s_{1}$ and $s_{2}$ in $G[S_{i}^{\prime}]$. If $P$ does
not use $z_{u}$ nor $z_{v}$ then there is nothing to prove. Hence, assume $P$
uses $z_{u}$ or $z_{v}$ (or both). By definition of $W$, both $s_{1}$ and
$s_{2}$ lie outside the face $h$ of the cycle $u,x_{f},y_{f},v,y_{g},x_{g},u$
that contains $z_{u},z_{v}$. Hence, $P$ must enter and leave the face $h$, say
it enters at $u$ and leaves at $y_{f}$. All other possibilities are handled
analogously. Then we can avoid the vertices $z_{u}$ and $z_{v}$ by walking to
$v$ first, then $u$ (or $x_{f}$), and then to $y_{f}$.

The next claim follows from the definition of $S_{i}^{\prime}$ and the fact
that we can remove any duplicate consecutive sets in a reconfiguration
sequence.

######  Claim 15.

$S_{i+1}^{\prime}$ is obtained from $S_{i}^{\prime}$ by the addition or
removal of a single token for all $1\leq i<t$.

This finishes the proof in case $\\{u,v\\}\in E(G)$. Hence, we assume now that
$\\{u,v\\}\not\in E(G)$ and ($\\{x_{f},z_{v}\\}\in E(G)$ or
$\\{y_{f},z_{u}\\}\in E(G)$) and ($\\{x_{g},z_{v}\\}\in E(G)$ or
$\\{y_{g},z_{u}\\}\in E(G)$). That is, $G^{\prime}$ is obtained from $G$ by
deleting $z_{u}$ and $z_{v}$ and introducing the edge $\\{x_{f},y_{g}\\}$. We
now obtain $S_{i}^{\prime}$ from $S_{i}$, for $1\leq i\leq t$, by replacing

  * •

$z_{u}$ by $x_{f}$ and $z_{v}$ by $y_{g}$ if
$S_{i}\cap\\{z_{u},z_{v}\\}=\\{z_{u},z_{v}\\}$,

  * •

$z_{u}$ by $x_{f}$ if $S_{i}\cap\\{z_{u},z_{v}\\}=\\{z_{u}\\}$, and

  * •

$z_{v}$ by $y_{g}$ if $S_{i}\cap\\{z_{u},z_{v}\\}=\\{z_{v}\\}$.

We claim that $S_{1}^{\prime},\ldots,S_{t}^{\prime}$ is a reconfiguration
sequence from $S$ to $T$ in $G^{\prime}$. We need no new arguments to prove
that each $S_{i}^{\prime}$ is a dominating set of $G$ and hence of
$G^{\prime}$ and that each $S_{i+1}^{\prime}$ is obtained from
$S_{i}^{\prime}$ by adding or removing one token. It remains to show that each
$S_{i}^{\prime}$ is connected in $G^{\prime}$.

######  Claim 16.

For $1\leq i\leq t$, $S_{i}^{\prime}$ is connected in $G^{\prime}$.

######  Proof B.8.

According to Lemma 4.13, $u,v\in S_{i}$, and also $u,v\in S_{i}^{\prime}$, for
all $1\leq i\leq t$. If $S_{i}\setminus\\{z_{u},z_{v}\\}$ is connected,
$S_{i}^{\prime}$ is also connected, hence assume
$S_{i}\setminus\\{z_{u},z_{v}\\}$ is not connected. As
$X=\\{u,x_{f},z_{u},x_{g}\\}$ is connected via $u$ and
$Y=\\{v,y_{f},z_{v},y_{g}\\}$ is connected via $v$, it suffices to show that
our vertex exchange creates a connection in $G^{\prime}$ between any vertex of
$X$ and any vertex of $Y$. If $S_{i}\cap\\{z_{u},z_{v}\\}=\\{z_{u},z_{v}\\}$
this is clear, as we shift the tokens to $x_{f}$ and $y_{g}$ and in
$G^{\prime}$ we have introduced the edge $\\{x_{f},y_{g}\\}$. If
$S_{i}\cap\\{z_{u},z_{v}\\}=\\{z_{u}\\}$, then $\\{z_{u},y_{g}\\}\in E(G)$ and
$y_{g}\in S_{i}$, or $\\{z_{u},y_{f}\\}\in E(G)$ and $y_{f}\in S_{i}$. We move
the token $z_{u}$ to $x_{f}$. In the first case we have connectivity via the
new edge $\\{x_{f},y_{g}\\}\in E(G^{\prime})$, and in the second case we have
connectivity via the edge $\\{x_{f},y_{f}\\}\in E(G)$. The case
$S_{i}\cap\\{z_{u},z_{v}\\}=\\{z_{v}\\}$ is symmetric.

This finishes the proof that if $(G,S,T,k)$ is a positive instance then
$(G^{\prime},S,T,k)$ is a positive instance. Now assume that there exists a
reconfiguration sequence $S=S_{1}^{\prime},\ldots,S_{t}^{\prime}=T$ in
$G^{\prime}$. In case we do not introduce the new edge to obtain $G^{\prime}$
from $G$, we do not need new arguments to see that
$S_{1}^{\prime},\ldots,S_{t}^{\prime}$ is a reconfiguration sequence also in
$G$. Moreover, if $G^{\prime\prime}[S_{i}^{\prime}]$ is connected for all $i$,
where $G^{\prime\prime}$ is obtained from $G^{\prime}$ by removing the edge
$\\{x_{f},y_{g}\\}$, then again there is nothing to prove as $G^{\prime}$ is a
subgraph of $G$ and therefore $S=S_{1}^{\prime},\ldots,S_{t}^{\prime}=T$ is a
reconfiguration sequence in $G$. Hence, assume that there exists at least one
contiguous subsequence $\sigma$ starting at index $s$ and ending at index $f$
(with possibly $s=f$) such that
$G^{\prime\prime}[S_{s}^{\prime}],G^{\prime\prime}[S_{s+1}^{\prime}],\ldots,G^{\prime\prime}[S_{f}^{\prime}]$
are not connected. In other words, there exists a subsequence of length one or
more that uses the edge $\\{x_{f},y_{g}\\}$ for connectivity. Moreover, we
assume, without loss of generality (the other case is symmetric), that
$S_{s}^{\prime}$ is obtained from $S_{s-1}^{\prime}$ by adding a token on
vertex $y_{g}$, i.e., $S_{s}^{\prime}=S_{s-1}^{\prime}\cup\\{y_{g}\\}$, and
$S_{f+1}^{\prime}$ is obtained from $S_{f}^{\prime}$ by removing the token on
vertex $x_{f}$, i.e., $S_{f+1}^{\prime}=S_{f}^{\prime}\setminus\\{x_{f}\\}$.
We also assume that $E(G)$ contains the edges $\\{x_{f},z_{v}\\}$ and
$\\{z_{u},y_{g}\\}$ (the remaining cases are handled identically). It remains
to show how to modify $\sigma$ so that it does not use the edge
$\\{x_{f},y_{g}\\}$ for connectivity and remains a valid reconfiguration
sequence in $G$. By applying the same arguments for any such subsequence we
obtain the required reconfiguration sequence in $G$. We modify $\sigma$ as
follows. We let
$S_{i}^{\prime\prime}=(S_{i}^{\prime}\setminus\\{y_{g}\\})\cup\\{z_{v}\\}$,
for $s\leq i\leq f$. Then we replace $S_{f+1}^{\prime}$ by four new sets
$A_{1}$, $A_{2}$, $A_{3}$, and $A_{4}$, where
$A_{1}=S_{f}^{\prime}\setminus\\{x_{f}\\}$, $A_{2}=A_{1}\cup\\{z_{u}\\}$,
$A_{3}=A_{2}\setminus\\{z_{v}\\}$, $A_{3}=A_{3}\cup\\{y_{g}\\}$, and
$A_{4}=A_{3}\setminus\\{z_{u}\\}$. Using the fact that the vertices
$x_{f},y_{f},x_{g},y_{g}$ are not adjacent to vertices of
$D\setminus\\{u,v\\}$, it is easy to see that this yields a valid
reconfiguration sequence, as both domination and connectivity are preserved.
This completes the proof of the lemma.