Distance Recoloring^††thanks: This work was partially completed when Duc A. Hoang was a postdoctoral researcher at the Vietnam Institute for Advanced Study in Mathematics (VIASM). Duc A. Hoang would like to thank VIASM for their support and hospitality.

Let $uv$ be some token edge of degree $4$ that is removed when applying (R1), that is, we replace $uv$ by the path $uu^{\prime}v^{\prime}v$ where $u^{\prime},v^{\prime}$ are newly added vertices, $uu^{\prime}$ and $vv^{\prime}$ are token edges, and $u^{\prime}v^{\prime}$ is a link edge. (For example, see Fig. 1.) Observe that $T_{A}\subset T^{1}_{A}$ and $T_{B}\subset T^{1}_{B}$. Here we use a convention that $G^{1}$ is constructed from $G$ by replacing the edge $uv$ by a path of length $3$. We note that $u\in T_{A}$ implies that $u,v^{\prime}$ are in $T^{1}_{A}$ while $u^{\prime},v$ are not and similarly $v\in T_{A}$ implies that $u^{\prime},v$ are in $T^{1}_{A}$ while $u,v^{\prime}$ are not.

Let $\mathcal{S}$ be a $\mathsf{TS}$-sequence in $G$ between $T_{A}$ and $T_{B}$. We construct a $\mathsf{TS}$-sequence $\mathcal{S}^{1}$ in $G^{1}$ between $T_{A}^{1}$ and $T_{B}^{1}$ from $\mathcal{S}$ as follows. We replace any move $u\to v$ in $\mathcal{S}$ by the ordered sequence of moves $\langle v^{\prime}\to v,u\to u^{\prime}\rangle$ and $v\to u$ by $\langle v\to v^{\prime},u^{\prime}\to u\rangle$. By the construction, since the move $u\to v$ results in a new independent set of $G$, so does each member in $\langle v^{\prime}\to v,u\to u^{\prime}\rangle$ of $G^{1}$. More precisely, since $u\to v$ can be applied in $G$, so does $v^{\prime}\to v$ in $G^{1}$. After the move $v^{\prime}\to v$, the move $u\to u^{\prime}$ can be performed as no token is placed on a neighbor of $u^{\prime}$ other than the one on $u$. Similar arguments hold for $v\to u$ and the sequence $\langle v\to v^{\prime},u^{\prime}\to u\rangle$. Thus, $\mathcal{S}^{1}$ is indeed a $\mathsf{TS}$-sequence $\mathcal{S}^{1}$ in $G^{1}$ between $T_{A}^{1}$ and $T_{B}^{1}$.

Now, let $\mathcal{S}^{1}$ be a $\mathsf{TS}$-sequence in $G^{1}$ between $T^{1}_{A}$ and $T^{1}_{B}$. We construct a $\mathsf{TS}$-sequence $\mathcal{S}$ in $G$ between $T_{A}$ and $T_{B}$ from $\mathcal{S}^{1}$ as follows. Every time we see a move $v^{\prime}\to v$ in $\mathcal{S}^{1}$, we ignore it. If after a move $v^{\prime}\to v$ (which we ignored) we see a move $u\to u^{\prime}$ then we replace $u\to u^{\prime}$ by the move $u\to v$. Again, by the construction, since the move $u\to u^{\prime}$ results in a new independent set of $G^{1}$ and so does the move $v^{\prime}\to v$ before it, the move $u\to v$ also results in a new independent set of $G$. More precisely, after the move $v^{\prime}\to v$ is applied, no token in $G^{1}$ can move to a neighbor of $v$ in $G^{1}$, which means that by our construction of $\mathcal{S}$, no token in $G$ other than the one on $u$ can be placed on a neighbor of $v$ in $G$. Hence, the move $u\to v$ results in a new independent set of $G$. Similarly, if we see a move $u^{\prime}\to u$ in $\mathcal{S}^{1}$, we ignore it. If after a move $u^{\prime}\to u$ (which we ignored) we see a move $v\to v^{\prime}$ then we replace $v\to v^{\prime}$ by the move $v\to u$. Similarly, one can argue that the move $v\to u$ results in a new independent set of $G$. Thus, $\mathcal{S}$ is a $\mathsf{TS}$-sequence in $G$ between $T_{A}$ and $T_{B}$. ∎

