Reconfiguring spanning and induced subgraphs∗
Tesshu Hanaka†

Takehiro Ito‡

Naomi Nishimura§

Haruka Mizuta‡

Vijay Subramanya§

Benjamin Moore§
Akira Suzuki‡

arXiv:1803.06074v1 [] 16 Mar 2018

Krishna Vaidyanathan§
March 19, 2018

Abstract
Subgraph reconfiguration is a family of problems focusing on the reachability of the
solution space in which feasible solutions are subgraphs, represented either as sets of vertices
or sets of edges, satisfying a prescribed graph structure property. Although there has been
previous work that can be categorized as subgraph reconfiguration, most of the related
results appear under the name of the property under consideration; for example, independent
set, clique, and matching. In this paper, we systematically clarify the complexity status of
subgraph reconfiguration with respect to graph structure properties.

1

Introduction

Combinatorial reconfiguration [6, 5, 11] studies the reachability/connectivity of the solution space
formed by feasible solutions of an instance of a search problem. More specifically, consider a graph
such that each node in the graph represents a feasible solution to an instance of a search problem
P , and there is an edge between nodes representing any two feasible solutions that are “adjacent,”
according to a prescribed reconfiguration rule A; such a graph is called the reconfiguration graph
for P and A. In the reachability problem for P and A, we are given source and target solutions
to P , and the goal is to determine whether or not there is a path between the two corresponding
nodes in the reconfiguration graph for P and A. We call a desired path a reconfiguration sequence
between source and target solutions, where a reconfiguration step from one solution to another
corresponds to an edge in the path.

1.1

Subgraph reconfiguration

In this paper, we use the term subgraph reconfiguration to describe a family of reachability
problems that take subgraphs (more accurately, vertex subsets or edge subsets of a given graph)
as feasible solutions. Each of the individual problems in the family can be defined by specifying
the node set and the edge set of a reconfiguration graph, as follows. (We use the terms node for
reconfiguration graphs and vertex for input graphs.)
Nodes of a reconfiguration graph. The set of feasible solutions (i.e., subgraphs) can be defined
in terms of a specified graph structure property Π which subgraphs must satisfy; for example, “a
graph is a tree,” “a graph is edgeless (an independent set),” and so on. By the choice of how
∗ This work is partially supported by JST ERATO Grant Number JPMJER1201, JST CREST Grant Number
JPMJCR1402, and JSPS KAKENHI Grant Numbers JP16K00004 and JP17K12636, Japan. Research by Canadian
authors is supported by the Natural Science and Engineering Research Council of Canada.
† Kyushu University, Fukuoka, Japan, 3EC15004S@s.kyushu-u.ac.jp
‡ Tohoku University, Sendai, Japan, takehiro@ecei.tohoku.ac.jp, haruka.mizuta.s4@dc.tohoku.ac.jp,
a.suzuki@ecei.tohoku.ac.jp
§ University of Waterloo, Waterloo, Canada, {brmoore, nishi, v7subram, kvaidyan}@uwaterloo.ca

1

Table 1: Subgraph representations and variants
Subgraph representations
Variant names
Known reachability problems
edge subset
edge
spanning tree [6]
matching [6, 10], and b-matching [10]
clique [7]
independent set [6, 8]
vertex subset
induced
induced forest [9]
induced bipartite [9]
induced tree [12]
spanning
clique [7]

Es = E0

E1

E2

E3 = Et

Figure 1: A reconfiguration sequence hE0 , E1 , E2 , E3 i in the edge variant under the TJ rule (also
under the TS rule) with the property “a graph is a path,” where the edges forming solutions are
depicted by thick lines.
to represent subgraphs, each specific problem in the family can be categorized into one of three
variants. (See also Table 1.) If a subgraph is represented as an edge subset, which we will call the
edge variant, then the subgraph formed (induced) by the edge subset must satisfy Π. For example,
Figure 1 illustrates four subgraphs represented as edge subsets, where Π is “a graph is a path.”
On the other hand, if a subgraph is represented as a vertex subset, we can opt either to require
that the subgraph induced by the vertex subset satisfies Π or that the subgraph induced by the
vertex subset contains at least one spanning subgraph that satisfies Π; we will refer to these as the
induced variant and spanning variant, respectively. For example, if Π is “a graph is a path,” then
in the induced variant, the vertex subset must induce a path, whereas in the spanning variant, the
vertex subset is feasible if its induced subgraph contains at least one Hamiltonian path. Figure 2
illustrates feasible vertex subsets of the induced variant and spanning variant. In the figure, the
vertex subset V1′ is feasible in the spanning variant, but is not feasible in the induced variant,
because it contains a spanning path but does not induce a path. As can be seen by this simple
example, in the spanning variant, we need to pay attention to the additional complexity of finding
a spanning subgraph and the complications resulting from the fact that the subgraph induced by
the vertex subset may contain more than one spanning subgraph which satisfies Π.
Edges of a reconfiguration graph. Since we represent a feasible solution by a set of vertices
(or edges) in any variant, we can consider that tokens are placed on each vertex (resp., edge) in
the feasible solution. Then, in this paper, we mainly deal with the two well-known reconfiguration
rules, called the token-jumping (TJ) [8] and token-sliding (TS) rules [2, 4, 8]. In the former, a
token can move to any other vertex (edge) in a given graph, whereas in the latter it can move only
to an adjacent vertex (adjacent edge, that is sharing a common vertex.) For example, Figure 1
and Figure 2 illustrate reconfiguration sequences under the TJ rule for each variant. Note that the
sequence in Figure 1 can also be considered as a sequence under the TS rule. In the reconfiguration
graph, two nodes are adjacent if and only if one of the two corresponding solutions can be obtained
from the other one by a single move of one token that follows the specified reconfiguration rule.
Therefore, all nodes in a connected component of the reconfiguration graph represent subgraphs
having the same number of vertices (edges).
We note in passing that since in most cases we wish to retain the same number of vertices
and/or edges, we rarely use the token-addition-and-removal (TAR) rule [6, 8], where we can add
or remove a single token at a time, for subgraph reconfiguration problems.
2

Vs = V0

V1

V2

V3

V4 = Vt

(a) Induced variant

Vs = V0’

V1’

V2’ = Vt

(b) Spanning variant
Figure 2: Reconfiguration sequences hV0 , V1 , V2 , V3 , V4 i in the induced variant under the TJ rule
and hV0′ , V1′ , V2′ i in the spanning variant under the TJ rule with the property “a graph is a path,”
where the vertices forming solutions are depicted by colored circles, and the subgraphs satisfying
the property by thick lines.

1.2

Previous work

