# On the Complexity of Distance-$d$ Independent Set Reconfiguration

Duc A. Hoang ID ✉ Present address: VNU University of Science, Vietnam National
University, 334 Nguyen Trai Road, Thanh Xuan, Hanoi 100000, Viet Nam. Present
email<EMAIL_ADDRESS>Graduate School of Informatics, Kyoto
University
Kyoto, Japan
<EMAIL_ADDRESS>
###### Abstract

For a fixed positive integer $d\geq 2$, a distance-$d$ independent set
(D$d$IS) of a graph is a vertex-subset whose distance between any two members
is at least $d$. Imagine that there is a token placed on each member of a
D$d$IS. Two D$d$ISs are adjacent under Token Sliding ($\mathsf{TS}$) if one
can be obtained from the other by moving a token from one vertex to one of its
unoccupied adjacent vertices. Under Token Jumping ($\mathsf{TJ}$), the target
vertex needs not to be adjacent to the original one. The Distance-$d$
Independent Set Reconfiguration (D$d$ISR) problem under
$\mathsf{TS}/\mathsf{TJ}$ asks if there is a corresponding sequence of
adjacent D$d$ISs that transforms one given D$d$IS into another. The problem
for $d=2$, also known as the Independent Set Reconfiguration problem, has been
well-studied in the literature and its computational complexity on several
graph classes has been known. In this paper, we study the computational
complexity of D$d$ISR on different graphs under $\mathsf{TS}$ and
$\mathsf{TJ}$ for any fixed $d\geq 3$. On chordal graphs, we show that D$d$ISR
under $\mathsf{TJ}$ is in $\mathtt{P}$ when $d$ is even and
$\mathtt{PSPACE}$-complete when $d$ is odd. On split graphs, there is an
interesting complexity dichotomy: D$d$ISR is $\mathtt{PSPACE}$-complete for
$d=2$ but in $\mathtt{P}$ for $d=3$ under $\mathsf{TS}$, while under
$\mathsf{TJ}$ it is in $\mathtt{P}$ for $d=2$ but $\mathtt{PSPACE}$-complete
for $d=3$. Additionally, certain well-known hardness results for $d=2$ on
perfect graphs and planar graphs of maximum degree three and bounded bandwidth
can be extended for $d\geq 3$.

##  1 Introduction

Recently, reconfiguration problems have attracted the attention from both
theoretical and practical viewpoints. The input of a reconfiguration problem
consists of two feasible solutions of some source problem (e.g.,
Satisfiability, Independent Set, Vertex Cover, Dominating Set, etc.) and a
_reconfiguration rule_ that describes an adjacency relation between solutions.
One of the primary goal is to decide whether one feasible solution can be
transformed into the other via a sequence of adjacent feasible solutions where
each intermediate member is obtained from its predecessor by applying the
given reconfiguration rule exactly once. Such a sequence, if exists, is called
a _reconfiguration sequence_. In general, the (huge) set of all feasible
solutions is not given, and one can verify in polynomial time (with respect to
the input’s size) the feasibility and adjacency of solutions. Another way of
looking at reconfiguration problems involves the so-called reconfiguration
graphs—a graph whose vertices/nodes are feasible solutions and their adjacency
relation is defined via the given reconfiguration rule. Naturally, a
reconfiguration sequence is nothing but a walk in the corresponding
reconfiguration graph. Readers may recall the classic Rubik’s cube puzzle as
an example of a reconfiguration problem, where each configuration of the
Rubik’s cube corresponds to a feasible solution, and two configurations
(solutions) are adjacent if one can be obtained from the other by rotating a
face of the cube by either $90$, $180$, or $270$ degrees. The question is
whether one can transform an arbitrary configuration to the one where each
face of the cube has only one color. For an overview of this research area, we
refer readers to the surveys [Heuvel13, Nishimura18, MynhardtN19,
BousquetMNS22].

Reconfiguration problems involving vertex-subsets (e.g., clique, independent
set, vertex cover, dominating set, etc.) of a graph have been extensively
considered in the literature. In such problems, to make it more convenient for
describing reconfiguration rules, one usually views a vertex-subset of a graph
as a set of tokens placed on its vertices. Some well-known reconfiguration
rules in this setting are:

  * ◼

Token Sliding (${\mathsf{TS}}$): a token can only move to one of the
unoccupied adjacent vertices;

  * ◼

Token Jumping (${\mathsf{TJ}}$): a token can move to any unoccupied vertex;
and

  * ◼

Token Addition/Removal (${\mathsf{TAR}}(k)$): a token can either be added to
an unoccupied vertex or removed from an occupied one, such that the number of
tokens is always (upper/lower) bounded by some given positive integer $k$.

Let $G$ be a simple, undirected graph. An independent set of a graph $G$ is a
set of pairwise non-adjacent vertices. The Independent Set (IS) problem, which
asks if $G$ has an independent set of size at least some given positive
integer $k$, is one of the fundamental ${\mathtt{NP}}$-complete problems in
the computational complexity theory [GareyJohnson79]. Given an integer $d\geq
2$, a distance-$d$ independent set (also known as $d$-scattered set or
sometimes $d$-independent set111In fact, the terminology $d$-independent set
is sometimes used to indicate a vertex-subset such that any two members are of
distance at least $d+1$ for $d\geq 1$. We note that sometimes a
$d$-independent set is defined as a vertex-subset $S$ such that the maximum
degree of the subgraph induced by $S$ is at most $d$. In some other contexts,
a $d$-independent set is nothing but an independent set of size $d$.) of $G$
is a set of vertices whose pairwise distance is at least $d$. This
“distance-$d$ independent set” concept generalizes “independent set”: an
independent set is also a distance-$2$ independent set but may not be a
distance-$d$ independent set for $d\geq 3$. Given a fixed integer $d\geq 2$,
the Distance-$d$ Independent Set (D$d$IS) problem asks if there is a
distance-$d$ independent set of $G$ whose size is at least some given positive
integer $k$. Clearly, D$2$IS is nothing but IS. It is known that D$d$IS is
${\mathtt{NP}}$-complete for every fixed $d\geq 3$ on general graphs [KongZ93]
and even on regular bipartite graphs when $d\in\\{3,4,5\\}$ [KongZ00]. Eto et
al. [EtoGM14] proved that D$d$IS is ${\mathtt{NP}}$-complete for every fixed
$d\geq 3$ even for planar bipartite graphs of maximum degree three. They also
proved that on chordal graphs, D$d$IS is in ${\mathtt{P}}$ for any even $d\geq
2$ and remains ${\mathtt{NP}}$-complete for any odd $d\geq 3$. The complexity
of D$d$IS on several other graphs has also been studied [AgnarssonDH03,
MontealegreT16, JenaJDN18]. Additionally, D$d$IS and its variants have been
studied extensively from different viewpoints, including exact exponential
algorithms [YamanakaKT19], approximability [KatsikarelisLP19, EtoGM14,
JenaJDN18], and parameterized complexity [KatsikarelisLP20].

In this paper, we take D$d$IS as the source problem and initiate the study of
Distance-$d$ Independent Set Reconfiguration (D$d$ISR) from the classic
complexity viewpoint. The problem for $d=2$, which is usually known as the
Independent Set Reconfiguration (ISR) problem, has been well-studied from both
classic and parameterized complexity viewpoints. ISR under ${\mathsf{TS}}$ was
first introduced by Hearn and Demaine [HearnD05]. Ito et al. [ItoDHPSUU11]
introduced and studied the problem under ${\mathsf{TAR}}$ along with several
other reconfiguration problems. Under ${\mathsf{TJ}}$, the problem was first
studied by Kamiński et al. [KaminskiMM12]. Very recently, the study of ISR on
directed graphs has been initiated by Ito et al. [ItoIKNOTW22]. Additionally,
research on the structure and realizability of reconfiguration graphs for ISR
has been initiated both under ${\mathsf{TS}}$ [AvisH23-1, AvisH23-2] and
${\mathsf{TJ}}$ [BousquetDPT23]. Readers are referred to [Nishimura18,
BousquetMNS22] for a complete overview of recent developments regarding ISR.
We now briefly mention some known results regarding the computational
complexity of ISR on different graph classes. ISR remains
${\mathtt{PSPACE}}$-complete under any of
${\mathsf{TS}},{\mathsf{TJ}},{\mathsf{TAR}}$ on general graphs [ItoDHPSUU11],
planar graphs of maximum degree three and bounded bandwidth [HearnD05,
Zanden15, Wrochna18] and perfect graphs [KaminskiMM12]. Under ${\mathsf{TS}}$,
the problem is ${\mathtt{PSPACE}}$-complete even on split graphs
[BelmonteKLMOS21]. Interestingly, on bipartite graphs, ISR under
${\mathsf{TS}}$ is ${\mathtt{PSPACE}}$-complete while under any of
${\mathsf{TJ}}$ and ${\mathsf{TAR}}$ it is ${\mathtt{NP}}$-complete
[LokshtanovM19]. On the positive side, ISR under any of ${\mathsf{TJ}}$ and
${\mathsf{TAR}}$ is in ${\mathtt{P}}$ on even-hole-free graphs [KaminskiMM12]
(which also contains chordal graphs, split graphs, interval graphs, trees,
etc.), cographs [Bonsma16], and claw-free graphs [BonsmaKW14]. ISR under
${\mathsf{TS}}$ is in ${\mathtt{P}}$ on cographs [KaminskiMM12], claw-free
graphs [BonsmaKW14], trees [DemaineDFHIOOUY15], bipartite permutation graphs
and bipartite distance-hereditary graphs [Fox-EpsteinHOU15], and interval
graphs [BonamyB17, BrianskiFHM21]. Very recently, Bartier et al. [BartierBM24]
proved that ISR under any of ${\mathsf{TS}}$ and ${\mathsf{TJ}}$ is
${\mathtt{PSPACE}}$-complete on $H$-free graphs when $H$ is neither a path nor
a subdivision of the claw. Additionally, they designed a polynomial-time
algorithm to solve ISR under ${\mathsf{TS}}$ when the input graph is fork-
free.

D$d$ISR for $d\geq 3$ was first studied by Siebertz [Siebertz18] from the
parameterized complexity viewpoint. More precisely, in [Siebertz18], Siebertz
proved that D$d$ISR under ${\mathsf{TAR}}$ is in ${\mathtt{FPT}}$ for every
$d\geq 2$ on “nowhere dense graphs” (which generalized the previously known
result for $d=2$ of Lokshtanov et al. [LokshtanovMPRS15]) and it is
$\mathtt{W[1]}$-hard for some value of $d\geq 2$ on “somewhere dense graphs”
that are closed under taking subgraphs.

Since the ${\mathsf{TJ}}$ and ${\mathsf{TAR}}$ rules are somewhat equivalent
[KaminskiMM12], i.e., any ${\mathsf{TJ}}$-sequence between two size-$k$ token-
sets can be converted into a ${\mathsf{TAR}}$-sequence between them whose
members are token-sets of size at least $k-1$ and vice versa222They proved the
result for ISR, but it is not hard to extend it for D$d$ISR., in this paper,
we consider D$d$ISR ($d\geq 3$) under only ${\mathsf{TS}}$ and
${\mathsf{TJ}}$. Most of our results are summarized in Table 1. In short, we
show the following results.

  * ◼

It is worth noting that

    * □

Even though it is well-known that D$d$IS on $G$ and IS on its $(d-1)$th power
(this concept will be defined later) are equivalent, this does not necessarily
hold for their reconfiguration variants. (Section 3.1.)

    * □