Observe that applying (R2) does not result any new token edge of degree $4$. Let $uv$ be some link edge joining two degree $3$ gadgets on which (R2) is applied, that is, we replace $uv$ by the path $uu^{\prime}v^{\prime}v$ where $u^{\prime},v^{\prime}$ are newly added vertices, $uu^{\prime}$ and $v^{\prime}v$ are link edges, and $u^{\prime}v^{\prime}$ is a token edge. (For example, see Figs. 2, 3 and 4.) Observe that $T_{A}^{1}\subset T_{A}^{2}$ and $T_{B}^{1}\subset T_{B}^{2}$. Here we use a convention that $G^{2}$ is constructed from $G^{1}$ by replacing the edge $uv$ by a path of length $3$. We note that $u\in T_{A}^{1}$ implies that $u,v^{\prime}$ are in $T_{A}^{2}$ while $u^{\prime},v$ are not and similarly $v\in T_{A}^{1}$ implies that $u^{\prime},v$ are in $T_{A}^{2}$ while $u,v^{\prime}$ are not.

Let $\mathcal{S}^{1}$ be a $\mathsf{TS}$-sequence in $G^{1}$ between $T_{A}^{1}$ and $T_{B}^{1}$. We construct a $\mathsf{TS}$-sequence $\mathcal{S}^{2}$ in $G^{2}$ between $T_{A}^{2}$ and $T_{B}^{2}$ from $\mathcal{S}^{1}$ as follows. We replace any move $u\to w$ in $\mathcal{S}^{1}$, where $u$ and $w$ are in the same token triangle/token edge, by the ordered sequence $\langle u\to w,v^{\prime}\to u^{\prime}\rangle$, and any move $w\to u$ by $\langle u^{\prime}\to v^{\prime},w\to u\rangle$ if there is a token on $u^{\prime}$. By the construction, since the move $u\to w$ results a new independent set of $G^{1}$, so does the move $u\to w$ in $G^{2}$. Moreover, as there is no token on $u$ or any of its neighbor other than the one on $w$ after performing $u\to w$ in $G^{2}$, the move $v^{\prime}\to u^{\prime}$ also results a new independent set of $G^{2}$. Similarly, since the move $w\to u$ results in a new independent set of $G^{1}$, so does the move $w\to u$ in $G^{2}$. Moreover, as $w\to u$ is a valid token-slide, right before performing it, there is no token on $v$, and thus the move $u^{\prime}\to v^{\prime}$ can be inserted right before $w\to u$ in $G^{2}$ if a token on $u^{\prime}$ exists. Analogously, we also replace any move $v\to x$ in $\mathcal{S}^{1}$, were $x$ and $v$ are in the same token triangle/token edge, by the ordered sequence $\langle v\to x,u^{\prime}\to v^{\prime}\rangle$ and $x\to v$ by $\langle v^{\prime}\to u^{\prime},x\to v\rangle$ if there is a token on $v^{\prime}$. By symmetry, one can also verify that these moves are valid in $G^{2}$, i.e., they always result in new independent sets of $G^{2}$. Thus, $\mathcal{S}^{2}$ is indeed a $\mathsf{TS}$-sequence $\mathcal{S}^{2}$ in $G^{2}$ between $T_{A}^{2}$ and $T_{B}^{2}$.