Although there has been previous work that can be categorized as subgraph reconfiguration,
most of the related results appear under the name of the property Π under consideration. Accordingly, we can view reconfiguration of independent sets [6, 8] as the induced variant of subgraph
reconfiguration such that the property Π is “a graph is edgeless.” Other examples can be found
in Table 1. We here explain only known results which are directly related to our contributions.
Reconfiguration of cliques can be seen as both the spanning and the induced variant; the
problem is PSPACE-complete under any rule, even when restricted to perfect graphs [7]. Indeed,
for this problem, the rules TAR, TJ, and TS have all been shown to be equivalent from the
viewpoint of polynomial-time solvability. It is also known that reconfiguration of cliques can be
solved in polynomial time for several well-known graph classes [7].
Wasa et al. [12] considered the induced variant under the TJ and TS rules with the property
Π being “a graph is a tree.” They showed that this variant under each of the TJ and TS rules
is PSPACE-complete, and is W[1]-hard when parameterized by both the size of a solution and
the length of a reconfiguration sequence. They also gave a fixed-parameter algorithm when parameterized by both the size of a solution and the maximum degree of an input graph, under
both the TJ and TS rules. In closely related work, Mouawad et al. [9] considered the induced
variants of subgraph reconfiguration under the TAR rule with the properties Π being either
“a graph is a forest” or “a graph is bipartite.” They showed that these variants are W[1]-hard
when parameterized by the size of a solution plus the length of a reconfiguration sequence.

1.3

Our contributions

In this paper, we study the complexity of subgraph reconfiguration under the TJ and TS
rules. (Our results are summarized in Table 2, together with known results, where an (i, j)-biclique
is a complete bipartite graph with the bipartition of i vertices and j vertices.) As mentioned above,
because we consider the TJ and TS rules, it suffices to deal with subgraphs having the same number
of vertices or edges. Subgraphs of the same size may be isomorphic for certain properties Π, such
as “a graph is a path” and “a graph is a clique,” because there is only one choice of a path or
a clique of a particular size. On the other hand, for the property “a graph is a tree,” there are
several choices of trees of a particular size. (We will show an example in Section 3 with Figure 4.)
As shown in Table 2, we systematically clarify the complexity of subgraph reconfiguration
for several fundamental graph properties. In particular, we show that the edge variant under the
TJ rule is computationally intractable for the property “a graph is a path” but tractable for the

3

Property Π
path
cycle
tree

Table 2: Previous and new results
Edge
Induced
variant
variant
NP-hard (TJ)
PSPACE-c. (TJ, TS)
[Theorem 2]
[Theorems 7, 9]
P (TJ, TS)
PSPACE-c. (TJ, TS)
[Theorem 3]
[Theorems 8, 9]
P (TJ)
PSPACE-c. (TJ, TS)
[Theorem 6]
[12]

(i, j)-biclique

P (TJ, TS)
[Theorem 5]

clique

P (TJ, TS)
[Theorem 4]

diameter
two
any
property

XP for solution
size (TJ, TS)
[Theorem 1]

PSPACE-c. for i = j (TJ)
PSPACE-c. for fixed i (TJ)
[Corollary 1, Theorem 12]
PSPACE-c. (TJ, TS)
[7]
PSPACE-c. (TS)
[Theorem 15]
XP for solution
size (TJ, TS)
[Theorem 1]

Spanning
variant
PSPACE-c. (TJ, TS)
[Theorems 7, 9]
PSPACE-c. (TJ, TS)
[Theorems 8, 9]
P (TJ)
PSPACE-c. (TS)
[Theorems 11, 10]
NP-hard for i = j (TJ)
P for fixed i (TJ)
[Theorems 13, 14]
PSPACE-c. (TJ, TS)
[7]
PSPACE-c. (TS)
[Theorem 15]
XP for solution
size (TJ, TS)
[Theorem 1]

property “a graph is a tree.” This implies that the computational (in)tractability does not follow
directly from the inclusion relationship of graph classes required as the properties Π; one possible
explanation is that the path property implies a specific graph, whereas the tree property allows
several choices of trees, making the problem easier.

1.4

Preliminaries

Although we assume throughout the paper that an input graph G is simple, all our algorithms
can be easily extended to graphs having multiple edges. We denote by (G, Vs , Vt ) an instance of a
spanning variant or an induced variant whose input graph is G and source and target solutions are
vertex subsets Vs and Vt of G. Similarly, we denote by (G, Es , Et ) an instance of the edge variant.
We may assume without loss of generality that |Vs | = |Vt | holds for the spanning and induced
variants, and |Es | = |Et | holds for the edge variant; otherwise, the answer is clearly no since under
both the TJ and TS rules, all solutions must be of the same size.

2

General algorithm

In this section, we give a general XP algorithm when the size of a solution (that is, the size
of a vertex or edge subset that represents a subgraph) is taken as the parameter. For notational
convenience, we simply use element to represent a vertex (or an edge) for the spanning and induced
variants (resp., the edge variant), and candidate to represent a set of elements (which does not
necessarily satisfy the property Π.) Furthermore, we define the size of a given graph as the number
of elements in the graph.
Theorem 1. Let Π be any graph structure property, and let f (k) denote the time to check if a
candidate of size k satisfies Π. Then, all of the spanning, induced, and edge variants under the
TJ or TS rules can be solved in time O(nk+1 k + nk f (k)), where n is the size of a given graph and
k is the size of a source (and target) solution. Furthermore, a shortest reconfiguration sequence
between source and target solutions can be found in the same time bound, if it exists.
Proof. Our claim is that the reconfiguration graph can be constructed in the stated time. Since
a given source solution is of size k, it suffices to deal only with candidates of size exactly k. For
4

Ps

Pt

e1s
s1

ens
s2

sn

e1t
t1

G
sn+1

tn

e1
x
t
en+1

ent
t2

s
en+1

e2
v

e3
s

t

w

tn+1

Figure 3: Reduction to the edge variant under the TJ rule for the property “a graph is a path.”
a given graph, the total number of possible candidates of size k is O(nk ). For each candidate,
we can check in time f (k) whether it satisfies Π. Therefore, we can construct the node set of
the reconfiguration graph in time O(nk f (k)). We then obtain the edge set of the reconfiguration
graph. Notice that each node in the reconfiguration graph has O(nk) adjacent nodes, because we
can replace only a single element at a time. Therefore, we can find all pairs of adjacent nodes in
time O(nk+1 k).
In this way, we can construct the reconfiguration graph in time O(nk+1 k + nk f (k)) in total.
The reconfiguration graph consists of O(nk ) nodes and O(nk+1 k) edges. Therefore, by breadthfirst search starting from the node representing a given source solution, we can determine in time
O(nk+1 k) whether or not there exists a reconfiguration sequence between two nodes representing
the source and target solutions. Notice that if a desired reconfiguration sequence exists, then the
breadth-first search finds a shortest one.

3

Edge variants