The definition of D$d$IS implies the triviality of D$d$ISR for large enough
$d$ on graphs whose (connected) components’ diameters are bounded by some
constant, including cographs and split graphs. (Section 3.2.)

  * ◼

On chordal graphs and split graphs, there are some interesting complexity
dichotomies. (Section 4.)

    * □

Under ${\mathsf{TJ}}$ on chordal graphs, D$d$ISR is in ${\mathtt{P}}$ for even
$d$ and ${\mathtt{PSPACE}}$-complete for odd $d$.

    * □

On split graphs, D$d$ISR under ${\mathsf{TS}}$ is ${\mathtt{PSPACE}}$-complete
for $d=2$ [BelmonteKLMOS21] but in ${\mathtt{P}}$ for $d=3$. Under
${\mathsf{TJ}}$, it is in ${\mathtt{P}}$ for $d=2$ [KaminskiMM12] but
${\mathtt{PSPACE}}$-complete for $d=3$.

  * ◼

The known results for $d=2$ on perfect graphs [KaminskiMM12] and on planar
graphs of maximum degree three and bounded bandwidth [HearnD05, Zanden15,
Wrochna18] can be extended for $d\geq 3$. (Section 6.)

Graph ${\mathsf{TS}}$ ${\mathsf{TJ}}$ $d=2$ $d\geq 3$ $d=2$ $d\geq 3$ chordal
${\mathtt{PSPACE}}$-C [BelmonteKLMOS21] unknown ${\mathtt{P}}$ [KaminskiMM12]
even $d$: ${\mathtt{P}}$ (Cor. 4.1) odd $d$: ${\mathtt{PSPACE}}$-C (Thm. 4.2)
${\mathtt{PSPACE}}$-C [BelmonteKLMOS21] ${\mathtt{P}}$ [KaminskiMM12] $d=3$:
${\mathtt{PSPACE}}$-C split ${\mathtt{P}}$ (Cor. 4.3) ($\subseteq$ chordal)
(Props. 4.4 and 3.4) $d\geq 4$: ${\mathtt{P}}$ (Prop. 3.4) tree ($\subseteq$
chordal) ${\mathtt{P}}$ [DemaineDFHIOOUY15] unknown ${\mathtt{P}}$
[KaminskiMM12] ${\mathtt{P}}$ (Cor. 3.2) perfect ${\mathtt{PSPACE}}$-C
[KaminskiMM12] ${\mathtt{PSPACE}}$-C ${\mathtt{PSPACE}}$-C [KaminskiMM12]
${\mathtt{PSPACE}}$-C (Thm. 6.2) (Thm. 6.2) planar $\cap$ subcubic $\cap$
bounded bandwidth ${\mathtt{PSPACE}}$-C ${\mathtt{PSPACE}}$-C
${\mathtt{PSPACE}}$-C ${\mathtt{PSPACE}}$-C [HearnD05, Zanden15, Wrochna18]
(Thm. 6.3) [HearnD05, Zanden15, Wrochna18] (Thm. 6.3) cograph ($\subseteq$
perfect) ${\mathtt{P}}$ [KaminskiMM12] ${\mathtt{P}}$ (Cor. 3.5)
${\mathtt{P}}$ [Bonsma16] ${\mathtt{P}}$ (Cor. 3.5) interval ($\subseteq$
chordal) ${\mathtt{P}}$ [BonamyB17, BrianskiFHM21] unknown ${\mathtt{P}}$
[KaminskiMM12] ${\mathtt{P}}$ (Cor. 3.2)

Table 1: The computational complexity of D$d$ISR ($d\geq 3$) on some graphs
considered in this paper. For comparison, we also mention the corresponding
known results for $d=2$. ${\mathtt{PSPACE}}$-C stands for
${\mathtt{PSPACE}}$-complete.

##  2 Preliminaries

For terminology and notation not defined here, see [Diestel17]. Let $G$ be a
simple, undirected graph with vertex-set $V(G)$ and edge-set $E(G)$. For two
sets $I,J$, we sometimes use $I-J$ and $I+J$ to indicate $I\setminus J$ and
$I\cup J$, respectively. Additionally, we simply write $I-u$ and $I+u$ instead
of $I-\\{u\\}$ and $I+\\{u\\}$, respectively. The neighborhood of a vertex $v$
in $G$, denoted by $N_{G}(v)$, is the set $\\{w\in V(G):vw\in E(G)\\}$. The
closed neighborhood of $v$ in $G$, denoted by $N_{G}[v]$, is simply the set
$N_{G}(v)+v$. Similarly, for a vertex-subset $I\subseteq V(G)$, its
neighborhood $N_{G}(I)$ and closed neighborhood $N_{G}[I]$ are respectively
$\bigcup_{v\in I}N_{G}(v)$ and $N_{G}(I)+I$. The degree of a vertex $v$ in
$G$, denoted by $\mathsf{deg}_{G}(v)$, is $|N_{G}(v)|$. The distance between
two vertices $u,v$ in $G$, denoted by $\mathsf{dist}_{G}(u,v)$, is the number
of edges in a shortest path between them. For convenience, if there is no path
between $u$ and $v$ then $\mathsf{dist}_{G}(u,v)=\infty$. The diameter of $G$,
denoted by $\mathsf{diam}(G)$, is the largest distance between any two
vertices. A (connected) component of $G$ is a maximal subgraph in which there
is a path connecting any pair of vertices. An independent set (IS) of $G$ is a
vertex-subset $I\subseteq V(G)$ such that for any $u,v\in I$, we have
$uv\notin E(G)$. A distance-$d$ independent set (D$d$IS) of $G$ for an integer
$d\geq 2$ is a vertex-subset $I\subseteq V(G)$ such that for any $u,v\in I$,
$\mathsf{dist}_{G}(u,v)\geq d$.

Unless otherwise noted, we denote by $(G,I,J,{\mathsf{R}})$ an instance of
D$d$ISR under ${\mathsf{R}}\in\\{{\mathsf{TS}},{\mathsf{TJ}}\\}$ where $I$ and
$J$ are two distinct D$d$ISs of a given graph $G$, for some fixed $d\geq 2$.
Since $(G,I,J,{\mathsf{R}})$ is obviously a no-instance if $|I|\neq|J|$, from
now on, we always assume that $|I|=|J|$. Imagine that a token is placed on
each vertex in a D$d$IS of a graph $G$. A ${\mathsf{TS}}$-sequence in $G$
between two D$d$ISs $I$ and $J$ is the sequence $\mathcal{S}=\langle
I=I_{0},I_{1},\dots,I_{q}=J\rangle$ such that for $i\in\\{0,\dots,q-1\\}$, the
set $I_{i}$ is a D$d$IS of $G$ and there exists a pair $x_{i},y_{i}\in V(G)$
such that $I_{i}-I_{i+1}=\\{x_{i}\\}$, $I_{i+1}-I_{i}=\\{y_{i}\\}$, and
$x_{i}y_{i}\in E(G)$. By simply removing the restriction $x_{i}y_{i}\in E(G)$,
we immediately obtain the definition of a ${\mathsf{TJ}}$-sequence in $G$.
Depending on the considered rule
${\mathsf{R}}\in\\{{\mathsf{TS}},{\mathsf{TJ}}\\}$, we can also say that
$I_{i+1}$ is obtained from $I_{i}$ by immediately sliding/jumping a token from
$x_{i}$ to $y_{i}$ and write
$x_{i}\overset{G}{\longrightarrow}_{{\mathsf{R}}}y_{i}$. As a result, we can
also write $\mathcal{S}=\langle
x_{0}\overset{G}{\longrightarrow}_{{\mathsf{R}}}y_{0},\dots,x_{q-1}\overset{G}{\longrightarrow}_{{\mathsf{R}}}y_{q-1}\rangle$.
In short, $\mathcal{S}$ can be viewed as a (ordered) sequence of either
D$d$ISs or token-moves. (Recall that we defined $\mathcal{S}$ as a sequence
between $I$ and $J$. As a result, when regarding $\mathcal{S}$ as a sequence
of token-moves, we implicitly assume that the initial D$d$IS is $I$.) With
respect to the latter viewpoint, we say that $\mathcal{S}$ slides/jumps a
token $t$ from $u$ to $v$ in $G$ if $t$ is originally placed on $u\in I_{0}$
and finally on $v\in I_{q}$ after performing $\mathcal{S}$. The length of a
${\mathsf{R}}$-sequence is simply the number of times the rule ${\mathsf{R}}$
is applied. In particular, the ${\mathsf{R}}$-sequence $\mathcal{S}=\langle
x_{0}\overset{G}{\longrightarrow}_{{\mathsf{R}}}y_{0},\dots,x_{q-1}\overset{G}{\longrightarrow}_{{\mathsf{R}}}y_{q-1}\rangle$
has length $q$.

We conclude this section with the following remark: since D$d$IS is in
${\mathtt{NP}}$, D$d$ISR is always in ${\mathtt{PSPACE}}$ [ItoDHPSUU11]. As a
result, to show the ${\mathtt{PSPACE}}$-completeness of D$d$ISR, it is
sufficient to construct a polynomial-time reduction from a known
${\mathtt{PSPACE}}$-hard problem and prove its correctness.

##  3 Observations

###  3.1 Graphs and Their Powers

An extremely useful concept for studying distance-$d$ independent sets is the
so-called graph power. For a graph $G$ and an integer $s\geq 1$, the $s$th
power of $G$ is the graph $G^{s}$ whose vertices are $V(G)$ and two vertices
$u,v$ are adjacent in $G^{s}$ if $\mathsf{dist}_{G}(u,v)\leq s$. Observe that
$I$ is a distance-$d$ independent set of $G$ if and only if $I$ is an
independent set of $G^{d-1}$. Therefore, D$d$IS in $G$ is equivalent to IS in
$G^{d-1}$.

However, this may not apply for their reconfiguration variants. More
precisely, the statement “the D$d$ISR’s instance $(G,I,J,{\mathsf{R}})$ is a
yes-instance if and only if the ISR’s instance $(G^{d-1},I,J,{\mathsf{R}})$ is
a yes-instance” holds for ${\mathsf{R}}={\mathsf{TJ}}$ but not for
${\mathsf{R}}={\mathsf{TS}}$. The reason is that under ${\mathsf{TJ}}$ we do
not care about edges when performing token-jumps (as long as they result new
D$d$ISs), therefore whatever token-jump we perform in $G$ can also be done in
$G^{d-1}$ and vice versa. Therefore, we have the following proposition.

######  Proposition 3.1.

Let ${\mathcal{G}}$ and ${\mathcal{H}}$ be two graph classes and suppose that
for every $G\in{\mathcal{G}}$ we have $G^{d-1}\in{\mathcal{H}}$ for some fixed
integer $d\geq 2$. If ISR under ${\mathsf{TJ}}$ on ${\mathcal{H}}$ can be
solved in polynomial time, so does D$d$ISR under ${\mathsf{TJ}}$ on
${\mathcal{G}}$.

Recall that the power of any interval graph is also an interval graph
[AgnarssonGH00, ChenC10] and ISR under ${\mathsf{TJ}}$ on even-hole-free
graphs (which contains interval graphs) is in ${\mathtt{P}}$ [KaminskiMM12].
Along with Proposition 3.1, we immediately obtain the following corollary.

######  Corollary 3.2.