Now, let $\mathcal{S}^{2}$ be a $\mathsf{TS}$-sequence in $G^{2}$ between $T_{A}^{2}$ and $T_{B}^{2}$. We construct a $\mathsf{TS}$-sequence $\mathcal{S}^{1}$ in $G^{1}$ between $T_{A}^{1}$ and $T_{B}^{1}$ from $\mathcal{S}^{2}$ as follows. Every time we see a move $u^{\prime}\to v^{\prime}$ or $v^{\prime}\to u^{\prime}$, we ignore it. (Intuitively, we ignore any move between two new vertices not in $G^{1}$.) By the construction, since each move $u\to w$ in $\mathcal{S}^{2}$, where $u$ and $w$ are in the same token triangle/token edge of $G^{1}$, results in new independent set of $G^{2}$, it also results in new independent set of $G^{1}$, as every token triangle/token edge in $G^{1}$ is also in $G^{2}$. Thus, $\mathcal{S}$ is a $\mathsf{TS}$-sequence in $G^{1}$ between $T_{A}^{1}$ and $T_{B}^{1}$. ∎

Let $(G,T_{A},T_{B})$ be an instance of Sliding Tokens and $(G^{\prime},T^{\prime}_{A},T^{\prime}_{B})$ be the corresponding instance of Restricted Sliding Tokens. The \PSPACE-completeness follows from our construction and Sections 3.3.2 and 3.3.2 above. From our construction, since the input graph $G$ is planar, so is the constructed graph $G^{\prime}$. Additionally, we can also show that $G^{\prime}$ is $2$-degenerate. Let us prove by contradiction. Let $X$ be an induced subgraph in $G^{\prime}$ such that the minimum degree of any vertex in $X$ is at least $3$. By construction of $G^{\prime}$ for any vertex $x$ of degree $3$ in a token edge all its neighbors are of degree at most $2$. If $x\in X$, then at least one of its neighbors also belong to $X$ by definition. Hence, $X$ has a vertex of degree at most $2$ contradicting our assumption. For any vertex $x$ of degree $3$ in a token triangle at least one neighbor ($y$ which is outside the token triangle) is of degree at most $2$ and its neighbors ($x^{\prime}$ and $x^{\prime\prime}$) in the token triangle may be of degree $3$. $y\in X$ leads to a contradiction. If $x^{\prime}$ and $x^{\prime\prime}$ is in $X$ then including their corresponding neighbors of degree at most $2$ which are outside the token triangle in $X$ also leads to a contradiction. However, $x,x^{\prime}$ and $x^{\prime\prime}$ without any neighbors outside the token triangle in $X$ have degree at most $2$. This also leads to a contradiction.

∎

Suppose that $C=\{c_{1},\dots,c_{p}\}$ where $p$ is either $d+1$ if $d$ is odd or $d+2$ if $d$ is even. We define the path $P=v_{0}v_{1}\dots v_{p}v_{p+1}v_{p+2}$ such that $v_{0}=u$ and $v_{p+2}=v$. $P$ has length $p+2$, which is equal to $(d+1)+2=d+3$ if $d$ is odd and $(d+2)+2=d+4$ if $d$ is even. We define the color list $L$ for each vertex of $P$ as follows.

• •

  $L(u)=L(v_{0})=L_{u}$, $L(v)=L(v_{p+2})=L_{v}$, $L(v_{1})=\{a,c_{1}\}$, and $L(v_{p+1})=\{c_{p},b\}$.

• •

  For $2\leq i\leq p$, $L(v_{i})=\{c_{i-1},c_{i}\}$.

We claim that the path $P$ with the color list $L$ indeed form a $(C,a,b)$-forbidding path. It suffices to verify the conditions (1) and (2) in Definition 1.