In this section, we study the edge variant of subgraph reconfiguration for the properties of
being paths, cycles, cliques, bicliques, and trees.
We first consider the property “a graph is a path” under the TJ rule.
Theorem 2. The edge variant of subgraph reconfiguration under the TJ rule is NP-hard
for the property “a graph is a path.”
Proof. We give a polynomial-time reduction from the Hamiltonian path problem. Recall that a
Hamiltonian path in a graph G is a path that visits each vertex of G exactly once. Given a graph G
and two vertices s, t ∈ V (G) of G, the NP-complete problem Hamiltonian path is to determine
whether or not G has a Hamiltonian path which starts from s and ends in t [3].
For an instance (G, s, t) of Hamiltonian path, we construct a corresponding instance (G′ , Es , Et )
of our problem, as follows. (See also Figure 3.) Let n = |V (G)|. We first add two new vertices v and x to G with two new edges e1 = xv and e2 = vs. We then add two paths Ps =
hs1 , s2 , . . . , sn+1 , xi and Pt = ht1 , t2 , . . . , tn+1 , xi, where s1 , s2 , . . . , sn+1 and t1 , t2 , . . . , tn+1 are distinct new vertices. Each of Ps and Pt consists of n+1 edges; we denote by es1 , es2 , . . . , esn+1 the edges
s1 s2 , s2 s3 , . . . , sn+1 x in Ps , respectively, and by et1 , et2 , . . . , etn+1 the edges t1 t2 , t2 t3 , . . . , tn+1 x in
Pt , respectively. We finally add a new vertex w with an edge e3 = tw, completing the construction
of G′ . We then set Es = {es1 , es2 , . . . , esn+1 , e1 , e2 } and Et = {et1 , et2 , . . . , etn+1 , e1 , e2 }; these edge
subsets clearly form paths in G′ . We have thus constructed our corresponding instance (G′ , Es , Et )
in polynomial time.
We now prove that an instance (G, s, t) of Hamiltonian path is a yes-instance if and only if
the corresponding instance (G′ , Es , Et ) is a yes-instance.
To prove the only-if direction, we first suppose that G has a Hamiltonian path P starting from
s and ending in t. Then, we construct an actual reconfiguration sequence from Es to Et using
the edges in P . Notice that P consists of n − 1 edges. Thus, we first move the n − 1 edges
es1 , es2 , . . . , esn−1 in Es to the edges in P one by one, and then move esn to e3 . Next, we move esn+1 to
etn+1 , and then move the edges in E(P ) ∪ {e3 } to etn , etn−1 , . . . , et1 one by one. By the construction
of G′ , we know that each of the intermediate edge subsets forms a path in G′ , as required.
5

We now prove the if direction by supposing that there exists a reconfiguration sequence hEs =
E0 , E1 , . . . , Eℓ = Et i. Let Eq be the first edge subset in the sequence such that E(Pt ) ∩ Eq 6= ∅;
we claim that Eq contains a Hamiltonian path in G. First, notice that the edge in E(Pt ) ∩ Eq
is etn+1 ; otherwise the subgraph formed by Eq is disconnected. Since |Eq | = |Es | = n + 3 and
|E(Ps )| = n + 1, we can observe that Eq contains no edge in Ps ; otherwise the degree of x would
be three, or Eq would form a disconnected subgraph. Therefore, the n + 2 edges in Eq \ {etn+1 }
must be chosen from E(G) ∪ {e1 , e2 , e3 }. Since |V (G)| = n and Eq must form a path in G′ , we
know that Eq \ {etn+1 } consists of e1 , e2 , e3 and n − 1 edges in G. Thus, Eq \ {etn+1, e1 , e2 , e3 } forms
a Hamiltonian path in G starting from s and ending in t, as required.
We now consider the property “a graph is a cycle,” as follows.
Theorem 3. The edge variant of subgraph reconfiguration under each of the TJ and TS
rules can be solved in linear time for the property “a graph is a cycle.”
Proof. Let (G, Es , Et ) be a given instance. We claim that the reconfiguration graph is edgeless, in
other words, no feasible solution can be transformed at all. Then, the answer is yes if and only if
Es = Et holds; this condition can be checked in linear time.
Let E ′ be any feasible solution of G, and consider a replacement of an edge e− ∈ E ′ with an
edge e+ other than e− . Let u, v be the endpoints of e− . When we remove e− from E ′ , the resulting
edge subset E ′ \{e} forms a path whose ends are u and v. Then, to ensure that the candidate forms
a cycle, we can choose only e− = uv as e+ . This contradicts the assumption that e+ 6= e− .
The same arguments hold for the property “a graph is a clique,” and we obtain the following
theorem. We note that, for this property, both induced and spanning variants (i.e., when solutions
are represented by vertex subsets) are PSPACE-complete under any rule [7].
Theorem 4. The edge variant of subgraph reconfiguration under each of the TJ and TS
rules can be solved in linear time for the property “a graph is a clique.”
We next consider the property “a graph is an (i, j)-biclique,” as follows.
Theorem 5. The edge variant of subgraph reconfiguration under each of the TJ and TS
rules can be solved in polynomial time for the property “a graph is an (i, j)-biclique” for any pair
of positive integers i and j.
Proof. We may assume without loss of generality that i ≤ j holds. We prove the theorem in the
following three cases: Case 1: i = 1 and j ≤ 2; Case 2: i, j ≥ 2; and Case 3: i = 1 and j ≥ 3.
We first consider Case 1, which is the easiest case. In this case, any (1, j)-biclique has at most
two edges. Therefore, by Theorem 1 we can conclude that this case is solvable in polynomial time.
We then consider Case 2. We show that (G, Es , Et ) is a yes-instance if and only if Es = Et
holds. To do so, we claim that the reconfiguration graph is edgeless, in other words, no feasible
solution can be transformed at all. To see this, because i, j ≥ 2, notice that the removal of any
edge e in an (i, j)-biclique results in a bipartite graph with the same bipartition of i vertices and
j vertices. Therefore, to obtain an (i, j)-biclique by adding a single edge, we must add back the
same edge e.
We finally deal with Case 3. Notice that a (1, j)-biclique is a star with j leaves, and its center
vertex is of degree j ≥ 3. Then, we claim that (G, Es , Et ) is a yes-instance if and only if the center
vertices of stars represented by Es and Et are the same. The if direction clearly holds, because
we can always move edges in Es \ Et into ones in Et \ Es one by one. We thus prove the only-if
direction; indeed, we prove the contrapositive, that is, the answer is no if the center vertices of
stars represented by Es and Et are different. Consider such a star Ts formed by Es . Since Ts has
j ≥ 3 leaves, the removal of any edge in Es results in a star having j − 1 ≥ 2 leaves. Therefore, to
ensure that each intermediate solution is a star with j leaves, we can add only an edge of G which
is incident to the center of Ts . Thus, we cannot change the center vertex.

6

Es = E0

E1

E2 = Et