D$d$ISR under ${\mathsf{TJ}}$ is in ${\mathtt{P}}$ on interval graphs for any
$d\geq 2$.

On the other hand, when using token-slides, we need to consider which edges
can be used for moving tokens, and clearly $G^{d-1}$ has much more edges than
$G$, which means certain token-slides we perform in $G^{d-1}$ cannot be done
in $G$. More precisely, we have the following proposition.

######  Proposition 3.3.

Let $d\geq 3$ be a fixed integer. There exists a D$d$ISR’s no-instance
$(G,I,J,{\mathsf{TS}})$ such that the ISR’s instance
$(G^{d-1},I,J,{\mathsf{TS}})$ is a yes-instance, where $I,J$ are D$d$ISs of
$G$ (and therefore ISs of $G^{d-1}$) of size $k\geq 2$.

  * Proof.

We construct a graph $G$ as follows.

$P_{1}$$P_{2}$$P_{k}$$v_{1}$$v_{2}$$v_{k}$$v_{1}^{\star}$$v_{2}^{\star}$$v_{k}^{\star}$$w_{1}$$w_{2}$$w_{k}$$w_{1}^{\star}$$w_{2}^{\star}$$w_{k}^{\star}$

Figure 1: Construction of a D$d$ISR’s instance $(G,I,J,{\mathsf{TS}})$
satisfying Proposition 3.3. Paths $P_{1},\dots,P_{k}$ are marked by light gray
boxes. Paths $Q_{v_{i}^{\star},v_{j}}$ and $Q_{w_{i}^{\star},w_{j}}$ of length
$d-1$ are represented by bold dashed egdes, where $1\leq i,j\leq k$ and $i\neq
j$. Tokens in $I$ (resp. $J$) are marked with black (resp. gray) color.

Let $P_{1},\dots,P_{k}$ be $k$ disjoint paths of length $d-1$, for some $k\geq
2$. For each $i\in\\{1,2,\dots,k\\}$, let $v_{i}$ and $w_{i}$ be the endpoints
of $P_{i}$ and let $v^{\star}_{i}$ (resp. $w^{\star}_{i}$) be the unique
neighbor of $v_{i}$ (resp. $w_{i}$) in $P_{i}$. For each
$i\in\\{1,2,\dots,k\\}$, join $v^{\star}_{i}$ and $v_{j}$ (resp.
$w^{\star}_{i}$ and $w_{j}$), where $j\neq i$ and $1\leq j\leq k$, by a path
$Q_{v^{\star}_{i},v_{j}}$ (resp. $Q_{w^{\star}_{i},w_{j}}$) of length $d-1$.
Let $I=\\{v_{1},v_{2},\dots,v_{k}\\}$,
$I^{\star}=\\{v^{\star}_{1},v^{\star}_{2},\dots,v^{\star}_{k}\\}$,
$J=\\{w_{1},w_{2},\dots,w_{k}\\}$, and
$J^{\star}=\\{w^{\star}_{1},w^{\star}_{2},\dots,w^{\star}_{k}\\}$. (See Figure
1.)

We first verify that $I$ is indeed a D$d$IS of $G$. Similar arguments also
hold for $J$. Let $v_{i},v_{j}$ be any two distinct members of $I$, where
$1\leq i<j\leq k$. From the construction of $G$, one can verify that any path
$P^{ij}$ between $v_{i}$ and $v_{j}$ is of length

    * □

$d$ if either $V(P^{ij})\cap I^{\star}=\\{v^{\star}_{i}\\}$ or $V(P^{ij})\cap
I^{\star}=\\{v^{\star}_{j}\\}$;

    * □

$2(d-1)$ if ${V(P^{ij})}\cap I^{\star}=\\{v^{\star}_{\ell}\\}$ for some
$\ell\in\\{1,2,\dots,k\\}-\\{i,j\\}$;

    * □

at least $2(d-3)+4$ in the remaining cases, since any other path $P^{ij}$ must
contain one path of length at least $1$ between $v_{i}$ and some
$v^{\star}_{p}$, one path of length at least $1$ between $v_{j}$ and some
$v^{\star}_{q}\neq v^{\star}_{p}$, exactly two paths of length $d-3$: one
between $v^{\star}_{p}$ and $w^{\star}_{p}$ and the other between
$v^{\star}_{q}$ and $w^{\star}_{q}$, and one path of length at least $2$
between $w^{\star}_{p}$ and $w^{\star}_{q}$, for some
$p,q\in\\{1,2,\dots,k\\}$.

Thus, when $d\geq 3$, any path $P^{ij}$ between $v_{i}$ and $v_{j}$ has length
at least $d$, and the equality happens when either $V(P^{ij})\cap
I^{\star}=\\{v^{\star}_{i}\\}$ or $V(P^{ij})\cap
I^{\star}=\\{v^{\star}_{j}\\}$. It follows that
$\mathsf{dist}_{G}(v_{i},v_{j})\geq d$. Since this holds for any pair
$v_{i},v_{j}\in I$ ($1\leq i<j\leq k$), the set $I$ is a D$d$IS of $G$.

Next, we prove that $(G,I,J,{\mathsf{TS}})$ is a no-instance of D$d$ISR. To
show this, we prove that no tokens in $I$ can be moved even to one of its
adjacent vertices and (by applying similar arguments) so do those in $J$. For
each $i\in\\{1,2,\dots,k\\}$, let $x_{ij}$ be the unique neighbor of $v_{i}$
in the path $Q_{v^{\star}_{j},v_{i}}$ where $j\in\\{1,2,\dots,k\\}-i$. From
the construction of $G$,
$N_{G}(v_{i})=\bigcup_{j\in\\{1,2,\dots,k\\}-i}\\{x_{ij}\\}\cup\\{v^{\star}_{i}\\}$.
We now prove that for each $i\in\\{1,2,\dots,k\\}$, a token $t_{i}$ on $v_{i}$
can be slid to one of its neighbors if all other tokens $t_{j}$ on $v_{j}$,
for $j\in\\{1,2,\dots,k\\}-i$, must be moved before moving $t_{i}$. If this
claim holds, no tokens in $I$ (and similarly in $J$) can be moved, and
therefore $(G,I,J,{\mathsf{TS}})$ is a no-instance.

If $t_{i}$ is moved to $v^{\star}_{i}$, since all $Q_{v^{\star}_{i},v_{j}}$
are of length $d-1$, the tokens $t_{j}$ must be moved before $t_{i}$, for
$j\in\\{1,2,\dots,k\\}-i$. If $t_{i}$ is moved to some $x_{ij}$, since
$Q_{v^{\star}_{j},v_{i}}$ is of length $d-1$, the token $t_{j}$ on $v_{j}$
must be moved before $t_{i}$, for $j\in\\{1,2,\dots,k\\}-1$. By applying the
above arguments for $t_{j}$ instead of $t_{i}$, we obtain that there must be
some token $t_{\ell}$, where $\ell\in\\{1,2,\dots,k\\}-\\{i,j\\}$ that must be
moved before $t_{j}$, which clearly also before $t_{i}$. By repeatedly
applying these arguments, we finally obtain that all other tokens must be
moved before $t_{i}$.

It remains to show that $(G^{d-1},I,J,{\mathsf{TS}})$ is a yes-instance of
ISR. Observe that for each $i\in\\{1,2,\dots,k\\}$, we have
$\mathsf{dist}_{G}(v_{i},w_{i})=d-1$ and $\mathsf{dist}_{G}(v_{i},w_{j})\geq
2d-3\geq d$ for every $d\geq 3$ and $j\in\\{1,2,\dots,k\\}-i$. Therefore, in
$G^{d-1}$, there is an edge between $v_{i}$ and $w_{i}$, while there is no
edge joining $v_{i}$ and $w_{j}$, for $i,j\in\\{1,2,\dots,k\\}$ and $i\neq j$.
Thus, $\mathcal{S}=\langle
v_{1}\overset{G^{d-1}}{\longrightarrow}_{{\mathsf{TS}}}w_{1},v_{2}\overset{G^{d-1}}{\longrightarrow}_{{\mathsf{TS}}}w_{2},\dots,v_{k}\overset{G^{d-1}}{\longrightarrow}_{{\mathsf{TS}}}w_{k}\rangle$
is a ${\mathsf{TS}}$-sequence that transforms $I$ into $J$. ∎

###  3.2 Graphs With Bounded Diameter Components

The following observation is straightforward.

######  Proposition 3.4.

Let ${\mathcal{G}}$ be a graph class such that there is some constant $c>0$
satisfying $\mathsf{diam}(C_{G})\leq c$ for any $G\in{\mathcal{G}}$ and any
component $C_{G}$ of $G$. Then, D$d$ISR on ${\mathcal{G}}$ under
${\mathsf{R}}\in\\{{\mathsf{TS}},{\mathsf{TJ}}\\}$ is in ${\mathtt{P}}$ for
every $d\geq c+1$.

  * Proof.

When $d\geq c+1$, any D$d$IS contains at most one vertex in each component of
$G$, and the problem becomes trivial: under ${\mathsf{TJ}}$, the answer is
always “yes”; under ${\mathsf{TS}}$, compare the number of tokens in each
component. ∎

As a result, on cographs (a.k.a $P_{4}$-free graphs), one can immediately
derive the following corollary.

######  Corollary 3.5.

D$d$ISR on cographs under ${\mathsf{R}}\in\\{{\mathsf{TS}},{\mathsf{TJ}}\\}$
is in ${\mathtt{P}}$ for any $d\geq 2$.

  * Proof.

It is well-known that the problems for $d=2$ is in ${\mathtt{P}}$
[KaminskiMM12, Bonsma16]. Since a connected cograph has diameter at most two,
Proposition 3.4 settles the case $d\geq 3$. ∎

##  4 Chordal Graphs and Split Graphs

In this section, we will focus on chordal graphs and split graphs. Recall that
the odd power of a chordal graph is also chordal [BalakrishnanP83,
AgnarssonGH00] and ISR under ${\mathsf{TJ}}$ on even-hole-free graphs (which
contains chordal graphs) is in ${\mathtt{P}}$ [KaminskiMM12]. Therefore, it
follows from Proposition 3.1 that the following corollary holds.

######  Corollary 4.1.

D$d$ISR is in ${\mathtt{P}}$ on chordal graphs under ${\mathsf{TJ}}$ for any
even $d\geq 2$.

In contrast, we have the following theorem.

######  Theorem 4.2.

D$d$ISR is ${\mathtt{PSPACE}}$-complete on chordal graphs under
${\mathsf{TJ}}$ for any odd $d\geq 3$.

  * Proof.

We reduce from the ISR problem, which is known to be
${\mathtt{PSPACE}}$-complete under ${\mathsf{TJ}}$ [ItoDHPSUU11]. Let
$(G,I,J,{\mathsf{TJ}})$ be an ISR’s instance. We construct a D$d$ISR’s
instance $({G^{\prime}},{I^{\prime}},{J^{\prime}},{\mathsf{TJ}})$ ($d\geq 3$
is odd) as follows. We note that a similar reduction was used by Eto et al.
[EtoGM14] for showing the ${\mathtt{NP}}$-completeness of D$d$IS on chordal
graphs for odd $d\geq 3$. We first describe how to construct ${G^{\prime}}$
from $G$. For each vertex $v\in V(G)$, we add $v$ to $V({G^{\prime}})$. For
each edge $uv\in V(G)$, we add a vertex $x_{uv}$ to $V({G^{\prime}})$ and
create an edge in ${G^{\prime}}$ between $x_{uv}$ and both $u$ and $v$. Next,
we add an edge in $G^{\prime}$ between $x_{uv}$ and $x_{u^{\prime}v^{\prime}}$
for any pair of distinct edges $uv,u^{\prime}v^{\prime}\in E(G)$. Finally, for
each $v\in V(G)$, we add to ${G^{\prime}}$ a new path $P_{v}$ on $(d-3)/2$
vertices and then add an edge in ${G^{\prime}}$ between $v$ and one of
$P_{v}$’s endpoints. One can verify that ${G^{\prime}}$ is indeed a chordal
graph: it is obtained from a split graph by attaching new paths to certain
vertices. Clearly this construction can be done in polynomial time. (For
example, see Figure 2.)