We first verify (1). Suppose that $x\in L(u)$, $y\in L(v)$, and $(x,y)\neq(a,b)$. We describe how to construct a $[x,y]$-coloring. If $x=a$, we color $v_{0}$ by $a$, $v_{p+1}$ by $b$, $v_{p+2}$ by $y$ and $v_{i}$ by $c_{i}$ for $1\leq i\leq p$. Similarly, if $y=b$, we color $v_{p+2}$ by $b$, $v_{1}$ by $a$, $v_{0}$ by $x$, and $v_{i}$ by $c_{i-1}$ for $2\leq i\leq p+1$. If both $x\neq a$ and $y\neq b$, one possible valid coloring is to color $v_{0}$ by $x$, $v_{1}$ by $a$, $v_{p+1}$ by $b$, $v_{p+2}$ by $y$ and $v_{i}$ by $c_{i}$ for $2\leq i\leq p$. One can verify that our constructed colorings are $(d,k)$-colorings of $P$.

On the other hand, suppose that a $[x,y]$-coloring of $P$ exists. We claim that $x\in L(u)$, $y\in L(v)$, and $(x,y)\neq(a,b)$. The first two conditions are followed from the definition of a $[x,y]$-coloring. We show that the last condition holds. Observe that if $u=v_{0}$ has color $x=a$ then we are forced to color $v_{1}$ by $c_{1}$, $v_{2}$ by $c_{2}$, and so on until $v_{p}$ by $c_{p}$, and $v_{p+1}$ by $b$, which implies that the color of $v_{p+2}=v$ cannot be $b$; otherwise, our constructed coloring is not a $(d,k)$-coloring of $P$. Similar arguments can be applied for the case $v=v_{p+2}$ has color $y=b$. Thus, $(x,y)\neq(a,b)$.

We now verify (2). Let $(x,y)$ and $(x,y^{\prime})$ be two admissible pairs. From (1), a $[x,y]$-coloring $\alpha$ and a $[x,y^{\prime}]$-coloring $\beta$ of $P$ exist. We describe how to construct a reconfiguration sequence $\mathcal{S}$ which starts from $\alpha$, ends at $\beta$, and satisfies (2). If $v_{0}$ has color $x=a$, then both $\alpha$ and $\beta$ have the same coloring for all vertices of $P$ except at vertex $v$ and are therefore adjacent $(d,k)$-colorings. As $(x,y^{\prime})$ is an admissible pair, $y^{\prime}\neq b$, hence, we can recolor $v$ from $y$ to $y^{\prime}$.

If $v_{0}$ has color $x\neq a$, we show that a reconfiguration sequence from $\alpha$ to $\beta$ exists by describing a procedure that recolors both $\alpha$ and $\beta$ to the same $[x,y^{\prime}]$-coloring $\gamma$ of $P$. The coloring $\gamma$ is constructed from any $[x,y]$-coloring of $P$ where $x\neq a$ as follows. First, we recolor $v_{1}$ by $a$ (if it was already colored $a$ then there is nothing to do). Notice that the only other vertex in $v_{1},\dots,v_{p+1}$ which can potentially have the color $a$ is $v_{p+1}$, in the case that $a=b$. But as the distance between $v_{1}$ and $v_{p+1}$ is $p>d$, this recoloring step is valid.

Next, we recolor $v_{2}$ by $c_{1}$ as $c_{1}$ is not used to color any other vertex in $P$ currently. We proceed with coloring every $v_{i}$ by color $c_{i-1}$, $3\leq i\leq p+1$. Each recoloring step above is valid, as when we color $v_{i}$ by $c_{i-1}$, we always ensure that $c_{i-1}$ is not used to color any other vertex in $P$ at that time. Again, if $v_{i}$ is already colored $c_{i-1}$ then there is nothing to do. At the end of this process $v_{p+1}$ is colored with $c_{p}$. Finally, as the nearest vertex to $v=v_{p+2}$ which is colored $a$ is the vertex $v_{1}$ is at distance $p+1>d$ from $v$, this leaves us free to color $v$ with $y^{\prime}\in L(v)$. This gives the required reconfiguration sequence from $\alpha$ to $\beta$ by combining the sequences from $\alpha$ to $\gamma$ and from $\beta$ to $\gamma$. The case for admissible pairs $(x,y)$ and $(x^{\prime},y)$ is symmetric. ∎