Figure 4: Reconfiguration sequence hE0 , E1 , E2 i in the edge variant under the TJ rule with the
property “a graph is a tree.”
In this way, we have proved Theorem 5. Although Case 1 takes non-linear time, our algorithm
can be easily improved (without using Theorem 1) so that it runs in linear time.
We finally consider the property “a graph is a tree” under the TJ rule. As we have mentioned
in the introduction, for this property, there are several choices of trees even of a particular size,
and a reconfiguration sequence does not necessarily consist of isomorphic trees (see Figure 4). This
“flexibility” of subgraphs may yield the contrast between Theorem 2 for the path property and the
following theorem for the tree property.
Theorem 6. The edge variant of subgraph reconfiguration under the TJ rule can be solved
in linear time for the property “a graph is a tree.”
Proof. Suppose that (G, Es , Et ) is a given instance. We may assume without loss of generality that
|Es | = |Et | ≥ 2; otherwise |Es | = |Et | ≤ 1 holds, and hence the instance is trivially a yes-instance.
We will prove below that any instance with |Es | = |Et | ≥ 2 is a yes-instance if and only if all the
edges in Es and Et are contained in the same connected component of G. Note that this condition
can be checked in linear time.
We first prove the only-if direction of our claim. Since |Es | = |Et | ≥ 2 and subgraphs always
must retain a tree structure (more specifically, they must be connected graphs), observe that we
can exchange edges only in the same connected component of G. Thus, the only-if direction follows.
To complete the proof, it suffices to prove the if direction of our claim. For notational convenience, for any feasible solution Ei we denote by Ti the tree represented by Ei , and by Vi the
vertex set of Ti . In this direction, we consider the following two cases: (a) Vs ∩ Vt = ∅, and (b)
Vs ∩ Vt 6= ∅.
We consider case (a), that is, Vs ∩ Vt = ∅. Since Ts and Tt are contained in one connected
component of G, there exists a path hv0 , v1 , . . . , vℓ i in G such that v0 ∈ Vs , vℓ ∈ Vt and vi ∈
/ Vs ∪ Vt
for all i ∈ {1, 2, . . . , ℓ − 1}. Since Ts is a tree, it has at least two degree-one vertices. Let vs
be any degree-one vertex in Vs \ {v0 }, and let es be the leaf edge of Ts incident to vs . Then,
we can exchange es with v0 v1 , and obtain another tree represented by the resulting edge subset
(Es ∪ {v0 v1 }) \ {es }. By repeatedly applying this operation along the path hv1 , v2 , . . . , vℓ i, we can
obtain a solution Ek such that Vk ∩ Vt = {vℓ } 6= ∅; this case will be considered below.
We finally consider case (b), that is, Vs ∩ Vt 6= ∅. Consider the graph (Vs ∩ Vt , Es ∩ Et ). Then,
(Vs ∩ Vt , Es ∩ Et ) is a forest, and let G′ = (V ′ , E ′ ) be a connected component (i.e., a tree) of
(Vs ∩ Vt , Es ∩ Et ) whose edge set is of maximum size. We now prove that there is a reconfiguration
sequence between Es and Et by induction on k = |Es \ E ′ | = |Et \ E ′ |. If k = 0, then Es = E ′ = Et
and hence the claim holds. We thus consider the case where k > 0 holds. Since G′ is a proper
subtree of Tt , there exists at least one edge et in Et \ E ′ such that one endpoint of et is contained in
V ′ and the other is not. We claim that there exists an edge es in Es \ E ′ which can be moved into
et , that is, the subgraph represented by the resulting edge subset (Es ∪ {et }) \ {es } forms a tree. If
both endpoints of et are contained in Vs (not just V ′ ), Es ∪ {et } contains a cycle; let C ⊆ Es ∪ {et }
be the edge set of the cycle. Since the subgraph Tt has no cycle, there exists at least one edge in
C \ Et , and we choose one of them as es . On the other hand, if just one endpoint of et is contained
in Vs , then we choose a leaf edge of Ts in Es \ E ′ as es . Note that there exists such a leaf edge since
G′ is a proper subtree of Ts . From the choice of es and et , we know the subgraph represented by
the resulting edge subset (Es ∪ {et }) \ {es } forms a tree; let Ek = (Es ∪ {et }) \ {es }. Furthermore,
since Ek ∩ Et includes E ′ ∪ {et } and the subgraph formed by E ′ ∪ {et } is connected, the subgraph
7

G

G

s2

s1

s

t

t1

s1

t2

(a)

s

t

t1

(b)

Figure 5: Reductions for the properties (a) “a graph is a path,” and (b) “a graph is a cycle.”
formed by Ek ∩ Et has a connected component whose edge set has size at least |E ′ | + 1. Therefore,
we can conclude that Ek is reconfigurable into Et by the induction hypothesis.

4

Induced and spanning variants

In this section, we deal with the induced and spanning variants where subgraphs are represented as
vertex subsets. Most of our results for these variants are hardness results, except for Theorems 11
and 14.

4.1

Path and cycle

In this subsection, we show that both induced and spanning variants under the TJ or TS rules are
PSPACE-complete for the properties “a graph is a path” and “a graph is a cycle.” All proofs in
this subsection make use of reductions that employ almost identical constructions. Therefore, we
describe the detailed proof for only one case, and give proof sketches for the other cases.
We give polynomial-time reductions from the shortest path reconfiguration problem,
which can be seen as a subgraph reconfiguration problem, defined as follows [1]. For a
simple, unweighted, and undirected graph G and two distinct vertices s, t of G, shortest path
reconfiguration is the induced (or spanning) variant of subgraph reconfiguration under
the TJ rule for the property “a graph is a shortest st-path.” Notice that there is no difference
between the induced variant and the spanning variant for this property, because any shortest path
in a simple graph forms an induced subgraph. This problem is known to be PSPACE-complete [1].
Let d be the (shortest) distance from s to t in G. For each i ∈ {0, 1, . . . , d}, we denote by
Li ⊆ V (G) the set of vertices that lie on a shortest st-path at distance i from s. Therefore, we
have L0 = {s} and Ld = {t}. We call each Li a layer. Observe that any shortest st-path contains
exactly one vertex from each layer, and we can assume without loss of generality that G has no
vertex which does not belong to any layer.
We first give the following theorem.
Theorem 7. For the property “a graph is a path,” the induced and spanning variants of subgraph
reconfiguration under the TJ rule are both PSPACE-complete on bipartite graphs.
Proof. Observe that these variants are in PSPACE. Therefore, we construct a polynomial-time
reduction from shortest path reconfiguration.
Let (G, Vs , Vt ) be an instance of shortest path reconfiguration. Since any shortest stpath contains exactly one vertex from each layer, we can assume without loss of generality that
G has no edge joining two vertices in the same layer, that is, each layer Li forms an independent
set in G. Then, G is a bipartite graph. From (G, Vs , Vt ), we construct a corresponding instance
(G′ , Vs′ , Vt′ ) for the induced and spanning variants; note that we use the same reduction for both
variants. Let G′ be the graph obtained from G by adding four new vertices s1 , s2 , t1 , t2 which are
connected with four new edges s2 s1 , s1 s, tt1 , t1 t2 . (See Figure 5(a).) Note that G′ is also bipartite.
8