$1$$2$$3$$4$$5$$G$$1$$2$$3$$4$$5$$x_{12}$$x_{14}$$x_{23}$$x_{24}$$x_{35}$$f(1)$$f(4)$$f(2)$$f(5)$$f(3)$${G^{\prime}}$

Figure 2: An example of constructing a chordal graph ${G^{\prime}}$ from $G$
for $d=5$. Vertices in a light-gray box form a clique. Vertices in
$V({G^{\prime}})-V(G)$ are marked with the gray color.

For each $u\in V(G)$, we define $f(u)\in V({G^{\prime}})$ to be the vertex
whose distance in ${G^{\prime}}$ from $u$ is largest among all vertices in
$V(P_{u})+u$. Let $f(X)=\bigcup_{x\in X}\\{f(x)\\}$ for a vertex-subset
$X\subseteq V(G)$. From the construction of ${G^{\prime}}$, note that if $u$
and $v$ are two vertices of distance $2$ in $G$, one can always find a
shortest path $Q$ between $f(u)$ and $f(v)$ whose length is exactly $d$.
Indeed, $Q$ can be obtained by joining the paths from $f(u)$ to $u$, from $u$
to $x_{uw}$, from $x_{uw}$ to $x_{wv}$, from $x_{wv}$ to $v$, and from $v$ to
$f(v)$, where $w\in N_{G}(u)\cap N_{G}(v)$. It follows that if $I$ is an
independent set of $G$ then $f(I)$ is a distance-$d$ independent set of
${G^{\prime}}$. Therefore, we can set ${I^{\prime}}=f(I)$ and
${J^{\prime}}=f(J)$.

From the construction of ${G^{\prime}}$, note that for each $uv\in E(G)$,
$x_{uv}$ is of distance exactly one from each $x_{wz}$ for $wz\in E(G)-uv$, at
most two from each $v\in V(G)$, and at most $2+(d-3)/2\leq d-1$ from each
vertex in $P_{v}$ for $v\in V(G)$. It follows that any distance-$d$
independent set of ${G^{\prime}}$ of size at least two must not contain any
vertex in $\bigcup_{uv\in E(G)}\\{x_{uv}\\}$.

We now show that there is a ${\mathsf{TJ}}$-sequence between $I$ and $J$ in
$G$ if and only if there is a ${\mathsf{TJ}}$-sequence between ${I^{\prime}}$
and ${J^{\prime}}$ in ${G^{\prime}}$. If $|I|=|J|=1$, the claim is trivial. As
a result, we consider the case $|I|=|J|\geq 2$. Since $f(I)$ is a distance-$d$
independent set in ${G^{\prime}}$ if $I$ is an independent set in $G$, the
only-if direction is clear. It remains to show the if direction. Let
${\mathcal{S}}^{\prime}$ be a ${\mathsf{TJ}}$-sequence in ${G^{\prime}}$
between ${I^{\prime}}$ and ${J^{\prime}}$. We modify ${\mathcal{S}}^{\prime}$
by repeating the following steps:

  * □

Let $x\overset{{G^{\prime}}}{\longrightarrow}_{{\mathsf{TJ}}}y$ be the first
token-jump that move a token from $x\in f(V(G))$ to some $y\in
V(P_{u})+u-f(u)$ for some $u\in V(G)$. If no such token-jump exists, we stop.
Let $I_{x}$ and $I_{y}$ be respectively the distance-$d$ independent sets
obtained before and after this token-jump. In particular, $I_{y}=I_{x}-x+y$.

  * □

Replace $x\overset{{G^{\prime}}}{\longrightarrow}_{{\mathsf{TJ}}}y$ by
$x\overset{{G^{\prime}}}{\longrightarrow}_{{\mathsf{TJ}}}f(u)$ and replace the
first step after $x\overset{{G^{\prime}}}{\longrightarrow}_{{\mathsf{TJ}}}y$
of the form $y\overset{{G^{\prime}}}{\longrightarrow}_{{\mathsf{TJ}}}z$ by
$f(u)\overset{{G^{\prime}}}{\longrightarrow}_{{\mathsf{TJ}}}z$. From the
construction of ${G^{\prime}}$, note that any path containing $f(u)$ must also
contains all vertices in $V(P_{u})+u$. Additionally,
$I_{x}\cap(V(P_{u})+u)=\emptyset$, otherwise no token in $I_{x}$ can jump to
$y$. Therefore, the set $I_{x}-x+f(u)$ is also a distance-$d$ independent set.
Moreover,
$\mathsf{dist}_{{G^{\prime}}}(f(u),z)\geq\mathsf{dist}_{{G^{\prime}}}(y,z)$
for any $z\in V({G^{\prime}})-V(P_{u})$. Roughly speaking, this implies that
no token-jump between
$x\overset{{G^{\prime}}}{\longrightarrow}_{{\mathsf{TJ}}}y$ and
$y\overset{{G^{\prime}}}{\longrightarrow}_{{\mathsf{TJ}}}z$ breaks the
“distance-$d$ restriction”. Thus, after the above replacements,
${\mathcal{S}}^{\prime}$ is still a ${\mathsf{TJ}}$-sequence in
${G^{\prime}}$.

  * □

Repeat the first step.

After modification, the final resulting ${\mathsf{TJ}}$-sequence
${\mathcal{S}}^{\prime}$ in ${G^{\prime}}$ contains only token-jumps between
vertices in $f(V(G))$. By definition of $f$, we can construct a
${\mathsf{TJ}}$-sequence between $I$ and $J$ in $G$ simply by replacing each
step $x\overset{{G^{\prime}}}{\longrightarrow}_{{\mathsf{TJ}}}y$ in
${\mathcal{S}}^{\prime}$ by
$f^{-1}(x)\overset{G}{\longrightarrow}_{{\mathsf{TJ}}}f^{-1}(y)$. Our proof is
complete. ∎

Now, we consider the split graphs. Proposition 3.4 implies that on split
graphs (where each component has diameter at most $3$), D$d$ISR is in
${\mathtt{P}}$ under ${\mathsf{R}}\in\\{{\mathsf{TS}},{\mathsf{TJ}}\\}$ for
any $d\geq 4$. Interestingly, recall that when $d=2$, the problem under
${\mathsf{TS}}$ is ${\mathtt{PSPACE}}$-complete even on split graphs
[BelmonteKLMOS21] while under ${\mathsf{TJ}}$ it is in ${\mathtt{P}}$
[KaminskiMM12]. It remains to consider the case $d=3$.

Observe that the constructed graph ${G^{\prime}}$ in the proof of Theorem 4.2
is indeed a split graph when $d=3$. Therefore, we have the following
corollary.

######  Corollary 4.3.

D$3$ISR is ${\mathtt{PSPACE}}$-complete on split graphs under ${\mathsf{TJ}}$.

In contrast, under ${\mathsf{TS}}$, we have the following proposition.

######  Proposition 4.4.

D$3$ISR is in ${\mathtt{P}}$ on split graphs under ${\mathsf{TS}}$.

  * Proof.

Let $(G,I,J,{\mathsf{TS}})$ be an instance of D$3$ISR and suppose that $V(G)$
can be partitioned into a clique $K$ and an independent set $S$. One can
assume without loss of generality that $G$ is connected, otherwise each
component can be solved independently. If $|I|=|J|=1$, the problem becomes
trivial: $(G,I,J,{\mathsf{R}})$ is always a yes-instance. Thus, we now
consider $|I|=|J|\geq 2$. Observe that for every $u\in V(G)$ and $v\in K$, we
have $\mathsf{dist}_{G}(u,v)\leq 2$. Therefore, in this case, both $I$ and $J$
are subsets of $S$. Note that $I\neq J$. Now, no token in $I\cup J$ can be
slid, otherwise such a token must be slid to some vertex in $K$, and each
vertex in $K$ has distance at most two from any other token, which contradicts
the restriction that tokens must form a D$3$IS. Hence, $(G,I,J,{\mathsf{TS}})$
is always a no-instance if $|I|=|J|\geq 2$. ∎

##  5 A Reduction under ${\mathsf{TJ}}$ on General Graphs

Recall that Ito et al. [ItoDHPSUU11] proved the
${\mathtt{PSPACE}}$-completeness of ISR under ${\mathsf{TJ}}/{\mathsf{TAR}}$
by reducing from 3-Satisfiability Reconfiguration (3SAT-R). In this section,
we present a simple proof for the ${\mathtt{PSPACE}}$-hardness of D$d$ISR
($d\geq 3$) on general graphs under ${\mathsf{TJ}}$ by reducing from ISR
instead of 3SAT-R.

######  Theorem 5.1.

D$d$ISR is ${\mathtt{PSPACE}}$-complete under ${\mathsf{TJ}}$ for any $d\geq
3$.

  * Proof.

We reduce from the ISR problem, which is known to be
${\mathtt{PSPACE}}$-complete under ${\mathsf{TJ}}$ [ItoDHPSUU11]. Let
$(G,I,J,{\mathsf{TJ}})$ be an ISR’s instance. We construct a D$d$ISR’s
instance $({G^{\prime}},I,J,{\mathsf{TJ}})$ ($d\geq 3$) as follows. Unless
otherwise noted, we always assume $p=(d-1)/2$ if $d$ is odd and $p=(d-2)/2$ if
$d$ is even. To construct ${G^{\prime}}$ from $G$, we first replace each edge
$uv\in E(G)$ with a new path $P_{uv}=x_{0}^{uv}\dots x_{d-1}^{uv}$ of length
$d-1$, where $x_{0}^{uv}=u$ and $x_{d-1}^{uv}=v$. We emphasize that the
ordering of endpoints is important, i.e., $P_{vu}=x_{0}^{vu}\dots
x_{d-1}^{vu}$ is the path where $x_{i}^{vu}=x_{d-1-i}^{uv}$ for $0\leq i\leq
d-1$. Basically, $P_{uv}$ and $P_{vu}$ describe the same path with different
vertex-labels. If $d$ is odd, we create a new clique $K$ whose vertices are
$\bigcup_{uv\in E(G)}\\{x_{p}^{uv}\\}$. If $d$ is even, we add a new vertex
$x^{\star}$ and create an edge between it and every vertex in $\bigcup_{uv\in
E(G)}\\{x_{p}^{uv},x_{p+1}^{uv}\\}$. The resulting graph is ${G^{\prime}}$.
(For example, see Figure 3.) Clearly this construction can be done in
polynomial time.

$1$$2$$3$$4$$5$$d=2$$1$$2$$3$$4$$5$$x_{1}^{12}$$x_{1}^{14}$$x_{1}^{23}$$x_{1}^{24}$$x_{1}^{35}$$d=3$$1$$2$$3$$4$$5$$d=4$$x_{1}^{12}$$x_{1}^{14}$$x_{1}^{23}$$x_{1}^{24}$$x_{1}^{35}$$x_{2}^{12}$$x_{2}^{14}$$x_{2}^{23}$$x_{2}^{24}$$x_{2}^{35}$$x^{\star}$