We then set Vs′ = Vs ∪ {s1 , s2 , t1 , t2 } and Vt′ = Vt ∪ {s1 , s2 , t1 , t2 }. Since each of Vs and Vt induces
a shortest st-path in G, each of Vs′ and Vt′ is a feasible solution to both variants. This completes
the polynomial-time construction of the corresponding instance.
We now give the key lemma for proving the correctness of our reduction.
Lemma 1. Let V ′ ⊆ V (G′ ) be any solution for the induced or spanning variant which is reachable
by a reconfiguration sequence from Vs′ (or Vt′ ) under the TJ rule. Then, V ′ satisfies the following
two conditions:
(a) s2 , s1 , s, t, t1 , t2 ∈ V ′ ; and
(b) V ′ contains exactly one vertex from each layer of G.
Proof. We first prove that condition (a) is satisfied. Notice that both Vs′ and Vt′ satisfy this
condition. Because V ′ is reconfigurable from Vs′ or Vt′ , it suffices to show that we cannot move
any of s2 , s1 , s, t, t1 , t2 in a reconfiguration sequence starting from Vs′ or Vt′ . Suppose for sake of
contradiction that we can move at least one of s2 , s1 , s, t, t1 , t2 . Then, the first removed vertex v ∈
{s2 , s1 , s, t, t1 , t2 } must be either s2 or t2 ; otherwise the resulting subgraph would be disconnected.
Let w be the vertex with which we exchanged v. Then, w ∈ V (G′ ) \ {s2 , s1 , s, t, t1 , t2 } = V (G) \
{s, t}. Therefore, the resulting vertex subset cannot induce a path, and hence it cannot be a
solution for the induced variant. Similarly, the induced subgraph cannot contain a spanning path,
and hence it cannot be a solution for the spanning variant.
We next show that condition (b) is satisfied. Recall that d denotes the number of edges in a
shortest st-path in G. Then, we have |V ′ | = |Vs′ | = |Vt′ | = d+ 5. By condition (a), we know that V ′
contains s2 , s1 , t1 , t2 , and hence in both induced and spanning variants, s and t must be connected
by a path formed by d + 1 vertices in V ′ \ {s2 , s1 , t1 , t2 }. Since the length of this st-path is d, this
path is shortest and hence V ′ must contain exactly one vertex from each of d + 1 layers of G.
Consider any vertex subset V ′′ ⊆ V (G′ ) which satisfies conditions (a) and (b) of Lemma 1; note
that V ′′ is not necessarily a feasible solution. Then, these conditions ensure that V ′′ \ {s2 , s1 , t1 , t2 }
forms a shortest st-path in G if and only if the subgraph represented by V ′′ induces a path in G′ .
Thus, an instance (G, Vs , Vt ) of shortest path reconfiguration is a yes-instance if and only if
the corresponding instance (G′ , Vs′ , Vt′ ) of the induced or spanning variant is a yes-instance. This
completes the proof of Theorem 7.
Similar arguments give the following theorem.
Theorem 8. Both the induced and spanning variants of subgraph reconfiguration under the
TJ rule are PSPACE-complete for the property “a graph is a cycle.”
Proof. Our reduction is the same as in the proof of Theorem 7 except for the following point (see
also Figure 5(b)): instead of adding four new vertices, we connect s and t by a path of length three
with two new vertices s1 and t1 . Then, the same arguments hold as the proof of Theorem 7.

4.2

Path and cycle under the TS rule

We now consider the TS rule. Notice that, in the proofs of Theorems 7 and 8, we exchange only
vertices contained in the same layer. Since any shortest st-path in a graph G contains exactly one
vertex from each layer, we can assume without loss of generality that each layer Li of G forms a
clique. Then, the same reductions work for the TS rule, and we obtain the following theorem.
Theorem 9. Both the induced and spanning variants of subgraph reconfiguration under the
TS rule are PSPACE-complete for the properties “a graph is a path” and “a graph is a cycle.”

4.3

Tree

Wasa et al. [12] showed that the induced variant under the TJ and TS rules is PSPACE-complete
for the property “a graph is a tree.” In this subsection, we show that the spanning variant for this

9

property is also PSPACE-complete under the TS rule, while it is linear-time solvable under the TJ
rule.
We first note that our proof of Theorem 9 yields the following theorem.
Theorem 10. The spanning variant of subgraph reconfiguration under the TS rule is
PSPACE-complete for the property “a graph is a tree.”
Proof. We claim that the same reduction as in Theorem 9 applies. Let V ′ ⊆ V (G′ ) be any
solution which is reachable by a reconfiguration sequence from Vs′ (or Vt′ ) under the TS rule, where
(G′ , Vs′ , Vt′ ) is the corresponding instance for the spanning variant, as in the reduction. Then, the
TS rule ensures that s2 , s1 , s, t, t1 , t2 ∈ V ′ holds, and V ′ contains exactly one vertex from each
layer of G. Therefore, any solution forms a path even for the property “a graph is a tree,” and
hence the theorem follows.
In contrast to Theorem 10, the spanning variant under the TJ rule is solvable in linear time.
We note that the reduction in Theorem 10 does not work under the TJ rule, because the tokens
on s2 and t2 can move (jump) and hence there is no guarantee that a solution forms a path for the
property “a graph is a tree.”
Theorem 11. The spanning variant of subgraph reconfiguration under the TJ rule can be
solved in linear time for the property “a graph is a tree.”
Suppose that (G, Vs , Vt ) is a given instance. We assume that |Vs | = |Vt | ≥ 2 holds; otherwise it
is a trivial instance. Then, Theorem 11 can be obtained from the following lemma.
Lemma 2. (G, Vs , Vt ) with |Vs | = |Vt | ≥ 2 is a yes-instance if and only if Vs and Vt are contained
in the same connected component of G.
Proof. We first prove the only-if direction. Since |Vs | = |Vt | ≥ 2 and the property requires subgraphs to be connected, the subgraph induced by any feasible solution contains at least one edge.
Because we can exchange only one vertex at a time and the resulting subgraph must retain connected, Vs and Vt are contained in the same connected component of G if (G, Vs , Vt ) is a yesinstance.
Next, we prove the if direction for the case where |Vs | = |Vt | = 2. In this case, G[Vs ] and
G[Vt ] consist of single edges, say es and et , respectively. Since Vs and Vt are contained in the same
connected component of G, there is a path in G between es and et . Thus, we can exchange vertices
along the path, and obtain a reconfiguration sequence from Vs to Vt . In this way, the if direction
holds for this case.
Finally, we prove the if direction for the remaining case, that is, |Vs | = |Vt | ≥ 3. Consider any
spanning trees Ts of G[Vs ] and Tt of G[Vt ]. Since |Vs | = |Vt | ≥ 3, each of Ts and Tt has at least two
edges. Then, if we regard (G, E(Ts ), E(Tt )) as an instance of the edge variant under the TJ rule
for the property “a graph is a tree,” we know from the proof of Theorem 6 that it is a yes-instance.
Thus, there exists a reconfiguration sequence E = hE(Ts ) = E0 , E1 , . . . , Eℓ = E(Tt )i of edge
subsets under the TJ rule. We below show that, based on E, we can construct a reconfiguration
sequence between Vs and Vt for the spanning variant under the TJ rule.
For each Ei in E, let Vi be the vertex set of the tree represented by Ei . Notice that Vi is a
feasible solution for the spanning variant, and that V0 = Vs and Vℓ = Vt hold. We claim that
the sequence hVs = V0 , V1 , . . . , Vℓ = Vt i of vertex subsets is a reconfiguration sequence for the
spanning variant under the TJ rule (after removing redundant vertex subsets if needed). To show
this, it suffices to prove |Vi \ Vi−1 | = |Vi−1 \ Vi | ≤ 1 for all i ∈ {1, 2, . . . , ℓ}. Suppose for the sake of
contradiction that there exists Vi such that |Vi \Vi−1 | ≥ 2 holds. (See also Figure 6.) Since |Ei | ≥ 2
and |Ei \ Ei−1 | = 1 hold, we have Ei ∩ Ei−1 6= ∅ and hence Vi ∩ Vi−1 6= ∅. Then there is at least
one edge e = uv in Ei \ Ei−1 joining a vertex u ∈ Vi \ Vi−1 and v ∈ Vi ∩ Vi−1 , because Ei must form
a connected subgraph. Since |Vi \ Vi−1 | ≥ 2, there is another vertex u′ 6= u in Vi \ Vi−1 , and there
is an edge e′ incident to u′ . Note that e 6= e′ . Furthermore, we know that e′ ∈ Ei \ Ei−1 because
u′ ∈ Vi \ Vi−1 . Therefore, we have e, e′ ∈ Ei \ Ei−1 , which contradicts the fact that |Ei \ Ei−1 | = 1
holds.

10

Vi-1

Vi
v

e

u
e’ u’

Figure 6: Illustration for the proof of Lemma 2.
L

R

G

...
Figure 7: Reduction for the property “a graph is an (i, j)-biclique” for any fixed i ≥ 1.

4.4

Biclique

For the property “a graph is an (i, j)-biclique,” we show that the induced variant under the TJ
rule is PSPACE-complete even if i = j holds, or i is fixed. On the other hand, the spanning variant
under the TJ rule is NP-hard even if i = j holds, while it is polynomial-time solvable when i is
fixed.
We first give the following theorem for a fixed i ≥ 1.
Theorem 12. For the property “a graph is an (i, j)-biclique,” the induced variant of subgraph
reconfiguration under the TJ rule is PSPACE-complete even for any fixed integer i ≥ 1.
Proof. We give a polynomial-time reduction from the maximum independent set reconfiguration problem [13], which can be seen as a subgraph reconfiguration problem. The maximum
independent set reconfiguration problem is the induced variant for the property “a graph
is edgeless” such that two given independent sets are maximum. Note that, because we are given
maximum independent sets, there is no difference between the TJ and TS rules for this problem.
This problem is known to be PSPACE-complete [13].
Suppose that (G, Vs , Vt ) is an instance of maximum independent set reconfiguration.
We now construct a corresponding instance (G′ , Vs′ , Vt′ ) of the induced variant under the TJ rule
for the property “a graph is an (i, j)-biclique,” where i is any fixed positive integer. (See also
Figure 7.) Let L and R be distinct sets of new vertices such that |L| = i and |R| = 1. The vertex
set of G′ is defined as V (G′ ) = V (G) ∪ L ∪ R, and the edge set of G′ as E(G′ ) = E(G) ∪ {uv | u ∈
V (G), v ∈ L} ∪ {vw | v ∈ L, w ∈ R}, that is, new edges are added so that there are edges between
each vertex of L and each vertex of V (G) ∪ R. Let Vs′ = Vs ∪ L ∪ R and Vt′ = Vt ∪ L ∪ R. Since L,
R, Vs and Vt are all independent sets in G′ , both Vs′ and Vt′ form (i, j)-bicliques, where i = |L| and
j = |Vs ∪ R| = |Vt ∪ R|. We have now completed the construction of our corresponding instance,
which can be accomplished in polynomial time.
Because each vertex in L is connected to all vertices in V (G), a vertex subset V ′′ ⊆ V (G′ )
cannot form a bipartite graph (and hence an (i, j)-biclique) if V ′′ ∩ L 6= ∅ or if V ′′ contains two
vertices joined by an edge in G. In addition, we cannot move any token placed on L ∪ R onto a
vertex in V (G) because both Vs and Vt are maximum independent sets of G. Note that, in the case
of i = 1, there may exist a vertex u in V (G) which is adjacent to all vertices in Vs or in Vt . However,
u is not adjacent to the vertex in R, and hence the token placed on the vertex in L cannot be moved
to u in this case, either. Therefore, for any feasible solution V ′ ⊆ V (G′ ) which is reconfigurable
from Vs′ or Vt′ under the TJ rule, the vertex subset V ′ ∩ V (G) forms a maximum independent
set of G. Thus, an instance (G, Vs , Vt ) of maximum independent set reconfiguration is a
11

G
G1

G2

...

...

...

...
B1

...

...
A1

A2

B2

B

A

Figure 8: Reduction for the property “a graph is a (k, k)-biclique.”
yes-instance if and only if our corresponding instance (G′ , Vs′ , Vt′ ) is a yes-instance.
The corresponding instance (G′ , Vs′ , Vt′ ) constructed in the proof of Theorem 12 satisfies i = j
if we set i = |Vs | + 1 = |Vt | + 1. Therefore, we can obtain the following corollary.
Corollary 1. For the property “a graph is an (i, j)-biclique,” the induced variant of subgraph
reconfiguration under the TJ rule is PSPACE-complete even if i = j holds.
We next give the following theorem.
Theorem 13. For the property “a graph is an (i, j)-biclique,” the spanning variant of subgraph
reconfiguration under the TJ rule is NP-hard even if i = j holds.
Proof. We give a polynomial-time reduction from the balanced complete bipartite subgraph
problem, defined as follows [3]. Given a bipartite graph G and a positive integer k, the balanced
complete bipartite subgraph problem is to determine whether or not G contains a (k, k)biclique as a subgraph; this problem is known to be NP-hard [3].
Suppose that (G, k) is an instance of balanced complete bipartite subgraph, where G is
a bipartite graph with bipartition (A, B). Then, we construct a corresponding instance (G′ , Vs , Vt )
of the spanning variant under the TJ rule for the property “a graph is a (k, k)-biclique.” We first
construct a graph G′ . (See Figure 8.) We add to G two new (k, k)-bicliques G1 and G2 ; let (A1 , B1 )
be the bipartition of G1 , and (A2 , B2 ) be that of G2 . We then add edges between any two vertices
x ∈ B1 and y ∈ A, and between any two vertices x ∈ B and y ∈ A2 . Therefore, G′ [B1 ∪ A] and
G′ [B ∪ A2 ] are bicliques in G′ . This completes the construction of G′ . We then set Vs = V (G1 )
and Vt = V (G2 ). Then, Vs and Vt are solutions, since G[Vs ] and G[Vt ] contain (k, k)-bicliques G1
and G2 , respectively. In this way, the corresponding instance can be constructed in polynomial
time.
By the construction of G′ , any reconfiguration sequence between Vs = V (G1 ) and Vt = V (G2 )
must pass through a (k, k)-biclique of G. Therefore, the theorem follows.
We now give a polynomial-time algorithm solving the spanning variant for a fixed constant
i ≥ 1.
Theorem 14. For the property “a graph is an (i, j)-biclique,” the spanning variant of subgraph
reconfiguration under the TJ rule is solvable in polynomial time when i ≥ 1 is a fixed constant.
Proof. We give such an algorithm. We assume without loss of generality that j > i; otherwise both
i and j are fixed constants, and hence such a case can be solved in polynomial time by Theorem 1.
We will refer to the i vertices in the bounded-size part of the biclique as hubs, and the j vertices
in the other part as terminals. Let H ⊆ V (G) be an arbitrary vertex subset such that |H| = i.
We denote by C(H) the set of all common neighbors of H in G. Notice that, if |C(H)| ≥ j, then
the subgraph represented by H ∪ C(H) contains at least one (i, j)-biclique whose hub set is H.
We denote by S(H) the set of all solutions that contain (i, j)-bicliques with the hub set H. We
know that S(H) = ∅ if |C(H)| < j; otherwise H ∪ T is in S(H) for any subset T ⊆ C(H) such
that |T | = j. It should be noted that a solution in the spanning variant is simply a vertex subset
12