Figure 3: An example of constructing ${G^{\prime}}$ from a given graph $G$ for
some values of $d\in\\{2,3,4\\}$ (in case $d=2$, we have ${G^{\prime}}=G$).
Vertices in $V({G^{\prime}})-V(G)$ are marked with the gray color.

Now, we show that an independent set of $G$ of size $k\geq 2$ is also a
distance-$d$ independent set of ${G^{\prime}}$ and vice versa. From the
construction, for every $uv\in E(G)$, it follows that
$\mathsf{dist}_{{G^{\prime}}}(u,v)\leq d-1$ and therefore both $u$ and $v$
cannot be in the same distance-$d$ independent set of ${G^{\prime}}$.
Additionally, observe that for every $uv\notin E(G)$, any path between $u$ and
$v$ in ${G^{\prime}}$ must contain $x_{p}^{uw}$ and $x_{p}^{vz}$, for some
$w\in N_{G}(u)$ and $z\in N_{G}(v)$. Thus, a shortest path between $u$ and $v$
in ${G^{\prime}}$ must be of the form $x_{0}^{uw}\dots
x_{p}^{uw}x_{p}^{vz}\dots x_{0}^{vz}$ if $d$ is odd and $x_{0}^{uw}\dots
x_{p}^{uw}x^{\star}x_{p}^{vz}\dots x_{0}^{vz}$ if $d$ is even. One can verify
that such a shortest path has length exactly $d$. Therefore,
$\mathsf{dist}_{{G^{\prime}}}(u,v)\geq d$. As a result, if $I$ is an
independent set of $G$ (of size $k\geq 2$) then it is also a distance-$d$
independent set of ${G^{\prime}}$. On the other hand, suppose that
${I^{\prime}}$ is a distance-$d$ independent set of ${G^{\prime}}$ of size
$k\geq 2$. We claim that ${I^{\prime}}$ does not contain any new vertex. Let
$X=\bigcup_{uv\in E(G)}\\{x_{1}^{uv},\dots,x_{d-2}^{uv}\\}\cup\\{x^{\star}\\}$
be the set of all new vertices. (Note that $x^{\star}$ only appears when $d$
is even.) To show that ${I^{\prime}}\cap X=\emptyset$, we will show that the
distance between a vertex in $X$ and any other vertex in $V({G^{\prime}})$ is
at most $d-1$. From the construction of ${G^{\prime}}$, the distance between
$x^{\star}$ (if exists) and any other vertex is at most $p+1=(d-2)/2+1\leq
d-1$. It remains to show that one can always find a path of length at most
$d-1$ between a new vertex $x=x_{i}^{uv}\in X-x^{\star}$ and a vertex
$y=x_{j}^{wz}\in V({G^{\prime}})-\\{x,x^{\star}\\}$, where $1\leq i\leq d-2$,
$0\leq j\leq d-1$, and $uv,wz\in E(G)$. If $d$ is odd, such a path can be
constructed by joining the paths from $x=x_{i}^{uv}$ to $x_{p}^{uv}$ (of
length $\leq p-1$), from $x_{p}^{uv}$ to $x_{p}^{wz}$ (of length $\leq 1$),
and from $x_{p}^{wz}$ to $y=x_{j}^{wz}$ (of length $\leq p$). If $d$ is even,
such a path can be constructed by joining the paths from $x=x_{i}^{uv}$ to the
vertex $a\in\\{x_{p}^{uv},x_{p+1}^{uv}\\}$ closest to $x$ (of length $\leq
p-1$), from $a$ to $x^{\star}$ (of length $\leq 1$), from $x^{\star}$ to the
vertex $b\in\\{x_{p}^{wz},x_{p+1}^{wz}\\}$ closest to $y$ (of length $\leq
1$), and from $b$ to $y=x_{j}^{wz}$ (of length $\leq p$). As a result,
${I^{\prime}}\subseteq V(G)$, and from the construction of ${G^{\prime}}$, it
follows that ${I^{\prime}}$ is an independent set of $G$ of size $k\geq 2$.

We are now ready to show that $(G,I,J,{\mathsf{TJ}})$ is a yes-instance of ISR
if and only if $({G^{\prime}},I,J,{\mathsf{TJ}})$ is a yes-instance of
D$d$ISR. Suppose that $|I|=|J|=k$. If $k=1$, the claim is trivial. Therefore,
we consider $k\geq 2$. In this case, since any independent set of $G$ is also
a distance-$d$ independent set of ${G^{\prime}}$ and vice versa, it follows
that any ${\mathsf{TJ}}$-sequence in $G$ is also a ${\mathsf{TJ}}$-sequence in
${G^{\prime}}$ and vice versa. Our proof is complete. ∎

##  6 Extending Some Known Results for $d=2$

In this section, we prove that several known results on the complexity of
D$d$ISR for the case $d=2$ can be extended for $d\geq 3$.

###  6.1 General Graphs

Ito et al. [ItoDHPSUU11] proved that ISR is ${\mathtt{PSPACE}}$-complete on
general graphs under ${\mathsf{TJ}}/{\mathsf{TAR}}$. Indeed, their proof uses
only maximum independent sets, which implies that any token-jump is also a
token-slide [BonsmaKW14], and therefore the ${\mathtt{PSPACE}}$-completeness
also holds under ${\mathsf{TS}}$. We will show that the reduction of Ito et
al. [ItoDHPSUU11] can be extended for showing the
${\mathtt{PSPACE}}$-completeness of D$d$ISR for $d\geq 3$.

######  Theorem 6.1.

D$d$ISR is ${\mathtt{PSPACE}}$-complete under
${\mathsf{R}}\in\\{{\mathsf{TS}},{\mathsf{TJ}}\\}$ for any $d\geq 3$.

  * Proof.

Recall that Ito et al. [ItoDHPSUU11] proved the ${\mathtt{PSPACE}}$-hardness
of the problem for $d=2$ by reducing from a known ${\mathtt{PSPACE}}$-complete
problem called 3-Satisfiability Reconfiguration (3SAT-R) [GopalanKMP09]. A
3SAT formula $\varphi$ consists of $n$ variables $x_{1},\dots,x_{n}$ and $m$
clauses $c_{1},\dots,c_{m}$, each clause contains at most three literals (a
literal is either $x_{i}$ or $\overline{x_{i}}$). A truth assignment $\phi$ is
a way of assigning either $1$ (true) or $0$ (false) to each $x_{i}$. A truth
assignment $\phi$ satisfies a clause if at least one literal is $1$ and it
satisfies the formula $\varphi$ if all clauses are satisfied. In a 3SAT-R
instance $(\varphi,\phi_{s},\phi_{t})$, two satisfying assignments $\phi$ and
$\phi^{\prime}$ are adjacent if they differ in assigning exactly one variable.
The 3SAT-R problem asks whether there is an adjacent satisfying assignments
for $\varphi$ between two given satisfying assignments $\phi_{s}$ and
$\phi_{t}$. We will slightly modify their reduction to prove the
${\mathtt{PSPACE}}$-hardness for $d\geq 3$.

We first describe the reduction by Ito et al. [ItoDHPSUU11]. Let $\varphi$ be
a given 3SAT formula. We construct a graph $G$ as follows. For each variable
$x_{i}$ ($1\leq i\leq n$) in $\varphi$, we add an edge $e_{x_{i}}$ to the
graph; its two endpoints are labeled $x_{i}$ and $\overline{x_{i}}$. Then, for
each clause $c_{j}$ ($1\leq j\leq m$) in $\varphi$, we add a clique whose
nodes correspond to literals in $c_{j}$. Finally, we add an edge between two
nodes in different components if and only if the nodes correspond to opposite
literals. Ito et al. [ItoDHPSUU11] proved that there is a one-to-one
correspondence between satisfying assignments for $\varphi$ and maximum
independent sets of size $n+m$ in $G$: $n$ vertices are chosen from the
endpoints of edges corresponding to the variables; a literal is $1$ (true) if
the corresponding endpoint is chosen. They uses this observation to show that
there is a sequence of adjacent satisfying assignments between $\phi_{s}$ and
$\phi_{t}$ if and only if there is a ${\mathsf{TJ}}$-sequence between two
corresponding size-$(n+m)$ independent sets of $G$. (Indeed, they proved under
${\mathsf{TAR}}$ rule. However, since only independent sets of size at least
$n+m-1$ are used, any ${\mathsf{TAR}}$-sequence in $G$ can be converted into a
${\mathsf{TJ}}$-sequence [KaminskiMM12], the result under ${\mathsf{TJ}}$ also
holds.)

$\overline{x_{1}}$$x_{1}$$\overline{x_{2}}$$x_{2}$$\overline{x_{3}}$$x_{3}$$x_{1}$$\overline{x_{2}}$$\overline{x_{1}}$$x_{3}$$x_{2}$$\overline{x_{2}}$$\overline{x_{3}}$

Figure 4: An example of constructing the graphs $G$ and ${G^{\prime}}$ from a
3SAT formula $\varphi$ used in [ItoDHPSUU11] having three variables $x_{1}$,
$x_{2}$, and $x_{3}$ and three clauses $c_{1}=\\{x_{1},\overline{x_{2}}\\}$,
$c_{2}=\\{\overline{x_{1}},x_{2},x_{3}\\}$, and
$c_{3}=\\{\overline{x_{2}},\overline{x_{3}}\\}$. Paths of length $d-1$ are
represented by dotted edges.

Our modification is simple. Instead of joining two nodes in different
components by an edge, we join them by a path of length $d-1$. Let
${G^{\prime}}$ be the resulting graph. Figure 4 describes an example of
constructing ${G^{\prime}}$ from the same 3SAT formula used by Ito et al.
[ItoDHPSUU11]. Indeed, when $d=2$, our constructed graph ${G^{\prime}}$ and
the graph $G$ constructed by Ito et al. are identical. One can verify that any
independent set of $G$ of size $n+m$ is also a D$d$IS of ${G^{\prime}}$.
Additionally, note that no token can ever leave its corresponding component.
To see this, choose a token $t$ and assume inductively that the statement
holds for all other tokens, then $t$ can never jump/slide to any vertex
outside its corresponding component because some other token must be moved
first in order to make room for $t$. Thus, any token-jump is also a token-
slide. (Recall that each component is either a single vertex, an edge, or a
triangle.) Hence, $(G,I,J,{\mathsf{R}})$ is a yes-instance of ISR if and only
if $({G^{\prime}},I,J,{\mathsf{R}})$ is a yes-instance of D$d$ISR, where $I$
and $J$ are size-$(n+m)$ independent sets of $G$ (which are also D$d$ISs of
${G^{\prime}}$) and ${\mathsf{R}}\in\\{{\mathsf{TS}},{\mathsf{TJ}}\\}$. Our
proof is complete. ∎

###  6.2 Perfect Graphs

In this section, we prove the ${\mathtt{PSPACE}}$-completeness of D$d$ISR
($d\geq 3$) on perfect graphs by extending the corresponding known result for
ISR of Kamiński et al. [KaminskiMM12].

######  Theorem 6.2.

D$d$ISR is ${\mathtt{PSPACE}}$-complete on perfect graphs under
${\mathsf{R}}\in\\{{\mathsf{TS}},{\mathsf{TJ}}\\}$ for any $d\geq 3$.

  * Proof.

Recall that Kamiński et al. [KaminskiMM12] proved the
${\mathtt{PSPACE}}$-hardness of the problem for $d=2$ by reducing from a known
${\mathtt{PSPACE}}$-complete problem called Shortest Path Reconfiguration
(SPR) [Bonsma13]. In a SPR’s instance $(G,u,v,P,Q)$, two shortest $uv$-paths
are adjacent if one can be obtained from the other by exchanging exactly one
vertex. The SPR problem asks whether there is a sequence of adjacent shortest
$uv$-paths between $P$ and $Q$. We will slightly modify their reduction to
prove the ${\mathtt{PSPACE}}$-hardness for $d\geq 3$.

We first describe the reduction by Kamiński et al. [KaminskiMM12]. Let $G$ be
a given graph and let $u,v\in V(G)$. We delete all vertices and edges that
does not appear in any shortest $uv$-path and let the resulting graph be
${\widetilde{G}}$. Let $k=\mathsf{dist}_{G}(u,v)$ and for each
$i\in\\{0,\dots,k\\}$ let $D_{i}$ be the set of vertices in ${\widetilde{G}}$
of distance $i$ from $u$ and $k-i$ from $v$. Let ${G^{\prime}}$ be the graph
obtained from ${\widetilde{G}}$ by turning each $D_{i}$ into a clique and
complementing (i.e., if there is an edge between two vertices, remove it;
otherwise, create one) the edges of ${\widetilde{G}}$ between two consecutive
layers $D_{i}$ and $D_{i+1}$. Kamiński et al. [KaminskiMM12] proved that
$G^{\prime}$ is a perfect graph. They also claimed that there is a one-to-one
correspondence between $uv$-shortest paths of $G$ and independent sets of size
$k+1$ of ${G^{\prime}}$: the $k+1$ vertices of a shortest $uv$-path in $G$
become independent in ${G^{\prime}}$. This is used for showing that there is a
sequence of adjacent $uv$-shortest paths in $G$ if and only if there is a
${\mathsf{R}}$-sequence between size-$(k+1)$ independent sets of $G^{\prime}$,
for ${\mathsf{R}}\in\\{{\mathsf{TS}},{\mathsf{TJ}},{\mathsf{TAR}}\\}$.

Our modification is simple. We construct a graph ${G^{\prime\prime}}$ from
${G^{\prime}}$ as follows. First, we replace each edge between two consecutive
layers $D_{i}$ and $D_{i+1}$ by a new path of length $d-1$, and let the
resulting graph be $\widetilde{{G^{\prime}}}$. For each
$j\in\\{1,\dots,d-2\\}$, let $D_{i}^{j}$ be the set of vertices in
$\widetilde{{G^{\prime}}}$ of distance $j$ from some vertex in $D_{i}$ and
distance $d-1-j$ from some vertex in $D_{i+1}$. Let ${G^{\prime\prime}}$ be
the graph obtained from $\widetilde{{G^{\prime}}}$ by turning each $D_{i}^{j}$
into a clique. Since ${G^{\prime}}$ is perfect, the above construction implies
that ${G^{\prime\prime}}$ is perfect too. Clearly the construction of both
${G^{\prime}}$ and ${G^{\prime\prime}}$ can be done in polynomial time. In
fact, if $d=2$, we have ${G^{\prime\prime}}={G^{\prime}}$. (For example, see
Figure 5.)

$D_{0}$$D_{1}$$D_{2}$$D_{3}$$D_{4}$$D_{5}$$D_{0}$$D_{1}$$D_{2}$$D_{3}$$D_{4}$$D_{5}$$D_{1}^{1}$$D_{2}^{1}$$D_{3}^{1}$$u$$v$${\widetilde{G}}$$u$$v$${G^{\prime}}$
($d=2$)$u$$v$${G^{\prime\prime}}$ ($d=3$)

Figure 5: An example of constructing the perfect graphs ${G^{\prime}}$ and
${G^{\prime\prime}}$ from ${\widetilde{G}}$. Vertices in a light-gray box form
a clique. Vertices in $V({G^{\prime\prime}})-V({G^{\prime}})$ are marked with
the gray color.

It is sufficient to show that there is a ${\mathsf{R}}$-sequence of
size-$(k+1)$ independent sets in ${G^{\prime}}$ if and only if there is a
${\mathsf{R}}$-sequence of size-$(k+1)$ distance-$d$ independent sets in
${G^{\prime\prime}}$, for ${\mathsf{R}}\in\\{{\mathsf{TS}},{\mathsf{TJ}}\\}$.
From the construction of ${G^{\prime\prime}}$, it follows that any independent
set of ${G^{\prime}}$ of size $k+1$ is also a distance-$d$ independent set of
${G^{\prime\prime}}$, since a shortest path of length $2$ in ${G^{\prime}}$
between two vertices $x\in D_{i}$ and $y\in D_{i+1}$ becomes a shortest path
of length $(d-1)+1=d$ in ${G^{\prime\prime}}$. Thus, any
${\mathsf{TJ}}$-sequence in ${G^{\prime}}$ between two size-$(k+1)$
independent sets is also a ${\mathsf{TJ}}$-sequence in ${G^{\prime\prime}}$.
On the other hand, note that a size-$(k+1)$ distance-$d$ independent set of
${G^{\prime\prime}}$ must not contain any new vertex in
$V({G^{\prime\prime}})-V({G^{\prime}})$, otherwise one can verify that the set
must be of size at most $k$, which is a contradiction. (Note that a D$d$IS
must contain at most one vertex in $\bigcup_{j=1}^{d-2}D_{i}^{j}$.) As a
result, a size-$(k+1)$ distance-$d$ independent set of ${G^{\prime\prime}}$ is
also an independent set of ${G^{\prime}}$. Thus, any ${\mathsf{TJ}}$-sequence
in ${G^{\prime\prime}}$ between two size-$(k+1)$ distance-$d$ independent sets
is also a ${\mathsf{TJ}}$-sequence in ${G^{\prime\prime}}$. We note that in
both ${G^{\prime}}$ and ${G^{\prime\prime}}$, a token can never move out of
the layer where it belongs, and therefore any token-jump is also a token-
slide. Our proof is complete. ∎

###  6.3 Planar Graphs

In this section, we claim that the ${\mathtt{PSPACE}}$-hard reduction of Hearn
and Demaine [HearnD05] for ISR under ${\mathsf{TS}}$ can be extended to
D$d$ISR ($d\geq 3$) under ${\mathsf{R}}\in\\{{\mathsf{TS}},{\mathsf{TJ}}\\}$.
We now briefly introduce the powerful tool Hearn and Demaine [HearnD05,
HearnD09] used as the source problem for proving several hardness results,
including the ${\mathtt{PSPACE}}$-hardness of ISR: the Nondeterministic
Constraint Logic (NCL) machine.

$D_{0}$$D_{1}$$D_{2}$$D_{3}$$D_{4}$$D_{5}$$D_{0}$$D_{1}$$D_{2}$$D_{3}$$D_{4}$$D_{5}$$D_{1}^{1}$$D_{2}^{1}$$D_{3}^{1}$222222111(a)112(b)222(c)

Figure 6: (a) A configuration of an NCL machine, (b) NCL And vertex, and (c)
NCL Or vertex. Edges of weight $1$ (resp., $2$) are thin (resp., thick).

An NCL “machine” is an undirected graph whose edges are assigned with weight
$1$ (thin) or $2$ (thick). An (_NCL_) _configuration_ of this machine is an
orientation of the edges such that the sum of weights of in-coming arcs at
each vertex is at least two. Figure 6(a) illustrates a configuration of an NCL
machine. Two NCL configurations are _adjacent_ if they differ in a single edge
direction. Given an NCL machine along with two configurations, Hearn and
Demaine [HearnD05] proved that it is ${\mathtt{PSPACE}}$-complete to determine
whether there exists a sequence of adjacent NCL configurations which
transforms one into the other.

Indeed, even when restricted to _And /Or constraint graphs_, the above problem
remains ${\mathtt{PSPACE}}$-complete. An _And /Or constraint graph_ is a NCL
machine that contains exactly two type of vertices: “NCL And vertices” and
“NCL Or vertices”.

More precisely, a vertex of degree three is called an _NCL And vertex_ if its
three incident edges have weights $1$, $1$ and $2$. (See Figure 6(b).) The
“behavior” of an NCL And vertex $u$ is similar to a logical and: the
weight-$2$ edge can be directed outward for $u$ if and only if both two
weight-$1$ edges are directed inward for $u$. Note that, however, the
weight-$2$ edge is not necessarily directed outward even when both weight-$1$
edges are directed inward. A vertex of degree three is called an _NCL Or
vertex_ if its three incident edges have weights $2$, $2$ and $2$. (See Figure
6(c).) The “behavior” of an NCL Or vertex $v$ is similar to a logical or: one
of the three edges can be directed outward for $v$ if and only if at least one
of the other two edges is directed inward for $v$.

For example, the NCL machine in Figure 6(a) is an And/Or constraint graph.

######  Theorem 6.3.

D$d$ISR is ${\mathtt{PSPACE}}$-complete under
${\mathsf{R}}\in\\{{\mathsf{TS}},{\mathsf{TJ}}\\}$ on planar graphs of maximum
degree three and bounded bandwidth for any $d\geq 2$.

  * Proof.

We note that Hearn and Demaine [HearnD05]’s proof can be applied with the
vertex gadgets shown in Figure 7. Indeed, when $d=2$, the gadgets in Figure 7
are exactly those used in [HearnD05]. We rephrase their proof here for the
sake of completeness. From now on we consider only ${\mathsf{TS}}$ rule. We
will see later that in the constructed graph, any token-jump is also a token-
slide, and therefore our reduction also holds for ${\mathsf{TJ}}$. The maximum
degree will also be clear from the construction of gadgets and how they are
joined. The final complexity result follows from the result of van der Zanden
[Zanden15] which combines [HearnD05] and [Wrochna18]: NCL remains
${\mathtt{PSPACE}}$-complete even if an input NCL machine is planar and
bounded bandwidth.

The NCL And and Or vertex gadgets are constructed as in Figure 7(a) and (b).
The edges that cross the dashed-line gadget borders are “port” edges. A token
on an outer port-edge vertex represents an inward-directed NCL edge, and vice
versa. Given an And/Or graph and configuration, we construct a corresponding
graph for D$d$ISR under ${\mathsf{TS}}$, by joining together And and Or vertex
gadgets at their shared port edges, placing the port tokens appropriately.

$D_{0}$$D_{1}$$D_{2}$$D_{3}$$D_{4}$$D_{5}$$D_{0}$$D_{1}$$D_{2}$$D_{3}$$D_{4}$$D_{5}$$D_{1}^{1}$$D_{2}^{1}$$D_{3}^{1}$(a)(b)

Figure 7: Vertex gadgets for D$d$ISR under ${\mathsf{TS}}$: (a) And, (b) Or.
The dotted edges represent paths of length $d-2$.

First, observe that no port token may ever leave its port edge. Choosing a
particular port edge $E$, if we inductively assume that this condition holds
for all other port edges, then there is never a legal move outside $E$ for its
token—another port token would have to leave its own edge first.