V ′ of V (G), and there is no restriction on how to choose a hub set from V ′ . (For example, if a
solution V ′ induces a clique of size five, then there are ten ways to choose a hub set from V ′ for
(2, 3)-bicliques.) Therefore, S(H) ∩ S(H ′ ) 6= ∅ may hold for distinct hub sets H, H ′ .
We describe two key observations in the following. The first one is that for a hub set H, any
two solutions Va , Vb ∈ S(H) are reconfigurable because we can always move vertices in Va \ Vb into
ones in Vb \ Va one by one. The second one is that for any two distinct hub sets Ha and Hb , if
there exist Va ∈ S(Ha ) and Vb ∈ S(Hb ) such that |Va \ Vb | ≤ 1 and |Vb \ Va | ≤ 1 (this means that
Va and Vb are reconfigurable by one reconfiguration step, or Va = Vb ), then all pairs of solutions
in S(Ha ) ∪ S(Hb ) are reconfigurable.
Based on these observations, we construct an auxiliary graph A for a given instance (G, Vs , Vt ),
as follows. Each node in A corresponds to a set H of i vertices (hubs) in the input graph G such
that |C(H)| ≥ j; we represent the node in A simply by the corresponding hub set H. Two nodes
Ha and Hb are adjacent in A if there exist Va ∈ S(Ha ) and Vb ∈ S(Hb ) such that |Va \ Vb | ≤ 1 and
|Vb \ Va | ≤ 1. Let Hs and Ht be any two nodes such that Vs ∈ S(Hs ) and Vt ∈ S(Ht ), respectively.
Then, we claim that there is a reconfiguration sequence between Vs and Vt if and only if there is
a path in A between Hs and Ht .
We first suppose that there is a path P in A between Hs and Ht . We know that any two
consecutive nodes Ha and Hb in P are adjacent in A. Then, as we mentioned above, all pairs of
solutions in S(Ha ) ∪ S(Hb ) are reconfigurable. Since Vs ∈ S(Hs ) and Vt ∈ S(Ht ), we can thus
conclude that there is a reconfiguration sequence between Vs and Vt .
We now suppose that there exists a reconfiguration sequence R between Vs and Vt . For each
solution Va in R except for Vs and Vt , we choose an arbitrary node Ha in A which satisfies
Va ∈ S(Ha ). Consider any two consecutive solutions Va and Vb in R. Then, by the construction of
A, the chosen nodes Ha and Hb are adjacent in A (or sometimes Ha = Hb ) because |Va \ Vb | = 1
and |Vb \ Va | = 1. In this way, we can ensure the existence of a desired path in A.
The running time of the algorithm depends on the size i of a hub set. Let n be the number
of vertices in G. The size of the node set of A is in O(ni ). For any two nodes Ha and Hb in A,
we can determine in O(n) time whether there is an edge between them by checking that all of the
following four conditions hold or not:
(a) |(Ha ∪ C(Ha )) ∩ (Hb ∪ C(Hb ))| ≥ i + j − 1;
(b) |Ha \ (Hb ∪ C(Hb ))| ≤ 1;
(c) |Hb \ (Ha ∪ C(Ha ))| ≤ 1; and
(d) |Ha ∪ Hb | ≤ i + j + 1.
Note that, since we have assumed that i < j, condition (d) is always satisfied. Therefore, we take
O(n2i+1 ) time to construct A and to check whether the nodes corresponding to Vs and Vt are
connected.

4.5

Diameter-two graph

In this subsection, we consider the property “a graph has diameter at most two.” Note that the
induced and spanning variants are the same for this property.
Theorem 15. Both induced and spanning variants of subgraph reconfiguration under the
TS rule are PSPACE-complete for the property “a graph has diameter at most two.”
Proof. Since the induced variant and the spanning variant are the same for this property, it suffices
to show the PSPACE-hardness only for the induced variant. We give a polynomial-time reduction
from the clique reconfiguration problem, which is the induced variant (also the spanning
variant) of subgraph reconfiguration for the property “a graph is a clique.” This problem is
known to be PSPACE-complete under both the TJ and TS rules [7], and we give a reduction from
the problem under the TS rule.
Suppose that (G, Vs , Vt ) is an instance of clique reconfiguration under the TS rule such
that |Vs | = |Vt | ≥ 2; otherwise it is a trivial instance. Then, we construct a corresponding
instance (G′ , Vs′ , Vt′ ) of the induced variant under the TS rule. Let V (G) = {v1 , v2 , . . . , vn }, where
n = |V (G)|. We form G′ by making two copies of G and adding edges between corresponding

13

l2

v2
v1

l1
l4

v4

l6

v6

r5

l5

v5

r4
r3

l3

v3

r2 = rs
r1

(a) G

r6

(b) G’