The And gadget clearly satisfies the same constraints as an NCL And vertex;
the upper token can slide in just when both lower tokens are slid out.
Likewise, the upper token in the Or gadget can slide in when either lower
token is slid out—the internal token can then slide to one side or the other
to make room. It thus satisfies the same constraints as an NCL Or vertex. As a
result, it follows that a sequence of adjacent NCL configurations in a given
And/Or graph can indeed be transformed into a ${\mathsf{TS}}$-sequence in the
constructed graph and vice versa. Since no port token ever leaves its port
edge, it follows from the construction of gadgets that in the constructed
graph any token-jump is also a token-slide, which means the theorem also holds
for ${\mathsf{TJ}}$. Our proof is complete. ∎

##  7 Open Problem: Trees

In this section, we discuss the problems on trees. Since the power of a tree
is a (strongly) chordal graph [LinS95, KearneyC98] and ISR on chordal graphs
under ${\mathsf{TJ}}$ is in ${\mathtt{P}}$ [KaminskiMM12], Proposition 3.1
implies that the following corollary holds.

######  Corollary 7.1.

D$d$ISR under ${\mathsf{TJ}}$ on trees is in ${\mathtt{P}}$ for any $d\geq 3$.

On the other hand, the complexity of D$d$ISR under ${\mathsf{TS}}$ for $d\geq
3$ remains unknown.

######  Conjecture 7.2.

D$d$ISR under ${\mathsf{TS}}$ on trees is in ${\mathtt{P}}$ for $d\geq 3$.

Demaine et al. [DemaineDFHIOOUY15] showed that the problem for $d=2$ can be
solved in linear time. Their algorithm is based on the so-called rigid tokens.
Given a tree $T$ and a D$d$IS $I$ of $T$ ($d\geq 2$), a token $t$ on $u\in I$
is $(T,I,d)$-rigid if there is no ${\mathsf{TS}}$-sequence in $T$ that slides
$t$ from $u$ to some vertex $v\in N_{T}(u)$. We denote by
${\mathcal{R}}(T,I,d)$ the set of all vertices where $(T,I,d)$-rigid tokens
are placed. Demaine et al. proved that ${\mathcal{R}}(T,I,2)$ can be found in
linear time. (In general, deciding whether a token is $(G,I,2)$-rigid on some
graph $G$ is ${\mathtt{PSPACE}}$-complete [Fox-EpsteinHOU15].) Clearly, it
holds for any $d\geq 2$ that every D$d$ISR’s instance $(T,I,J,{\mathsf{TS}})$
where ${\mathcal{R}}(T,I,d)\neq{\mathcal{R}}(T,J,d)$ is a no-instance. When
${\mathcal{R}}(T,I,2)={\mathcal{R}}(T,J,2)=\emptyset$, they proved that
$(T,I,J,{\mathsf{TS}})$ is always a yes-instance of ISR. Based on these
observations, one can derive a polynomial-time algorithm for solving ISR on
trees under ${\mathsf{TS}}$.

Indeed, one can extend the recursive characterization of $(T,I,2)$-rigid
tokens given by Demaine et al. as follows. For a given vertex $u$ of a graph
$G$ and an integer $s\geq 0$, we denote by $N^{s}_{G}(u)$ the $s$-neighborhood
of $u$ in $G$ which contains all vertices of distance exactly $s$ from $u$ in
$G$. Additionally, we denote by $N^{s}_{G}[u]=\bigcup_{i=0}^{s}N^{i}_{G}(u)$
the set of all vertices of distance at most $s$ from $u$ in $G$ and called it
the s-closed neighborhood of $u$ in $G$. For example, $N^{0}_{G}(u)=\\{u\\}$,
$N^{1}_{G}(u)=N_{G}(u)$, and $N^{1}_{G}[u]=N_{G}[u]$. For two vertices $u,v$
of a tree $T$, we denote by $T^{u}_{v}$ the tree induced by $v$ and its
descendants when regarding $u$ as the root of $T$.

######  Lemma 7.3.

Let $I$ be a D$d$IS of a tree $T$ for $d\geq 2$ and let $u\in I$. The token
$t$ on $u$ is $(T,I,d)$-rigid if and only if

  1. (a)

$|V(T)|=|\\{u\\}|=1$; or

  2. (b)

$|V(T)|\geq 2$ and for each $v\in N_{T}(u)$ there exists a vertex
$w\in(N^{d-1}_{T}(v)-u)\cap I$ such that the token $t_{w}$ on $w$ is
$(T^{v}_{w},I\cap V(T^{v}_{w}),d)$-rigid.

  * Proof.

Our proof is analogous to the one given by Demaine et al. [DemaineDFHIOOUY15,
Lemma 1]. For the sake of completeness, we present it here. Part (a) is
trivial. We prove part (b). Before going into more details, we note that for
any $w\in(N^{d-1}_{T}(v)-u)$, if $w\notin V(T^{u}_{v})$ then
$\mathsf{dist}_{T}(w,u)\leq d-2$ and therefore $w\notin I$. In other words,
$(N^{d-1}_{T}(v)-u)\cap I\subseteq V(T^{u}_{v})$.

    * ($\Leftarrow$)

Suppose to the contrary that there exists a ${\mathsf{TS}}$-sequence that
slides $t$ to some vertex $v\in N_{T}(u)$. On the other hand, from the
assumption, there exists a vertex $w\in(N^{d-1}_{T}(v)-u)\cap I$ such that the
token $t_{w}$ on $w$ is $(T^{v}_{w},I\cap V(T^{v}_{w}),d)$-rigid. Since
$\mathsf{dist}_{T}(u,w)=d$, $t_{w}$ must be moved before $t$ and therefore can
only be moved to some vertex in $T^{v}_{w}$. However, since the token $t_{w}$
on $w$ is $(T^{v}_{w},I\cap V(T^{v}_{w}),d)$-rigid, this cannot be done. The
reason is that if there is a ${\mathsf{TS}}$-sequence ${\mathcal{S}}$ in $T$
that slides $t_{w}$, we can “restrict” it to a ${\mathsf{TS}}$-sequence in
$T^{v}_{w}$ by taking the intersection of each independent set in
${\mathcal{S}}$ with $V(T^{v}_{w})$, which implies $t_{w}$ is
$(T^{v}_{w},I\cap V(T^{v}_{w}),d)$-movable.

    * ($\Rightarrow$)

Suppose that $|V(T)|\geq 2$. We claim that if there exists $v\in N_{T}(u)$
such that either $(N^{d-1}_{T}(v)-u)\cap I=\emptyset$ or for every
$w\in(N^{d-1}_{T}(v)-u)\cap I$, the token $t_{w}$ on $w$ is $(T^{v}_{w},I\cap
V(T^{v}_{w}),d)$-movable then there exists a ${\mathsf{TS}}$-sequence
${\mathcal{S}}$ in $T$ that moves the token $t$ on $u$ to $v$. If
$(N^{d-1}_{T}(v)-u)\cap I=\emptyset$, there are no tokens of distance $d-1$
from $v$ except $t$, and therefore we can immediately slide $t$ to $v$. Thus,
it remains to consider the case for every $w\in(N^{d-1}_{T}(v)-u)\cap I$, the
token $t_{w}$ on $w$ is $(T^{v}_{w},I\cap V(T^{v}_{w}),d)$-movable. Since
$t_{w}$ is $(T^{v}_{w},I\cap V(T^{v}_{w}),d)$-movable, there exists a
${\mathsf{TS}}$-sequence ${\mathcal{S}}_{w}$ in $T^{v}_{w}$ that slides
$t_{w}$ to some vertex in $N_{T^{v}_{w}}(w)$. Moreover, note that for any
D$d$IS $I_{w}$ of $T^{v}_{w}$, we have $I_{w}\cup(I^{\prime}-V(T^{v}_{w}))$ is
also a D$d$IS of $T$, for any D$d$IS $I^{\prime}$ of $G$ satisfying
$I^{\prime}\cap V(T^{v}_{w})=I\cap V(T^{v}_{w})$. (Intuitively, we move tokens
“away from $w$” inside $T^{v}_{w}$. These moves do not break any “distance-$d$
restriction” between a token inside $T^{v}_{w}$ and a token outside
$T^{v}_{w}$.) In other words, one can “extend” ${\mathcal{S}}_{w}$ to form a
${\mathsf{TS}}$-sequence in $T$ by simply taking the union of each D$d$IS in
${\mathcal{S}}_{w}$ with $I^{\prime}-V(T^{v}_{w})$. Thus, for each
$w\in(N^{d-1}_{T}(v)-u)\cap I$, we can perform ${\mathcal{S}}_{w}$ to slides
$t_{w}$ to some vertex in $N_{T^{v}_{w}}(w)$ and finally slide $t$ from $u$ to
$v$. It remains to verify that for any pair of distinct vertices
$w,w^{\prime}\in(N^{d-1}_{T}(v)-u)\cap I$ we can indeed perform
${\mathcal{S}}_{w}$ and ${\mathcal{S}}_{w^{\prime}}$ independently. To see
this, note that by definition the subtrees $T^{v}_{w}$ and
$T^{v}_{w^{\prime}}$ are distinct, i.e., $V(T^{v}_{w})\cap
V(T^{v}_{w^{\prime}})=\emptyset$. Moreover, since both $w,w^{\prime}$ are in
$I$, there distance must be at least $d$.

∎

Using this characterization, one can naturally derive a recursive algorithm
that decides if the token on $u\in I$ is $(T,I,d)$-rigid in $O(n)$ time, where
$n=|V(T)|$. Therefore, one can find ${\mathcal{R}}(T,I,d)$ in $O(n^{2})$ time.

However, for $d\geq 3$, even when
${\mathcal{R}}(T,I,d)={\mathcal{R}}(T,J,d)=\emptyset$, $(T,I,J,{\mathsf{TS}})$
may be a no-instance of D$d$ISR. An example of such instances is described in
Figure 8.

$D_{0}$$D_{1}$$D_{2}$$D_{3}$$D_{4}$$D_{5}$$D_{0}$$D_{1}$$D_{2}$$D_{3}$$D_{4}$$D_{5}$$D_{1}^{1}$$D_{2}^{1}$$D_{3}^{1}$$u$

Figure 8: A no-instance $(T,I,J,{\mathsf{TS}})$ of D$d$ISR ($d\geq 3$) with
${\mathcal{R}}(T,I,d)={\mathcal{R}}(T,J,d)=\emptyset$. Tokens in $I$ (resp.
$J$) are marked with the black (resp. gray) color. All tokens are of distance
$d-1$ from $u$.

We remark that the instance described in Figure 8 does not apply for $d=2$,
because in that case no tokens can move. As a result, characterizing these no-
instances may be crucial in proving Conjecture 7.2. Additionally, a first step
toward proving Conjecture 7.2 may be to consider D$d$ISR under ${\mathsf{TS}}$
on caterpillars—a subclass of trees. Here a caterpillar is a tree having a
backbone path containing all vertices of degree at least $3$ (called backbone
vertices). Each hair of the caterpillar is a path starting from a backbone
vertex and not containing any other backbone vertex. For example, the graph in
Figure 8 is a caterpillar with the backbone path having exactly one vertex $u$
(whose degree is at least $3$) and four hairs of length exactly $d-1$ starting
from $u$.

## Acknowledgements

We thank the anonymous reviewers for their valuable comments and suggestions
which help to improve earlier versions of this paper. This research is
partially supported by the Japan Society for the Promotion of Science (JSPS)
KAKENHI Grant Number JP20H05964 (AFSA).