Figure 9: Reduction for the property “a graph has diameter at most two.” The vertices of Vs in
G and of Vs′ in G′ are depicted by gray vertices, where rs = r2 .
vertices of the two graphs. (See Figure 9.) More formally, the vertex set V (G′ ) is defined as
V (G′ ) = L ∪ R, where L = {li | vi ∈ V (G)} and R = {ri | vi ∈ V (G)}, and the edge set E(G′ ) is
defined as E(G′ ) = El ∪ Er ∪ Ec , where El = {li lj | vi vj ∈ E(G)}, Er = {ri rj | vi vj ∈ E(G)} and
Ec = {li ri | vi ∈ V (G)}. For each i ∈ {1, 2, . . . , n}, we call li and ri corresponding vertices, and
an edge joining corresponding vertices a connecting edge. We then construct Vs′ and Vt′ . We say
that a vertex v ′ in a vertex subset V ′ ⊆ V (G′ ) is exposed in V ′ if the corresponding vertex of v ′
does not belong to V ′ . We construct Vs′ and Vt′ so that they each have exactly one exposed vertex.
Let vs ∈ Vs be an arbitrary vertex in Vs and vt ∈ Vt be an arbitrary vertex in Vt . Then, we let
Vs′ = {li , ri | vi ∈ Vs } \ {rs } and Vt′ = {li , ri | vi ∈ Vt } \ {rt }. Note that ls and lt are the unique
exposed vertices in Vs′ and Vt′ , respectively. Since Vs and Vt form cliques in G, G′ [Vs′ ] and G′ [Vt′ ]
have diameter at most two. We have thus constructed our corresponding instance in polynomial
time.
Let V ′ be any subset of V (G′ ), and let VL′ = V ′ ∩ L and VR′ = V ′ ∩ R. The key observation
is that G[V ′ ] has diameter more than two if both VL′ and VR′ contain exposed vertices in V ′ .
We below prove that (G, Vs , Vt ) of clique reconfiguration is a yes-instance if and only if the
corresponding instance (G′ , Vs′ , Vt′ ) of the induced variant under the TS rule is a yes-instance.
We first prove the only-if direction, supposing that there exists a reconfiguration sequence
hVs = V0 , V1 , . . . , Vℓ = Vt i of cliques in G. Then, we show that Vs′ is reconfigurable into Vt′ by
induction on ℓ. If ℓ = 0 and hence Vs = Vt , then we can obtain Vt′ from Vs′ by exchanging rt in
Vs′ with rs (or Vs′ = Vt′ already holds). We then consider the case where ℓ ≥ 1. Let {vi } = V0 \ V1
and {vj } = V1 \ V0 ; note that vi and vj are adjacent in G since we consider the TS rule. Then, we
consider two vertex subsets V0′′ = (Vs′ ∪ {rs }) \ {ri } and V1′ = (V0′′ ∪ {lj }) \ {li }; note that rs and ri
are adjacent in G′ since rs , ri ∈ V0 = Vs , and that li and lj are adjacent in G′ since vi and vj are
adjacent in G. Notice that V ′′ and V1′ have distinct exposed vertices li and lj , respectively. By the
construction of G′ , since V0 and V1 are cliques in G, both G′ [V0′′ ] and G′ [V1′ ] have diameter at most
two. Then, the sequence hVs′ , V0′′ , V1′ i is a reconfiguration sequence between Vs′ and V1′ . Therefore,
by applying the induction hypothesis to (G′ , V1′ , Vt′ ) and (G, V1 , Vt ), we obtain a reconfiguration
sequence between V1′ and Vt′ . Thus, we can conclude that (G′ , Vs′ , Vt′ ) is a yes-instance.
To prove the if direction, we now suppose that there exists a reconfiguration sequence V ′ =
′
hVs = V0′ , V1′ , . . . , Vℓ′ = Vt′ i. Consider the case where Vi′ ∈ V ′ has the exposed vertex in the side L,
′
say li ∈ Vi′ , and hence ri 6∈ Vi′ ; the other case is symmetric. Because G′ [Vi+1
] must have diameter
′
at most two (and hence it must have only one exposed vertex), we know that Vi+1
is obtained from
Vi′ by one of the following three moves (1) a token on a vertex rk ∈ Vi′ is moved to ri ; (2) the token
on li is moved to its corresponding vertex ri ; or (3) the token on li is moved to a vertex lj ∈ L
which is not in Vi′ and is adjacent to all vertices Vi′ ∩ L. Notice that the other moves increase the
number of exposed vertices or make the resulting graph have diameter more than two. Then, each
Vi′ ∈ V ′ induces a clique of size |Vs | = |Vt | in either L or R, and we can obtain a desired sequence
of cliques between Vs and Vt .
We note that the TS rule is critical in the reduction of Theorem 15. Under the TJ rule, there
is no guarantee that we maintain a clique (and we cannot even guarantee that the resulting clique
gets bigger).
14

5

Conclusions and future work

The work in this paper initiates a systematic study of subgraph reconfiguration. Although
we have identified graph structure properties which are harder for the induced variant than the
spanning variant, it remains to be seen whether this pattern holds in general. For the general case,
questions of the roles of diameter and the number of subgraphs satisfying the property are worthy
of further investigation. Another obvious direction for further research is an investigation into the
fixed-parameter complexity of subgraph reconfiguration.
A natural extension of subgraph reconfiguration is the extension from isomorphism of
graph structure properties to other mappings, such as topological minors.

References
[1] P. Bonsma. The complexity of rerouting shortest paths. Theoretical Computer Science, 510:1–
12, 2013.
[2] P. Bonsma and L. Cereceda. Finding paths between graph colourings: PSPACE-completeness
and superpolynomial distances. Theoretical Computer Science, 410(50):5215–5226, 2009.
[3] M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of
NP-Completeness. Freeman, 1979.
[4] R. A. Hearn and E. D. Demaine. PSPACE-completeness of sliding-block puzzles and other
problems through the nondeterministic constraint logic model of computation. Theoretical
Computer Science, 343(1–2):72–96, 2005.
[5] J. van den Heuvel. The complexity of change. Surveys in Combinatorics 2013, 409:127–160,
2013.
[6] T. Ito, E. D. Demaine, N. J. A. Harvey, C. H. Papadimitriou, M. Sideri, R. Uehara, and
Y. Uno. On the complexity of reconfiguration problems. Theoretical Computer Science,
412(12–14):1054–1065, 2011.
[7] T. Ito, H. Ono, and Y. Otachi. Reconfiguration of cliques in a graph. In Proceedings of
the 12th Annual Conference on Theory and Applications of Models of Computation, pages
212–223, 2015.
[8] M. Kamiński, P. Medvedev, and M. Milanič. Complexity of independent set reconfigurability
problems. Theoretical Computer Science, 439:9–15, 2012.
[9] A. E. Mouawad, N. Nishimura, V. Raman, N. Simjour, and A. Suzuki. On the parameterized
complexity of reconfiguration problems. Algorithmica, 78(1):274–297, 2017.
[10] M. Mühlenthaler. Degree-constrained subgraph reconfiguration is in P. In Proceedings of
the 40th International Symposium on Mathematical Foundations of Computer Science, pages
505–516, 2015.
[11] N. Nishimura. Introduction to reconfiguration. Preprints 2017090055, 2017.
[12] K. Wasa, K. Yamanaka, and H. Arimura. The complexity of induced tree reconfiguration
problems. In Proceedings of the 10th International Conference of Language and Automata
Theory and Applications, pages 330–342, 2016.
[13] M. Wrochna. Reconfiguration in bounded bandwidth and tree-depth. Journal of Computer
and System Sciences, 93:1–10, 2018.

15