## References

  * [1] Valentin Bartier, Nicolas Bousquet and Moritz Mühlenthaler  “Independent set reconfiguration in $H$-free graphs” To appear  In _Proceedings of WG 2024_ , 2024  eprint: 2402.03063
  * [2] David Avis and Duc A. Hoang  “A Note On Acyclic Token Sliding Reconfiguration Graphs of Independent Sets”  In _arXiv preprint_ , 2023  arXiv:2301.00317
  * [3] David Avis and Duc A. Hoang  “On Reconfiguration Graph of Independent Sets under Token Sliding”  In _Graphs and Combinatorics_ 39.3 Springer, 2023, pp. 59  DOI: 10.1007/s00373-023-02644-w
  * [4] Nicolas Bousquet, Bastien Durain, Théo Pierron and Stéphan Thomassé  “Extremal Independent Set Reconfiguration”  In _The Electronic Journal of Combinatorics_ 30.3, 2023, pp. P3.8  DOI: 10.37236/11771
  * [5] Duc A. Hoang  “On The Complexity of Distance-$d$ Independent Set Reconfiguration”  In _Proceedings of WALCOM 2023_ 13973, LNCS, 2023, pp. 254–266  DOI: 10.1007/978-3-031-27051-2_22
  * [6] Nicolas Bousquet, Amer E. Mouawad, Naomi Nishimura and Sebastian Siebertz  “A survey on the parameterized complexity of the independent set and (connected) dominating set reconfiguration problems”  In _arXiv preprint_ , 2022  arXiv:2204.10526
  * [7] Takehiro Ito, Yuni Iwamasa, Yasuaki Kobayashi, Yu Nakahata, Yota Otachi, Masahiro Takahashi and Kunihiro Wasa  “Independent set reconfiguration on directed graphs”  In _Proceedings of MFCS 2022_ 241, LIPIcs  Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022, pp. 58:1–58:15  DOI: 10.4230/LIPIcs.MFCS.2022.58
  * [8] Rémy Belmonte, Eun Jung Kim, Michael Lampis, Valia Mitsou, Yota Otachi and Florian Sikora  “Token sliding on split graphs”  In _Theory of Computing Systems_ 65.4 Springer, 2021, pp. 662–686  DOI: 10.1007/s00224-020-09967-8
  * [9] Marcin Briański, Stefan Felsner, Jędrzej Hodor and Piotr Micek  “Reconfiguring Independent Sets on Interval Graphs”  In _Proceedings of MFCS 2021_ 202, LIPIcs  Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021, pp. 23:1–23:14  DOI: 10.4230/LIPIcs.MFCS.2021.23
  * [10] Ioannis Katsikarelis, Michael Lampis and Vangelis Th. Paschos  “Structurally parameterized $d$-scattered set”  In _Discrete Applied Mathematics_ 308 Elsevier, 2020, pp. 168–186  DOI: 10.1016/j.dam.2020.03.052
  * [11] Ioannis Katsikarelis, Michael Lampis and Vangelis Th. Paschos  “Improved (in-)approximability bounds for $d$-scattered set”  In _Proceedings of WAOA 2019_ 11926, LNCS  Springer, 2019, pp. 202–216  DOI: 10.1007/978-3-030-39479-0_14
  * [12] Daniel Lokshtanov and Amer E. Mouawad  “The complexity of independent set reconfiguration on bipartite graphs”  In _ACM Transactions on Algorithms_ 15.1 Acm, 2019, pp. 7:1–7:19  DOI: 10.1145/3280825
  * [13] C.M. Mynhardt and S. Nasserasr  “Reconfiguration of colourings and dominating sets in graphs”  In _50 years of Combinatorics, Graph Theory, and Computing_ CRC Press, 2019, pp. 171–191  DOI: 10.1201/9780429280092-10
  * [14] Katsuhisa Yamanaka, Shogo Kawaragi and Takashi Hirayama  “Exact Exponential Algorithm for Distance-3 Independent Set Problem”  In _IEICE Transactions on Information and Systems_ 102.3 The Institute of Electronics, InformationCommunication Engineers, 2019, pp. 499–501  DOI: 10.1587/transinf.2018FCL0002
  * [15] Sangram K. Jena, Ramesh K. Jallu, Gautam K. Das and Subhas C. Nandy  “The maximum distance-$d$ independent set problem on unit disk graphs”  In _Proceedings of FAW 2018_ 10823, LNCS  Springer, 2018, pp. 68–80  DOI: 10.1007/978-3-319-78455-7_6
  * [16] Naomi Nishimura  “Introduction to reconfiguration” (article 52)  In _Algorithms_ 11.4, 2018  DOI: 10.3390/a11040052
  * [17] Sebastian Siebertz  “Reconfiguration on nowhere dense graph classes” (article P3.24)  In _The Electronic Journal of Combinatorics_ 25.3, 2018  DOI: 10.37236/7458
  * [18] Marcin Wrochna  “Reconfiguration in bounded bandwidth and treedepth”  In _Journal of Computer and System Sciences_ 93, 2018, pp. 1–10  DOI: 10.1016/j.jcss.2017.11.003
  * [19] Marthe Bonamy and Nicolas Bousquet  “Token sliding on chordal graphs”  In _Proceedings of WG 2017_ 10520, LNCS  Springer, 2017, pp. 127–139  DOI: 10.1007/978-3-319-68705-6_10
  * [20] Reinhard Diestel  “Graph Theory” 173, Graduate Texts in Mathematics  Springer, 2017  DOI: 10.1007/978-3-662-53622-3
  * [21] Paul S. Bonsma  “Independent set reconfiguration in cographs and their generalizations”  In _Journal of Graph Theory_ 83.2, 2016, pp. 164–195  DOI: 10.1002/jgt.21992
  * [22] Pedro Montealegre and Ioan Todinca  “On distance-$d$ independent set and other problems in graphs with “few” minimal separators”  In _Proceedings of WG 2016_ 9941, LNCS  Springer, 2016, pp. 183–194  DOI: 10.1007/978-3-662-53536-3_16
  * [23] Erik D. Demaine, Martin L. Demaine, Eli Fox-Epstein, Duc A. Hoang, Takehiro Ito, Hirotaka Ono, Yota Otachi, Ryuhei Uehara and Takeshi Yamada  “Linear-time algorithm for sliding tokens on trees”  In _Theoretical Computer Science_ 600, 2015, pp. 132–142  DOI: 10.1016/j.tcs.2015.07.037
  * [24] Eli Fox-Epstein, Duc A. Hoang, Yota Otachi and Ryuhei Uehara  “Sliding token on bipartite permutation graphs”  In _Proceedings of ISAAC 2015_ 9472, LNCS  Springer, 2015, pp. 237–247  DOI: 10.1007/978-3-662-48971-0_21
  * [25] Daniel Lokshtanov, Amer E. Mouawad, Fahad Panolan, M.. Ramanujan and Saket Saurabh  “Reconfiguration on Sparse Graphs”  In _Proceedings of WADS 2015_ 9214, LNCS  Springer, 2015, pp. 506–517  DOI: 10.1007/978-3-319-21840-3_42
  * [26] Tom C. van der Zanden  “Parameterized complexity of graph constraint logic”  In _Proceedings of IPEC 2015_ 43, LIPIcs  Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2015, pp. 282–293  DOI: 10.4230/LIPIcs.IPEC.2015.282
  * [27] Paul S. Bonsma, Marcin Kamiński and Marcin Wrochna  “Reconfiguring independent sets in claw-free graphs”  In _Proceedings of SWAT 2014_ 8503, LNCS  Springer, 2014, pp. 86–97  DOI: 10.1007/978-3-319-08404-6_8
  * [28] Hiroshi Eto, Fengrui Guo and Eiji Miyano  “Distance-$d$ independent set problems for bipartite and chordal graphs”  In _Journal of Combinatorial Optimization_ 27.1 Springer, 2014, pp. 88–99  DOI: 10.1007/s10878-012-9594-4
  * [29] Paul S. Bonsma  “The complexity of rerouting shortest paths”  In _Theoretical Computer Science_ 510, 2013, pp. 1–12  DOI: 10.1016/j.tcs.2013.09.012
  * [30] Jan van den Heuvel  “The complexity of change”  In _Surveys in Combinatorics_ 409, London Math. Soc. Lecture Note Ser.  Cambridge University Press, 2013, pp. 127–160  DOI: 10.1017/CBO9781139506748.005
  * [31] Marcin Kamiński, Paul Medvedev and Martin Milanič  “Complexity of independent set reconfigurability problems”  In _Theoretical Computer Science_ 439, 2012, pp. 9–15  DOI: 10.1016/j.tcs.2012.03.004
  * [32] Takehiro Ito, Erik D. Demaine, Nicholas J.. Harvey, Christos H. Papadimitriou, Martha Sideri, Ryuhei Uehara and Yushi Uno  “On the complexity of reconfiguration problems”  In _Theoretical Computer Science_ 412.12-14, 2011, pp. 1054–1065  DOI: 10.1016/j.tcs.2010.12.005
  * [33] Parikshit Gopalan, Phokion G. Kolaitis, Elitza N. Maneva and Christos H. Papadimitriou  “The connectivity of Boolean satisfiability: computational and structural dichotomies”  In _SIAM Journal on Computing_ 38.6, 2009, pp. 2330–2355  DOI: 10.1137/07070440x
  * [34] Robert A. Hearn and Erik D. Demaine  “Games, puzzles, and computation”  CRC Press, 2009
  * [35] Robert A. Hearn and Erik D. Demaine  “PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation”  In _Theoretical Computer Science_ 343.1-2, 2005, pp. 72–96  DOI: 10.1016/j.tcs.2005.05.008
  * [36] Geir Agnarsson, Peter Damaschke and Magnús M. Halldórsson  “Powers of geometric intersection graphs and dispersion algorithms”  In _Discrete Applied Mathematics_ 132.1-3 Elsevier, 2003, pp. 3–16  DOI: 10.1016/S0166-218X(03)00386-X
  * [37] Mingjang Chen and Gerard J. Chang  “Families of graphs closed under taking powers”  In _Graphs and Combinatorics_ 17.2 Springer, 2001, pp. 207–212  DOI: 10.1007/PL00007241
  * [38] Geir Agnarsson, Raymond Greenlaw and Magnús M. Halldórsson  “On powers of chordal graphs and their colorings”  In _Congressus Numerantium_ 144, 2000, pp. 41–65
  * [39] M. Kong and Y. Zhao  “Computing $k$-Independent sets for regular bipartite graphs”  In _Congressus Numerantium_ 143, 2000, pp. 65–80
  * [40] Paul E. Kearney and Derek G. Corneil  “Tree powers”  In _Journal of Algorithms_ 29.1 Elsevier, 1998, pp. 111–131  DOI: 10.1006/jagm.1998.9999
  * [41] Yaw-Ling Lin and Steven S Skiena  “Algorithms for square roots of graphs”  In _SIAM Journal on Discrete Mathematics_ 8.1 SIAM, 1995, pp. 99–118  DOI: 10.1137/S089548019120016X
  * [42] M. Kong and Y. Zhao  “On computing maximum $k$-independent sets”  In _Congressus Numerantium_ 95, 1993, pp. 47–47
  * [43] R. Balakrishnan and P. Paulraja  “Powers of chordal graphs”  In _Journal of the Australian Mathematical Society_ 35.2 Cambridge University Press, 1983, pp. 211–217  DOI: 10.1017/S1446788700025696
  * [44] Michael R. Garey and David S. Johnson  “Computers and intractability: A guide to the theory of NP-completeness”  W.H. FreemanCompany, 1979