# Rerouting Planar Curves and Disjoint Paths††thanks: This work was supported
by JSPS KAKENHI Grant Numbers JP18H05291, JP20K11692, JP20K14317, JP20H05793,
JP20H05795, JP20K23323, JP21H03397, JP22K17854.

Takehiro Ito Graduate School of Information Sciences, Tohoku University,
Japan<EMAIL_ADDRESS>Yuni Iwamasa Graduate School of Informatics,
Kyoto University, Japan<EMAIL_ADDRESS>Naonori Kakimura Faculty of
Science and Technology, Keio University, Japan<EMAIL_ADDRESS>Yusuke Kobayashi Research Institute for Mathematical Sciences, Kyoto
University, Japan<EMAIL_ADDRESS>Shun-ichi Maezawa Department of
Mathematics, Tokyo University of Science, Japan<EMAIL_ADDRESS>Yuta
Nozaki Graduate School of Advanced Science and Engineering, Hiroshima
University, Japan<EMAIL_ADDRESS>Yoshio Okamoto Graduate School of
Informatics and Engineering, The University of Electro-Communications, Japan,
<EMAIL_ADDRESS>Kenta Ozeki Faculty of Environment and Information
Sciences, Yokohama National University, Japan<EMAIL_ADDRESS>
###### Abstract

In this paper, we consider a transformation of $k$ disjoint paths in a graph.
For a graph and a pair of $k$ disjoint paths $\mathcal{P}$ and $\mathcal{Q}$
connecting the same set of terminal pairs, we aim to determine whether
$\mathcal{P}$ can be transformed to $\mathcal{Q}$ by repeatedly replacing one
path with another path so that the intermediates are also $k$ disjoint paths.
The problem is called Disjoint Paths Reconfiguration. We first show that
Disjoint Paths Reconfiguration is $\mathsf{PSPACE}$-complete even when $k=2$.
On the other hand, we prove that, when the graph is embedded on a plane and
all paths in $\mathcal{P}$ and $\mathcal{Q}$ connect the boundaries of two
faces, Disjoint Paths Reconfiguration can be solved in polynomial time. The
algorithm is based on a topological characterization for rerouting curves on a
plane using the algebraic intersection number. We also consider a
transformation of disjoint $s$-$t$ paths as a variant. We show that the
disjoint $s$-$t$ paths reconfiguration problem in planar graphs can be
determined in polynomial time, while the problem is $\mathsf{PSPACE}$-complete
in general.

##  1 Introduction

###  1.1 Disjoint Paths and Reconfiguration

The _disjoint paths problem_ is a classical and important problem in
algorithmic graph theory and combinatorial optimization. In the problem, the
input consists of a graph $G=(V,E)$ and $2k$ distinct vertices
$s_{1},\dots,s_{k},t_{1},\dots,t_{k}$, called terminals, and the task is to
find $k$ vertex-disjoint paths $P_{1},\dots,P_{k}$ such that $P_{i}$ connects
$s_{i}$ and $t_{i}$ for $i=1,\dots,k$ if they exist. A tuple
$\mathcal{P}=(P_{1},\dots,P_{k})$ of paths satisfying this condition is called
a _linkage_. The disjoint paths problem has attracted attention since 1980s
because of its practical applications to transportation networks, network
routing [52], and VLSI-layout [21, 33]. When the number $k$ of terminal pairs
is part of the input, the disjoint paths problem was shown to be
$\mathrm{NP}$-hard by Karp [28], and it remains $\mathrm{NP}$-hard even for
planar graphs [34]. For the case of $k=2$, polynomial-time algorithms were
presented in [50, 51, 56], while the directed variant was shown to be
$\mathsf{NP}$-hard [20]. Later, for the case when the graph is undirected and
$k$ is a fixed constant, Robertson and Seymour [47] gave a polynomial-time
algorithm based on the graph minor theory, which is one of the biggest
achievements in this area. Although the setting of the disjoint paths problem
is quite simple and easy to understand, a deep theory in discrete mathematics
is required to solve the problem, which is a reason why this problem has
attracted attention in the theoretical study of algorithms.

An interesting special case is the problem in planar graphs. In the early
stages of the study of the disjoint paths problem, for the case when $G$ is
embedded on a plane and all the terminals are on one face or two faces,
polynomial-time algorithms were given in [45, 53, 54]. In the series of graph
minor papers, the disjoint paths problem on a plane or on a fixed surface was
solved for fixed $k$ [46]. For the planar case, faster algorithms were
presented in [1, 43, 44]. The directed variant of the problem can be solved in
polynomial time if the input digraph is planar and $k$ is a fixed constant
[14, 49].

In this paper, we consider a transformation of linkages in a graph. Roughly,
in a transformation, we pick up one path among the $k$ paths in a linkage, and
replace it with another path to obtain a new linkage. To give a formal
definition, suppose that $G$ is a graph and
$s_{1},\dots,s_{k},t_{1},\dots,t_{k}$ are distinct terminals. For two linkages
$\mathcal{P}=(P_{1},\dots,P_{k})$ and $\mathcal{Q}=(Q_{1},\dots,Q_{k})$, we
say that $\mathcal{P}$ is _adjacent_ to $\mathcal{Q}$ if there exists
$i\in\\{1,\dots,k\\}$ such that $P_{j}=Q_{j}$ for
$j\in\\{1,\dots,k\\}\setminus\\{i\\}$ and $P_{i}\not=Q_{i}$. We say that a
sequence
$\langle\mathcal{P}_{1},\mathcal{P}_{2},\dots,\mathcal{P}_{\ell}\rangle$ of
linkages is a _reconfiguration sequence_ from $\mathcal{P}_{1}$ to
$\mathcal{P}_{\ell}$ if $\mathcal{P}_{i}$ and $\mathcal{P}_{i+1}$ are adjacent
for $i=1,\dots,\ell-1$. If such a sequence exists, we say that
$\mathcal{P}_{1}$ is _reconfigurable_ to $\mathcal{P}_{\ell}$. In this paper,
we focus on the following reconfiguration problem, which we call Disjoint
Paths Reconfiguration.

Disjoint Paths Reconfiguration

Input. A graph $G=(V,E)$, distinct terminals
$s_{1},\dots,s_{k},t_{1},\dots,t_{k}$, and two linkages $\cal P$ and $\cal Q$.

Question. Is $\cal P$ reconfigurable to $\cal Q$?

The problem can be regarded as the problem of deciding the reachability
between linkages via rerouting paths. Such a problem falls in the area of
combinatorial reconfiguration; see Section 1.3 for prior work on combinatorial
reconfiguration. Note that Disjoint Paths Reconfiguration is a decision
problem that just returns “YES” or “NO” and does not necessarily find a
reconfiguration sequence when the answer is YES.

Although our study is motivated by theoretical interest in the literature of
combinatorial reconfiguration, the problem can model rerouting problem in a
telecommunication network as follows. Suppose that a linkage represents
routing in a telecommunication network, and we want to modify linkage
$\mathcal{P}$ to another linkage $\mathcal{Q}$ which is better than
$\mathcal{P}$ in some sense. If we can change only one path in a step in the
network for some technical reasons, and we have to keep a linkage in the
modification process, then this situation is modeled as Disjoint Paths
Reconfiguration.

We also study a special case of the disjoint paths problem when
$s_{1}=\dots=s_{k}$ and $t_{1}=\dots=t_{k}$, which we call the _disjoint
$s$-$t$ paths problem_. In the problem, for a graph and two terminals $s$ and
$t$, we seek for $k$ internally vertex-disjoint (or edge-disjoint) paths
connecting $s$ and $t$. It is well-known that the disjoint $s$-$t$ paths
problem can be solved in polynomial time. The study of disjoint $s$-$t$ paths
was originated from Menger’s min-max theorem [37] and the max-flow algorithm
by Ford and Fulkerson [19]. Faster algorithms for finding maximum disjoint
$s$-$t$ paths or a maximum $s$-$t$ flow have been actively studied in
particular for planar graphs; see e.g. [16, 27, 29, 59].

In the same way as Disjoint Paths Reconfiguration, we consider a
reconfiguration of internally vertex-disjoint $s$-$t$ paths. Let $G=(V,E)$ be
a graph with two distinct terminals $s$ and $t$. We say that a set
$\mathcal{P}=\\{P_{1},\dots,P_{k}\\}$ of $k$ paths in $G$ is an _$s$ -$t$
linkage_ if $P_{1},\dots,P_{k}$ are internally vertex-disjoint $s$-$t$ paths.
Note that $\mathcal{P}$ is not a tuple but a set, that is, we ignore the
ordering of the paths in $\mathcal{P}$. We say that $s$-$t$ linkages
$\mathcal{P}$ and $\mathcal{Q}$ are _adjacent_ if
$\mathcal{Q}=(\mathcal{P}\setminus P)\cup\\{Q\\}$ for some $s$-$t$ paths $P$
and $Q$ with $P\neq Q$. We define the reconfigurability of $s$-$t$ linkages in
the same way as linkages. We consider the following problem.

Disjoint $s$-$t$ Paths Reconfiguration

Input. A graph $G=(V,E)$, distinct terminals $s$ and $t$, and two $s$-$t$
linkages $\cal P$ and $\cal Q$.

Question. Is $\cal P$ reconfigurable to $\cal Q$?

###  1.2 Our Contributions

Since finding disjoint $s$-$t$ paths is an easy combinatorial optimization
problem, one may expect that Disjoint $s$-$t$ Paths Reconfiguration is also
tractable. However, this is not indeed the case. We show that Disjoint $s$-$t$
Paths Reconfiguration is $\mathsf{PSPACE}$-hard even when $k=2$.

######  Theorem 1.1.

The Disjoint $s$-$t$ Paths Reconfiguration is $\mathsf{PSPACE}$-complete even
when $k=2$ and the maximum degree of $G$ is four.

Note that Disjoint $s$-$t$ Paths Reconfiguration can be easily reduced to
Disjoint Paths Reconfiguration by splitting each of $s$ and $t$ into $k$
terminals. Thus, this theorem implies the $\mathsf{PSPACE}$-hardness of
Disjoint Paths Reconfiguration with $k=2$.

In this paper, we mainly focus on the problems in planar graphs. To better
understand Disjoint Paths Reconfiguration in planar graphs, we show a
topological necessary condition.

Topological conditions play important roles in the disjoint paths problem. If
there exist disjoint paths connecting terminal pairs in a graph embedded on a
surface $\Sigma$, then obviously there must exist disjoint curves on $\Sigma$
connecting them. For example, when terminals $s_{1},s_{2},t_{1}$ and $t_{2}$
lie on the outer face $F$ in a plane graph $G$ in this order, there exist no
disjoint curves connecting the terminal pairs in the disk
$\Sigma=\mathbb{R}^{2}\setminus F$, and hence we can conclude that $G$
contains no disjoint paths. Such a topological condition is used to design
polynomial-time algorithms for the disjoint paths problem with $k=2$ [50, 51,
56], and to deal with the problem on a disk or a cylinder [45]. When $\Sigma$
is a plane (or a sphere), we can always connect terminal pairs by disjoint
curves on $\Sigma$, and hence nothing is derived from the above argument.
Indeed, Robertson and Seymour [46] showed that if the input graph is embedded
on a surface and the terminals are mutually “far apart,” then desired disjoint
paths always exist.

In contrast, as we will show below in Theorem 1.2, there exists a topological
necessary condition for the reconfigurability of disjoint paths. Thus, even
when the terminals are mutually far apart, the reconfiguration of disjoint
paths is not always possible. This shows a difference between the disjoint
paths problem and Disjoint Paths Reconfiguration.

In order to formally discuss the topological necessary condition, we consider
the reconfiguration of curves on a surface. Suppose that $\Sigma$ is a surface
and let $s_{1},\dots,s_{k},t_{1},\dots,t_{k}$ be distinct points on $\Sigma$.
By abuse of notation, we say that $\mathcal{P}=(P_{1},\dots,P_{k})$ is a
_linkage_ if it is a collection of disjoint simple curves on $\Sigma$ such
that $P_{i}$ connects $s_{i}$ and $t_{i}$. We also define the adjacency and
reconfiguration sequences for linkages on $\Sigma$ in the same way as linkages
in a graph. Then, the reconfigurability between two linkages on a plane can be
characterized with a word $w_{j}$ associated to $Q_{j}$ which is an element of
the free group $F_{k}$ generated by $x_{1},\dots,x_{k}$ as follows; see
Section 3 for the definition of $w_{j}$.

######  Theorem 1.2.

Let $\mathcal{P}=(P_{1},\dots,P_{k})$ and $\mathcal{Q}=(Q_{1},\dots,Q_{k})$ be
linkages on a plane (or a sphere). Then, $\mathcal{P}$ is reconfigurable to
$\mathcal{Q}$ if and only if $w_{j}\in\langle x_{j}\rangle$ for any
$j\in\\{1,\dots,k\\}$, where $\langle x_{j}\rangle$ denotes the subgroup
generated by $x_{j}$.

See Figure 1 (left) for an example. It is worth noting that, if $k=2$ and
$\Sigma$ is a connected orientable closed surface of genus $g\geq 1$, then
such a topological necessary condition does not exist, i.e., the
reconfiguration is always possible; see Appendix A.

Figure 1: (Left) An example on the plane where $(P_{1},P_{2})$ is not
reconfigurable to $(Q_{1},Q_{2})$. (Right) An example in a graph where the
condition in Theorem 1.2 holds but $(P_{1},P_{2})$ is not reconfigurable to
$(Q_{1},Q_{2})$.

For a graph embedded on a plane, we can identify paths and curves. Then,
Theorem 1.2 gives a topological necessary condition for Disjoint Paths
Reconfiguration in planar graphs. However, the converse does not necessarily
hold: even when the condition in Theorem 1.2 holds, an instance of Disjoint
Paths Reconfiguration may have no reconfiguration sequence. See Figure 1
(right) for a simple example. The polynomial solvability of Disjoint Paths
Reconfiguration in planar graphs is open even for the case of $k=2$.

With the aid of the topological necessary condition, we design polynomial-time
algorithms for special cases, in which all the terminals are on a single face
(called _one-face instances_), or $s_{1},\dots,s_{k}$ are on some face and
$t_{1},\dots,t_{k}$ are on another face (called _two-face instances_). Note
that one/two-face instances have attracted attention in the disjoint paths
problem [45, 53, 54], in the multicommodity flow problem [39, 40], and in the
shortest disjoint paths problem [8, 13, 15, 31]. We show that any one-face
instance of Disjoint Paths Reconfiguration has a reconfiguration sequence
(Proposition 4.1). Moreover, we prove a topological characterization for two-
face instances of Disjoint Paths Reconfiguration (Theorem 4.2), which leads to
a polynomial-time algorithm in this case.

######  Theorem 1.3.

When the instances are restricted to two-face instances, Disjoint Paths
Reconfiguration can be solved in polynomial time.

Based on this theorem, we give a polynomial-time algorithm for Disjoint
$s$-$t$ Paths Reconfiguration in planar graphs.

######  Theorem 1.4.

There is a polynomial-time algorithm for Disjoint $s$-$t$ Paths
Reconfiguration in planar graphs.

Note that the number $k$ of paths in Theorems 1.3 and 1.4 can be part of the
input.

It is well known that $G$ has an $s$-$t$ linkage of size $k$ if and only if
$G$ has no $s$-$t$ separator of size $k-1$ (Menger’s theorem). The
characterization for two-face instances (Theorem 4.2) implies the following
theorem, which is interesting in the sense that one extra $s$-$t$ connectivity
is sufficient to guarantee the existence of a reconfiguration sequence.

######  Theorem 1.5.

Let $G=(V,E)$ be a planar graph with distinct vertices $s$ and $t$, and let
$\mathcal{P}$ and $\mathcal{Q}$ be $s$-$t$ linkages. If there is no $s$-$t$
separator of size $k$, then $\mathcal{P}$ is reconfigurable to $\mathcal{Q}$.

As mentioned above, the polynomial solvability of Disjoint Paths
Reconfiguration in planar graphs is open even for the case of $k=2$. On the
other hand, when $k$ is not bounded, Disjoint Paths Reconfiguration is
$\mathsf{PSPACE}$-complete as the next theorem shows.

######  Theorem 1.6.

The Disjoint Paths Reconfiguration is $\mathsf{PSPACE}$-complete when the
graph $G$ is planar and of bounded bandwidth.

Here, we recall the definition of the bandwidth of a graph. Let $G=(V,E)$ be
an undirected graph. Consider an injective map $\pi\colon V\to\mathbb{Z}$.
Then, the _bandwidth_ of $\pi$ is defined as
$\max\\{|\pi(u)-\pi(v)|\mid\\{u,v\\}\in E\\}$. The _bandwidth_ of $G$ is
defined as the minimum bandwidth of all injective maps $\pi\colon
V\to\mathbb{Z}$.

###  1.3 Related Work

_Combinatorial reconfiguration_ is an emerging field in discrete mathematics
and theoretical computer science. In typical problems of combinatorial
reconfiguration, we consider two discrete structures, and ask whether one can
be transformed to the other by a sequence of local changes. See surveys of
Nishimura [38] and van den Heuvel [57].

Path reconfiguration problems have been studied in this framework. The
apparently first problem is the shortest path reconfiguration, introduced by
Kaminski et al. [26]. In this problem, we are given an undirected graph with
two designated vertices $s$, $t$ and two $s$-$t$ shortest paths $P$ and $Q$.
Then, we want to decide whether $P$ can be transformed to $Q$ by a sequence of
one-vertex changes in such a way that all the intermediate $s$-$t$ paths
remain the shortest. Bonsma [6] proved that the shortest path reconfiguration
is $\mathsf{PSPACE}$-complete, but polynomial-time solvable when the input
graph is chordal or claw-free. Bonsma [7] further proved that the problem is
polynomial-time solvable for planar graphs. Wrochna [60] proved that the
problem is $\mathsf{PSPACE}$-complete even for graphs of bounded bandwidth.
Gajjar et al. [22] proved that the problem is polynomial-time solvable for
circle graphs, circular-arc graphs, permutation graphs and hypercubes. They
also considered a variant where a change can involve $k$ successive vertices;
in this variant they proved that the problem is $\mathsf{PSPACE}$-complete
even for line graphs. Properties of the adjacency relation in the shortest
path reconfiguration have also been studied [4, 5].

Another path reconfiguration problem has been introduced by Amiri et al. [3]
who were motivated by a problem in software defined networks. In their setup,
we are given a directed graph with edge capacity and two designated vertices
$s,t$. We are also given $k$ pairs of $s$-$t$ paths $(P_{i},Q_{i})$,
$i=1,2,\dots,k$, where the number of paths among $P_{1},P_{2},\dots,P_{k}$
(and among $Q_{1},Q_{2},\dots,Q_{k}$ respectively) traversing an edge is at
most the capacity of the edge. The problem is to determine whether one set of
paths can be transformed to the other set of paths by a sequence of the
following type of changes: specify one vertex $v$ and then switch the usable
outgoing edges at $v$ from those in the $P_{i}$ to those in the $Q_{i}$. In
each of the intermediate situations, there must be a unique path through
usable edges in $P_{i}\cup Q_{i}$ for each $i$. See [3] for the precise
problem specification. Amiri et al. [3] proved that the problem is
$\mathsf{NP}$-hard even when $k=2$. For directed acyclic graphs, they also
proved that the problem is $\mathsf{NP}$-hard (for unbounded $k$) but fixed-
parameter tractable with respect to $k$. A subsequent work [2] studied an
optimization variant in which the number of steps is to be minimized when a
set of “disjoint” changes can be performed simultaneously.

Matching reconfiguration in bipartite graphs can be seen as a certain type of
disjoint paths reconfiguration problems. In matching reconfiguration, we are
given two matchings (with extra properties) and want to determine whether one
matching can be transformed to the other matching by a sequence of local
changes. There are several choices for local changes. One of the most studied
local change rules is the token jumping rule, where we remove one edge and add
one edge at the same time. Ito et al. [24] proved that the matching
reconfiguration (under the token jumping rule) can be solved in polynomial
time.111The theorem by Ito et al. [24] only gave a polynomial-time algorithm
for a different local change, the so-called token addition and removal rule.
However, their result can easily be adapted to the token jumping rule, too.
See [25].

To see a connection of matching reconfiguration with disjoint paths
reconfiguration, consider the matching reconfiguration problem in bipartite
graphs $G$ under the token jumping rule, where we are given two matchings
$M,M^{\prime}$ of $G$. Then, we add two extra vertices $s,t$ to $G$, and for
each edge $e\in M$ (and $M^{\prime}$) we construct a unique $s$-$t$ path of
length three that passes through $e$. This way, we obtain two $s$-$t$ linkages
$\mathcal{P}$ and $\mathcal{P}^{\prime}$ from $M$ and $M^{\prime}$,
respectively. It is easy to observe that $\mathcal{P}$ can be reconfigured to
$\mathcal{P}^{\prime}$ in Disjoint $s$-$t$ Paths Reconfiguration if and only
if $M$ can be reconfigured to $M^{\prime}$ in the matching reconfiguration
problem in $G$.

There are a lot of studies on the disjoint paths problem and its variants. A
natural variant is to maximize the number of vertex-disjoint paths connecting
terminal pairs, which is called the _maximum disjoint paths problem_. Since
this problem is $\mathsf{NP}$-hard when $k$ is part of the input, it has been
studied from the viewpoint of approximation algorithms. It is known that a
simple greedy algorithm achieves an approximation of factor $O(\sqrt{|V|})$
[32], which is the current best approximation ratio for general graphs.
Chuzhoy and Kim [9] improved this factor to $\tilde{O}(n^{1/4})$ for grid
graphs, and Chuzhoy et al. [10] gave an $\tilde{O}(|V|^{9/19})$-approximation
algorithm for planar graphs. On the negative side, the maximum disjoint paths
problem is $2^{\Omega(\sqrt{\log|V|})}$-hard to approximate under some
complexity assumption [11], which is the current best hardness result.

Another variant is the _shortest non-crossing walks problem_. In a graph
embedded on a plane, we say that walks are _non-crossing_ if they do not cross
each other or themselves, while they may share edges or vertices; see [17] for
a formal definition. We can see that this concept is positioned in between
disjoint paths and disjoint curves. In the shortest non-crossing walks
problem, we are given a plane graph with non-negative edge lengths and $k$
terminal pairs that lie on the boundary of $h$ polygonal obstacles. The
objective is to find $k$ non-crossing walks that connect terminal pairs in $G$
of minimum total length, if they exist. For the case of $h=2$, Takahashi et
al. [55] gave an $O(|V|\log|V|)$-time algorithm, and Papadopoulou [42]
proposed a linear-time algorithm. For general $h$, Erickson and Nayyeri [17]
gave a $2^{O(h^{2})}|V|\log k$-time algorithm, which runs in polynomial time
when $h$ is a fixed constant. They also showed that the existence of a
feasible solution can be determined in linear time.

###  1.4 Organization

In Section 2, we introduce some notation and basic concepts in topology.
Section 3 deals with rerouting disjoint curves, giving the proof of Theorem
1.2. In Sections 4 and 5, we prove Theorems 1.3, 1.4, and 1.5. Hardness
results (Theorems 1.1 and 1.6) are then proven in Section 6.

##  2 Preliminaries

For a positive integer $k$, let $[k]=\\{1,2,\dots,k\\}$.

Let $G=(V,E)$ be a graph. For a subgraph $H$ of $G$, the vertex set of $H$ is
denoted by $V(H)$. Similarly, for a path $P$, let $V(P)$ denote the set of
vertices in $P$. For $X\subseteq V$, let $N(X)$ be the set of vertices in
$V\setminus X$ that are adjacent to the vertices in $X$. For a vertex set
$U\subseteq V$, let $G\setminus U$ denote the graph obtained from $G$ by
removing all the vertices in $U$ and the incident edges. For a path $P$ in
$G$, we denote $G\setminus V(P)$ by $G\setminus P$ to simplify the notation.
For disjoint vertex sets $X,Y\subseteq V$, we say that a vertex subset
$U\subseteq V\setminus(X\cup Y)$ _separates_ $X$ and $Y$ if $G\setminus U$
contains no path between $X$ and $Y$. For distinct vertices $s,t\in V$,
$U\subseteq V\setminus\\{s,t\\}$ is called an _$s$ -$t$ separator_ if $U$
separates $\\{s\\}$ and $\\{t\\}$.

For Disjoint Paths Reconfiguration (resp. Disjoint $s$-$t$ Paths
Reconfiguration), an instance is denoted by a triplet
$(G,\mathcal{P},\mathcal{Q})$, where $G$ is a graph and $\mathcal{P}$ and
$\mathcal{Q}$ are linkages (resp. $s$-$t$ linkages). Note that we omit the
terminals, because they are determined by $\mathcal{P}$ and $\mathcal{Q}$.
Since any instance has a trivial reconfiguration sequence when $k=1$, we may
assume that $k\geq 2$. For linkages (resp. $s$-$t$ linkages) $\mathcal{P}$ and
$\mathcal{Q}$, we denote $\mathcal{P}\leftrightarrow\mathcal{Q}$ if
$\mathcal{P}$ and $\mathcal{Q}$ are adjacent. Recall that
$\mathcal{P}=(P_{1},\dots,P_{k})$ is _adjacent_ to
$\mathcal{Q}=(Q_{1},\dots,Q_{k})$ if there exists $i\in[k]$ such that
$P_{j}=Q_{j}$ for $j\in[k]\setminus\\{i\\}$ and $P_{i}\not=Q_{i}$.

For a graph $G$ embedded on a surface $\Sigma$, each connected region of
$\Sigma\setminus G$ is called a _face_ of $G$. For a face $F$, its boundary is
denoted by $\partial{F}$. When a graph $G$ is embedded on a surface $\Sigma$,
a path in $G$ is sometimes identified with the corresponding curve in
$\Sigma$. A graph embedded on a plane is called a _plane graph_. A graph is
said to be _planar_ if it has a planar embedding.

The following notion is well known in topology. See [18, Section 1.2.3] for
instance.

######  Definition 2.1.

Let $C_{1}$ and $C_{2}$ be piecewise smooth oriented curves on an oriented
surface and let $p\in C_{1}\cap C_{2}$ be a transverse double point. The
_local intersection number_ $\varepsilon_{p}(C_{1},C_{2})$ of $C_{1}$ and
$C_{2}$ at $p$ is defined by $\varepsilon_{p}(C_{1},C_{2})=1$ if $C_{1}$
crosses $C_{2}$ from left to right and $\varepsilon_{p}(C_{1},C_{2})=-1$ if
$C_{1}$ crosses $C_{2}$ from right to left (see Figure 2). When $\partial
C_{1}\cap C_{2}=C_{1}\cap\partial C_{2}=\emptyset$, the _algebraic
intersection number_ $\mu(C_{1},C_{2})\in\mathbb{Z}$ is defined to be the sum
of $\varepsilon_{p}(C_{1},C_{2})$ over all $p\in C_{1}\cap C_{2}$ (after a
small perturbation if necessary). Note that $\partial C_{i}$ denotes the set
of endpoints of $C_{i}$.

Figure 2: Local intersection numbers of curves $C_{1}$ and $C_{2}$ at $p$.
Figure 3: Algebraic intersection numbers of paths $C_{1}$ and $C_{2}$ on a
graph.

When a graph is embedded on an oriented surface, paths in the graph are
piecewise smooth curves, and hence we can define the algebraic intersection
number for a pair of paths (see Figure 3).

##  3 Curves on a Plane

In this section, we consider the reconfiguration of curves on a plane and
prove Theorem 1.2. Suppose that we are given distinct points
$s_{1},\dots,s_{k},t_{1},\dots,t_{k}$ on a plane and linkages $\mathcal{P}$
and $\mathcal{Q}$ that consist of curves on the plane connecting $s_{i}$ and
$t_{i}$.

Throughout this section, all intersections of curves are assumed to be
transverse double points. Fix $j\in[k]$ and let $\bigcup_{i\in[k]}P_{i}\cap
Q_{j}=\\{s_{j},p_{1},\dots,p_{n},t_{j}\\}$, where the $n+2$ points are aligned
on $Q_{j}$ in this order. We now define $w_{j}\in F_{k}$ by

$w_{j}=\prod_{\ell\in[n]}x_{i_{\ell}}^{\varepsilon_{p_{\ell}}(P_{i_{\ell}},Q_{j})},$

where $i_{\ell}\in[k]$ satisfies $p_{\ell}\in P_{i_{\ell}}\cap Q_{j}$. Recall
that $F_{k}$ denotes the free group generated by $x_{1},\dots,x_{k}$. We give
an example in Figure 4.

Figure 4: An example of linkages with
$w_{1}=x_{2}x_{1}^{-1}x_{2}^{-1}x_{1}x_{2}^{-1}x_{1}^{-1}x_{2}$ and
$w_{2}=x_{1}x_{2}^{-1}x_{1}^{-1}x_{2}x_{1}^{-1}x_{2}^{-1}x_{1}$.

######  Remark 3.1.

Let $\mathrm{ab}\colon F_{k}\to\mathbb{Z}^{k}$ denote the abelianization, that
is, the $\ell$th entry of $\mathrm{ab}(w)$ is the sum of the exponents of
$x_{\ell}$’s in $w$. For distinct $i,j\in[k]$, the $i$th entry of
$\mathrm{ab}(w_{j})$ is equal to the algebraic intersection number
$\mu(P_{i},Q_{j})\in\mathbb{Z}$ of $P_{i}$ and $Q_{j}$. Thus, $w_{j}\in\langle
x_{j}\rangle$ implies that $\mu(P_{i},Q_{j})=0$ for any
$i\in[k]\setminus\\{j\\}$.

In the following two lemmas, we observe the behavior of $w_{j}$ under certain
moves of curves. For $j\in[k]$, let $w^{\prime}_{j}$ denote the word defined
by a linkage $\mathcal{P}^{\prime}$ and the curve $Q_{j}$.

######  Lemma 3.2.

Let $i\in[k]$ and let
$\mathcal{P}^{\prime}=(P^{\prime}_{1},\dots,P^{\prime}_{k})$ be a linkage such
that $P^{\prime}_{\ell}=P_{\ell}$ if $\ell\neq i$, and $P^{\prime}_{i}$ is
isotopic to $P_{i}$ relative to $\\{s_{i},t_{i}\\}$ in
$\mathbb{R}^{2}\setminus\bigcup_{\ell\neq i}P_{\ell}$. Then,
$w^{\prime}_{j}=w_{j}$ for $j\in[k]\setminus\\{i\\}$, and
$w^{\prime}_{i}=x_{i}^{e_{1}}w_{i}x_{i}^{e_{2}}$ for some
$e_{1},e_{2}\in\mathbb{Z}$.

###### Proof.

By the definition of an isotopy (see [18, Section 1.2.5]), $P^{\prime}_{i}$ is
obtained from $P_{i}$ by a finite sequence of the moves illustrated in Figure
5. By (I), one intersection of $P_{i}$ and $Q_{i}$ is created or eliminated,
and thus (I) changes $w_{i}$ to $w_{i}x_{i}^{\pm 1}$ or $x_{i}^{\pm 1}w_{i}$.
In (II), two intersections of $P_{i}$ and $Q_{\ell}$ are created or eliminated
for some $\ell\in[k]$. Since $x_{i}^{\pm 1}x_{i}^{\mp 1}=1$, $w_{j}$ is
unchanged under (II) for any $j\in[k]$. ∎

Figure 5: Local pictures of isotopies of $P_{i}$.

Recall here that $\langle x_{\ell}\rangle$ denotes the subgroup of $F_{k}$
generated by $x_{\ell}$.

######  Lemma 3.3.

Let $\gamma$ be a simple curve connecting $P_{i}$ and $s_{j}$ $(i\neq j)$
whose interior is disjoint from $\bigcup_{\ell\in[k]}P_{\ell}$, and define
$P^{\prime}_{i}$ as illustrated in Figure 6. Let $\mathcal{P}^{\prime}$ be the
linkage obtained from $\mathcal{P}$ by replacing $P_{i}$ with
$P^{\prime}_{i}$. For $\ell\in[k]$, if $w_{\ell}\in\langle x_{\ell}\rangle$,
then $w^{\prime}_{\ell}=w_{\ell}$.

###### Proof.

Define a group homomorphism $f_{ij}\colon F_{k}\to F_{k}$ by
$f_{ij}(x_{\ell})=x_{\ell}$ if $\ell\neq j$, and
$f_{ij}(x_{j})=x_{i}x_{j}x_{i}^{-1}$. Then, one can check that
$w^{\prime}_{\ell}=f_{ij}(w_{\ell})$ if $\ell\neq j$, and
$w^{\prime}_{j}=x_{i}^{-1}f_{ij}(w_{j})x_{i}$ (see Figure 6). Since
$w_{\ell}=x_{\ell}^{e_{\ell}}$ for some $e_{\ell}\in\mathbb{Z}$ by the
assumption, we have $w^{\prime}_{\ell}=w_{\ell}$ if $\ell\neq j$. Also, one
has

$w^{\prime}_{j}=x_{i}^{-1}f_{ij}(w_{j})x_{i}=x_{i}^{-1}(x_{i}x_{j}x_{i}^{-1})^{e_{j}}x_{i}=w_{j}.$

This completes the proof. ∎

Figure 6: (Left) A move of $P_{i}$ along $\gamma$. (Right) Intersections of
$P^{\prime}_{i}$ and $\bigcup_{\ell}Q_{\ell}$.

As a consequence of Lemmas 3.2 and 3.3, we obtain the following key lemma.

######  Lemma 3.4.

Suppose that $\mathcal{P}$ is reconfigurable to $\mathcal{P}^{\prime}$. For
$j\in[k]$, if $w_{j}\in\langle x_{j}\rangle$, then $w^{\prime}_{j}\in\langle
x_{j}\rangle$.

###### Proof.

It suffices to consider the case when there is $i\in[k]$ such that
$P^{\prime}_{\ell}=P_{\ell}$ if $\ell\neq i$, and $P^{\prime}_{i}\neq P_{i}$.
Since $P_{i}$ is isotopic to $P^{\prime}_{i}$ (relative to
$\\{s_{i},t_{i}\\}$) in $\mathbb{R}^{2}$, the curve $P^{\prime}_{i}$ is
obtained from $P_{i}$ by the moves in Lemmas 3.2 and 3.3. Therefore, these
lemmas imply that if $w_{j}\in\langle x_{j}\rangle$ then
$w^{\prime}_{j}\in\langle x_{j}\rangle$. ∎

With this key lemma, we can prove Theorem 1.2 stating that $\mathcal{P}$ is
reconfigurable to $\mathcal{Q}$ if and only if $w_{j}\in\langle x_{j}\rangle$
for any $j\in[k]$.

###### Proof of Theorem 1.2.

First suppose that $\mathcal{P}$ is reconfigurable to $\mathcal{Q}$, namely
$\mathcal{P}$ is reconfigurable to $\mathcal{P}^{\prime}$ such that
$P^{\prime}_{i}\cap Q_{i}=\\{s_{i},t_{i}\\}$ and $P^{\prime}_{i}\cap
Q_{j}=\emptyset$ for $j\in[k]\setminus\\{i\\}$. Then, $w^{\prime}_{j}=1$ for
any $j\in[k]$. Since $\mathcal{P}^{\prime}$ is reconfigurable to
$\mathcal{P}$, Lemma 3.4 implies that $w_{j}\in\langle x_{j}\rangle$ for any
$j\in[k]$.

The converse is shown by induction on the number, say $n$, of intersections of
$\mathcal{P}$ and $\mathcal{Q}$ except their endpoints. The case $n=0$ is
obvious. Let us consider the case $n\geq 1$. If $P_{i}\cap Q_{j}=\emptyset$
for any pair of distinct $i,j\in[k]$, then the reconfiguration is obviously
possible. Otherwise, there exists $x_{i}x_{i}^{-1}$ or $x_{i}^{-1}x_{i}$ in
the product of the definition of $w_{j^{*}}$ for some $i,j^{*}\in[k]$
(possibly $i=j^{*}$). This means that $P_{i}$ can be reconfigured to a curve
$P^{\prime}_{i}$ as illustrated in Figure 7. This process eliminates at least
two intersections and we have $w^{\prime}_{j}\in\langle x_{j}\rangle$ for any
$j\in[k]$ by Lemma 3.4. Thus, the induction hypothesis concludes that
$\mathcal{P}^{\prime}$ is reconfigurable to $\mathcal{Q}$. ∎

Figure 7: A reconfiguration of $P_{i}$ to $P^{\prime}_{i}$.

By Theorem 1.2 and Remark 3.1, we obtain the following corollary.

######  Corollary 3.5.

Let $\mathcal{P}=(P_{1},\dots,P_{k})$ and $\mathcal{Q}=(Q_{1},\dots,Q_{k})$ be
linkages on a plane (or a sphere). If $\mathcal{P}$ is reconfigurable to
$\mathcal{Q}$, then $\mu(P_{i},Q_{j})=0$ for any distinct $i,j\in[k]$.

It is worth mentioning that the converse is not necessarily true as
illustrated in Figure 4. This means that a “non-commutative” tool such as the
free group $F_{k}$ is essential to describe the complexity of the
reconfiguration of curves on a plane.

##  4 Algorithms for Planar Graphs

In this section, we consider the reconfiguration in planar graphs and prove
Theorems 1.3, 1.4, and 1.5. We deal with one-face instances and two-face
instances of Disjoint Paths Reconfiguration in Sections 4.1 and 4.2,
respectively. Then, we discuss Disjoint $s$-$t$ Paths Reconfiguration in
Section 4.3. A proof of a key theorem (Theorem 4.2) is postponed to Section 5.

###  4.1 One-Face Instance

We say that an instance $(G,\mathcal{P},\mathcal{Q})$ of Disjoint Paths
Reconfiguration is a _one-face instance_ if $G$ is a plane graph and all the
terminals are on the boundary of some face. We show that $\mathcal{P}$ is
always reconfigurable to $\mathcal{Q}$ in a one-face instance.

######  Proposition 4.1.

For any one-face instance $(G,\mathcal{P},\mathcal{Q})$ of Disjoint Paths
Reconfiguration, $\mathcal{P}$ is reconfigurable to $\mathcal{Q}$.

###### Proof.

We prove the proposition by induction on the number of vertices in $G$. Let
$I=(G,\mathcal{P},\mathcal{Q})$ be a one-face instance of Disjoint Paths
Reconfiguration.

If $G$ is not connected, then we can consider each connected component
separately. If $G$ is connected but not $2$-connected, then there exist
subgraphs $G_{1}$ and $G_{2}$ such that $G=G_{1}\cup G_{2}$ and $V(G_{1})\cap
V(G_{2})=\\{v\\}$ for some $v\in V$. For $i=1,2$, define $I_{i}$ as the
restriction of $I$ to $G_{i}$ if some path in $\mathcal{P}\cup\mathcal{Q}$
uses an edge in $G_{i}$ incident to $v$, and define $I_{i}$ as the restriction
of $I$ to $G_{i}\setminus\\{v\\}$ otherwise. Since $I_{1}$ and $I_{2}$ are
one-face instances (or trivial instances with at most one terminal pair), the
induction hypothesis shows that there exist reconfiguration sequences for
$I_{1}$ and $I_{2}$. By combining them, we obtain a reconfiguration sequence
from $\mathcal{P}$ to $\mathcal{Q}$.

In what follows, suppose that $G$ is $2$-connected. Let $F$ be a face of $G$
whose boundary contains all the terminals. Note that the boundary of $F$ forms
a cycle, because $G$ is $2$-connected. Since there is a linkage, for some
$i\in[k]$, there exists an $s_{i}$-$t_{i}$ path $R_{i}$ along $\partial{F}$
that contains no terminals other than $s_{i}$ and $t_{i}$. Since $\mathcal{P}$
and $\mathcal{Q}$ are linkages, $P_{j}$ and $Q_{j}$ are disjoint from $R_{i}$
for $j\in[k]\setminus\\{i\\}$. Define $\mathcal{P}^{\prime}$ (resp.
$\mathcal{Q}^{\prime}$) as the linkage that is obtained from $\mathcal{P}$
(resp. $\mathcal{Q}$) by replacing $P_{i}$ (resp. $Q_{i}$) with $R_{i}$. Then,
$\mathcal{P}\leftrightarrow\mathcal{P}^{\prime}$ and
$\mathcal{Q}\leftrightarrow\mathcal{Q}^{\prime}$.

Since $(G\setminus
R_{i},\mathcal{P}^{\prime}\setminus\\{R_{i}\\},\mathcal{Q}^{\prime}\setminus\\{R_{i}\\})$
is a one-face instance, $\mathcal{P}^{\prime}\setminus\\{R_{i}\\}$ is
reconfigurable to $\mathcal{Q}^{\prime}\setminus\\{R_{i}\\}$ in $G\setminus
R_{i}$ by the induction hypothesis. This implies that $\mathcal{P}^{\prime}$
is reconfigurable to $\mathcal{Q}^{\prime}$ in $G$. Therefore, $\mathcal{P}$
is reconfigurable to $\mathcal{Q}$ in $G$. ∎

###  4.2 Two-Face Instance

Let $k\geq 2$. We say that an instance $(G,\mathcal{P},\mathcal{Q})$ of
Disjoint Paths Reconfiguration is a _two-face instance_ if $G=(V,E)$ is a
plane graph, $s_{1},\dots,s_{k}$ are on the boundary of some face $S$, and
$t_{1},\dots,t_{k}$ are on the boundary of another face $T$. The objective of
this subsection is to present a polynomial-time algorithm for two-face
instances.

It suffices to consider the case when the graph is $2$-connected, since
otherwise we can easily reduce to the $2$-connected case. Hence, we may assume
that the boundary of each face forms a cycle. For ease of explanation, without
loss of generality, we assume that $G$ is embedded on $\mathbb{R}^{2}$ so that
$S$ is an inner face and $T$ is the outer face. Furthermore, we may assume
that $s_{1},\dots,s_{k}$ lie on the boundary of $S$ clockwise in this order
and $t_{1},\dots,t_{k}$ lie on the boundary of $T$ clockwise in this order,
because there is a linkage.

A vertex set $U\subseteq V$ is called a _terminal separator_ if $U$ separates
$\\{s_{1},\dots,s_{k}\\}$ and $\\{t_{1},\dots,t_{k}\\}$. For two curves (or
paths) $P$ and $Q$ between $\partial{S}$ and $\partial{T}$ that share no
endpoints, define $\mu(P,Q)$ as in Definition 2.1. That is, $\mu(P,Q)$ is the
number of times $P$ crosses $Q$ from left to right minus the number of times
$P$ crosses $Q$ from right to left, where we suppose that $P$ and $Q$ are
oriented from $\partial{S}$ to $\partial{T}$. Since $\mu(P_{i},Q_{j})$ takes
the same value for distinct $i,j\in[k]$ (see Appendix B), this value is
denoted by $\mu(\mathcal{P},\mathcal{Q})$. Roughly,
$\mu(\mathcal{P},\mathcal{Q})$ indicates the difference of the numbers of
rotations around $S$ of the linkages.

The existence of a linkage shows that the graph has no terminal separator of
size less than $k$. If the graph has no terminal separator of size $k$, then
we can characterize the reconfigurability by using
$\mu(\mathcal{P},\mathcal{Q})$. The following is a key theorem in our
algorithm, whose proof is given in Section 5.

######  Theorem 4.2.

Let $k\geq 2$. Suppose that a two-face instance $(G,\mathcal{P},\mathcal{Q})$
of Disjoint Paths Reconfiguration has no terminal separator of size $k$. Then,
$\mathcal{P}$ is reconfigurable to $\mathcal{Q}$ if and only if
$\mu(\mathcal{P},\mathcal{Q})=0$.

By using this theorem, we can design a polynomial-time algorithm for two-face
instances of Disjoint Paths Reconfiguration and prove Theorem 1.3.

###### Proof of Theorem 1.3.

Suppose that we are given a two-face instance $I=(G,\mathcal{P},\mathcal{Q})$
of Disjoint Paths Reconfiguration.

We first test whether $I$ has a terminal separator of size $k$, which can be
done in polynomial time by a standard minimum cut algorithm. If there is no
terminal separator of size $k$, then Theorem 4.2 shows that we can easily
solve Disjoint Paths Reconfiguration by checking whether
$\mu(\mathcal{P},\mathcal{Q})=0$ or not.

Suppose that we obtain a terminal separator $U$ of size $k$. Then, we obtain
subgraphs $G_{1}$ and $G_{2}$ of $G$ such that $G=G_{1}\cup G_{2}$,
$V(G_{1})\cap V(G_{2})=U$, $\\{s_{1},\dots,s_{k}\\}\subseteq V(G_{1})$, and
$\\{t_{1},\dots,t_{k}\\}\subseteq V(G_{2})$. We test whether $V(P_{i})\cap
U=V(Q_{i})\cap U$ holds for any $i\in[k]$ or not, where we note that each of
$V(P_{i})\cap U$ and $V(Q_{i})\cap U$ consists of a single vertex. If this
does not hold, then we can immediately conclude that $\mathcal{P}$ is not
reconfigurable to $\mathcal{Q}$, because $V(P_{i})\cap U$ does not change in
the reconfiguration. If $V(P_{i})\cap U=V(Q_{i})\cap U$ for $i\in[k]$, then we
consider the instance $I_{i}=(G_{i},\mathcal{P}_{i},\mathcal{Q}_{i})$ for
$i=1,2$, where $\mathcal{P}_{i}$ and $\mathcal{Q}_{i}$ are the restrictions of
$\mathcal{P}$ and $\mathcal{Q}$ to $G_{i}$. That is, $I_{i}$ is the
restriction of $I$ to $G_{i}$. Then, we see that $\mathcal{P}$ is
reconfigurable to $\mathcal{Q}$ if and only if $\mathcal{P}_{i}$ is
reconfigurable to $\mathcal{Q}_{i}$ for $i=1,2$. Since $I_{1}$ and $I_{2}$ are
one-face or two-face instances, by solving them recursively, we can solve the
original instance $I$ in polynomial time. See Algorithm 1 for a pseudocode of
the algorithm. ∎

Input: A two-face instance $I=(G,\mathcal{P},\mathcal{Q})$ of DPR.

Output: Is $\mathcal{P}$ reconfigurable to $\mathcal{Q}$?

1 Compute a terminal separator $U$ of size $k$;

2 if  _such $U$ does not exist_ then

3 if  _$\mu(\mathcal{P},\mathcal{Q})=0$_ then

4 return _YES_

5 else

6 return _NO_

7else

8 if  _$V(P_{i})\cap U\neq V(Q_{i})\cap U$ for some $i\in[k]$_ then

9 return _NO_

10 else

11 Construct $G_{1}$ and $G_{2}$;

12 Solve the restriction $I_{i}$ of $I$ to $G_{i}$ for $i=1,2$, recursively;

13 if  _$I_{i}$ is a YES-instance for $i=1,2$_ then

14 return _YES_

15 else

16 return _NO_

Algorithm 1 Algorithm for two-face instances of DPR

###  4.3 Reconfiguration of $s$-$t$ Paths

In this subsection, for Disjoint $s$-$t$ Paths Reconfiguration in planar
graphs, we show results that are analogous to Theorems 4.2 and 1.3, which have
been already stated in Section 1.2.

See 1.5

###### Proof.

Suppose that $G$, $s$, $t$, $\mathcal{P}$, and $\mathcal{Q}$ are as in the
statement, and assume that there is no $s$-$t$ separator of size $k$. We fix
an embedding of $G$ on the plane. If there is an edge connecting $s$ and $t$,
then $s$ and $t$ are on the boundary of some face, and hence $\mathcal{P}$ is
reconfigurable to $\mathcal{Q}$ in the same way as Proposition 4.1. Thus, it
suffices to consider the case when there is no edge connecting $s$ and $t$.

We now construct an instance of Disjoint Paths Reconfiguration by replacing
$s$ and $t$ with large “grids” as follows. Let $e_{1},e_{2},\dots,e_{\ell}$ be
the edges incident to $s$ clockwise in this order. Note that $\ell\geq k+1$
holds, because $G$ has no $s$-$t$ separator of size $k$. For $i\in[\ell]$, we
subdivide $e_{i}$ by introducing $p$ new vertices
$v^{1}_{i},v^{2}_{i},\dots,v^{p}_{i}$ such that they are aligned in this order
and $v^{1}_{i}$ is closest to $s$, where $p$ is a sufficiently large integer
(e.g., $p\geq|V|^{2})$. For $i\in[\ell]$ and for $j\in[p]$, we introduce a new
edge connecting $v^{j}_{i}$ and $v^{j}_{i+1}$, where
$v^{j}_{\ell+1}=v^{j}_{1}$. Define $s_{i}=v^{1}_{i}$ for $i\in[k]$ and remove
$s$. Then, the graph is embedded on the plane and $s_{1},\dots,s_{k}$ are on
the boundary of some face clockwise in this order; see Figure 8. By applying a
similar procedure to $t$, we modify the graph around $t$ and define
$t_{1},\dots,t_{k}$ that are on the boundary of some face counter-clockwise in
this order. Let $G^{\prime}$ be the obtained graph. Observe that $G^{\prime}$
contains no terminal separator of size $k$, because $G$ has no $s$-$t$
separator of size $k$.

Figure 8: (Left) Original graph $G$. (Right) Modification around $s$.

By rerouting the given $s$-$t$ linkages $\mathcal{P}$ and $\mathcal{Q}$ around
$s$ and $t$, we obtain linkages $\mathcal{P}^{\prime}$ and
$\mathcal{Q}^{\prime}$ from $\\{s_{1},\dots,s_{k}\\}$ to
$\\{t_{1},\dots,t_{k}\\}$ in $G^{\prime}$. Note that the restrictions of
$\mathcal{P}$ and $\mathcal{Q}$ to $G\setminus\\{s,t\\}$ coincide with those
of $\mathcal{P}^{\prime}$ and $\mathcal{Q}^{\prime}$, respectively. Then, we
can take $\mathcal{P}^{\prime}$ and $\mathcal{Q}^{\prime}$ so that
$|\mu(\mathcal{P}^{\prime},\mathcal{Q}^{\prime})|\leq|V|$. Furthermore, by
using at most $|V|$ concentric cycles around $s$ and $t$, we can reroute the
linkages so that the value $\mu(\mathcal{P}^{\prime},\mathcal{Q}^{\prime})$
decreases or increases by one. Therefore, by using $p\geq|V|^{2}$ concentric
cycles, we can reroute $\mathcal{P}^{\prime}$ and $\mathcal{Q}^{\prime}$ so
that $\mu(\mathcal{P}^{\prime},\mathcal{Q}^{\prime})$ becomes zero.

By Theorem 4.2, $\mathcal{P}^{\prime}$ is reconfigurable to
$\mathcal{Q}^{\prime}$ in $G^{\prime}$ (in terms of Disjoint Paths
Reconfiguration). Then, the reconfiguration sequence from
$\mathcal{P}^{\prime}$ to $\mathcal{Q}^{\prime}$ corresponds to that from
$\mathcal{P}$ to $\mathcal{Q}$ in $G$ (in terms of Disjoint $s$-$t$ Paths
Reconfiguration). Therefore, $\mathcal{P}$ is reconfigurable to $\mathcal{Q}$
in $G$. ∎

See 1.4

###### Proof.

Suppose that we are given a planar graph $G=(V,E)$ with $s,t\in V$ and $s$-$t$
linkages $\mathcal{P}=\\{P_{1},\dots,P_{k}\\}$ and
$\mathcal{Q}=\\{Q_{1},\dots,Q_{k}\\}$ in $G$. We first test whether $G$ has an
$s$-$t$ separator of size $k$. If there is no such a separator, then we can
immediately conclude that $\mathcal{P}$ is reconfigurable to $\mathcal{Q}$ by
Theorem 1.5.

Suppose that $G$ has an $s$-$t$ separator of size $k$. Let $X$ be the
inclusionwise minimal vertex set subject to $s\in X$ and $N(X)$ is an $s$-$t$
separator of size $k$. Note that such $X$ is uniquely determined by the
submodularity of $|N(X)|$ and it can be computed in polynomial time by a
standard minimum cut algorithm. Similarly, let $Y$ be the unique inclusionwise
minimal vertex set subject to $t\in Y$ and $N(Y)$ is an $s$-$t$ separator of
size $k$. Let $U=N(X)$, $W=N(Y)$, $G_{1}=G[X\cup U]$, $G_{2}=G\setminus(X\cup
Y)$, and $G_{3}=G[Y\cup W]$; see Figure 9. Since $V(P_{i})\cap U$ and
$V(P_{i})\cap W$ do not change in the reconfiguration, we can consider the
reconfiguration in $G_{1}$, $G_{2}$, and $G_{3}$, separately.

Figure 9: Construction of $G_{1}$, $G_{2}$, and $G_{3}$.

We first consider the reconfiguration in $G_{1}$. Observe that each path in
$\mathcal{P}$ contains exactly one vertex in $U$, and the restriction of
$\mathcal{P}$ to $G_{1}$ consists of $k$ paths from $s$ to $U$ that are
vertex-disjoint except at $s$. The same for $\mathcal{Q}$. By the minimality
of $X$, $G_{1}$ contains no vertex set of size $k$ that separates $\\{s\\}$
and $U$. Therefore, by the same argument as Theorem 1.5, the restriction of
$\mathcal{P}$ to $G_{1}$ is reconfigurable to that of $\mathcal{Q}$.

If $U\cap W\neq\emptyset$, then $G\setminus X$ contains no vertex set of size
$k$ that separates $U$ and $\\{t\\}$ by the minimality of $Y$. In such a case,
by shrinking $U$ to a single vertex and by applying the same argument as
above, the restriction of $\mathcal{P}$ to $G\setminus X$ is reconfigurable to
that of $\mathcal{Q}$. By combining the reconfiguration in $G_{1}$ and that in
$G\setminus X$, we obtain a reconfiguration sequence from $\mathcal{P}$ to
$\mathcal{Q}$.

Therefore, it suffices to consider the case when $U\cap W=\emptyset$. In the
same way as $G_{1}$, we see that the restriction of $\mathcal{P}$ to $G_{3}$
is reconfigurable to that of $\mathcal{Q}$. This shows that the
reconfigurability from $\mathcal{P}$ to $\mathcal{Q}$ in $G$ is equivalent to
that in $G_{2}$. By changing the indices if necessary, we may assume that
$P_{i}\cap U=Q_{i}\cap U$ for $i\in[k]$. If $P_{i}\cap W\neq Q_{i}\cap W$ for
some $i\in[k]$, then we can conclude that $\mathcal{P}$ is not reconfigurable
to $\mathcal{Q}$. Otherwise, let $\mathcal{P}^{\prime}$ and
$\mathcal{Q}^{\prime}$ be the restrictions of $\mathcal{P}$ and $\mathcal{Q}$
to $G_{2}$, respectively. Since
$(G_{2},\mathcal{P}^{\prime},\mathcal{Q}^{\prime})$ is a one-face or two-face
instance of Disjoint Paths Reconfiguration, we can solve it in polynomial time
by Proposition 4.1 and Theorem 1.3. Therefore, we can test the
reconfigurability from $\mathcal{P}$ to $\mathcal{Q}$ in polynomial time; see
Algorithm 2. ∎

Input: A planar graph $G$ and $s$-$t$ linkages $\mathcal{P}$ and
$\mathcal{Q}$.

Output: Is $\mathcal{P}$ reconfigurable to $\mathcal{Q}$?

1 Compute $X$ and $Y$ together with $s$-$t$ separators $U$ and $W$ of size
$k$;

2 if  _such separators do not exist or $U\cap W\neq\emptyset$_ then

3 return _YES_

4else

5 Construct $G_{2}=G\setminus(X\cup Y)$;

6 Change the indices so that $P_{i}\cap U=Q_{i}\cap U$ for $i\in[k]$;

7 if  _$P_{i}\cap W\neq Q_{i}\cap W$ for some $i\in[k]$_ then

8 return _NO_

9 else

10 Let $\mathcal{P}^{\prime}$ and $\mathcal{Q}^{\prime}$ be the restrictions
of $\mathcal{P}$ and $\mathcal{Q}$ to $G_{2}$;

11 if  _$(G_{2},\mathcal{P}^{\prime},\mathcal{Q}^{\prime})$ is a YES-instance
of DPR_ then

12 return _YES_

13 else

14 return _NO_

Algorithm 2 Algorithm for planar $s$-$t$ paths reconfiguration

##  5 Proof of Theorem 4.2

The necessity (“only if” part) in Theorem 4.2 is immediately derived from
Corollary 3.5.

In what follows in this section, we show the sufficiency (“if” part) in
Theorem 4.2, which is one of the main technical contributions in this paper.
Assume that $\mu(\mathcal{P},\mathcal{Q})=0$ and there is no terminal
separator of size $k$. The objective is to show that $\mathcal{P}$ is
reconfigurable to $\mathcal{Q}$. Our proof is constructive, and based on
topological arguments. A similar technique is used in [30, 35, 36, 41].

###  5.1 Preliminaries for the Proof

Let $C$ be a simple curve connecting the boundaries of $S$ and $T$ such that
$C$ contains no vertex in $G$, $C$ intersects the boundaries of $S$ and $T$
only at its endpoints, and $\mu(P_{i},C)=0$ for $i\in[k]$. Note that such $C$
always exists, because the last condition is satisfied if $C$ is disjoint from
$\mathcal{P}$. Note also that $\mu(Q_{i},C)=0$ holds for $i\in[k]$, because
$\mu(\mathcal{P},\mathcal{Q})=0$.

Since $T$ is the outer face, $\mathbb{R}^{2}\setminus(S\cup T)$ forms an
annulus (or a cylinder).222More precisely, the annulus is degenerated when
$\partial{S}\cap\partial{T}\neq\emptyset$, but the same argument works even
for this case. Thus, by cutting it along $C$, we obtain a rectangle whose
boundary consists of $\partial{S}$, $\partial{T}$, and two copies of $C$. We
take infinite copies of this rectangle and glue them together to obtain an
infinite long strip $R$. That is, for $j\in\mathbb{Z}$, let $C^{j}$ be a copy
of $C$, let $R^{j}$ be a copy of the rectangle whose boundary contains $C^{j}$
and $C^{j+1}$, and define $R=\bigcup_{j\in\mathbb{Z}}R^{j}$; see Figure 10. By
taking $C$ appropriately, we may assume that the copies of $s_{1},\dots,s_{k}$
lie on the boundary of $R^{j}$ in this order so that $s_{1}$ is closest to
$C^{j}$ and $s_{k}$ is closest to $C^{j+1}$. The same for $t_{1},\dots,t_{k}$.
Note that $R$ is called the _universal cover_ of
$\mathbb{R}^{2}\setminus(S\cup T)$ in the terminology of topology.

Since $G$ is embedded on $\mathbb{R}^{2}\setminus(S\cup T)$, this operation
naturally defines an infinite periodic graph $\hat{G}=(\hat{V},\hat{E})$ on
$R$ that consists of copies of $G$. A path in $\hat{G}$ is identified with the
corresponding curve in $R$. For $v\in V$ and $j\in\mathbb{Z}$, let
$v^{j}\in\hat{V}$ denote the unique vertex in $R^{j}$ that corresponds to $v$.
Since $\mu(P_{i},C)=0$ for $i\in[k]$, each path in $\hat{G}$ corresponding to
$P_{i}$ is from $s^{j}_{i}$ to $t^{j}_{i}$ for some $j\in\mathbb{Z}$, and we
denote such a path by $P^{j}_{i}$. We define $Q^{j}_{i}$ in the same way.
Since $\cal P$ and $\mathcal{Q}$ are linkages in $G$, $\\{P^{j}_{i}\mid
i\in[k],\ j\in\mathbb{Z}\\}$ and $\\{Q^{j}_{i}\mid i\in[k],\
j\in\mathbb{Z}\\}$ are sets of vertex-disjoint paths in $\hat{G}$.

Figure 10: (Left) Curve $C$ in $\mathbb{R}^{2}\setminus(S\cup T)$. (Right)
Construction of $R$.

A path in $\hat{G}$ connecting the boundary of $R$ corresponding to
$\partial{S}$ and that corresponding to $\partial{T}$ is called an _$\hat{S}$
-$\hat{T}$ path_. For an $\hat{S}$-$\hat{T}$ path $P$, let $L(P)$ be the
region of $R\setminus P$ that is on the “left-hand side” of $P$. Formally, let
$r$ be a point in $R^{j}$ for sufficiently small $j$, and define $L(P)$ as the
set of points $x\in R\setminus P$ such that any curve in $R$ between $r$ and
$x$ crosses $P$ an even number of times; see Figure 11. For two
$\hat{S}$-$\hat{T}$ paths $P$ and $Q$, we denote $P\preceq Q$ if
$L(P)\subseteq L(Q)$, and denote $P\prec Q$ if $L(P)\subsetneq L(Q)$. For two
linkages $\mathcal{P}=(P_{1},\dots,P_{k})$ and
$\mathcal{Q}=(Q_{1},\dots,Q_{k})$ in $G$ with $\mu(P_{i},C)=\mu(Q_{i},C)=0$
for $i\in[k]$, we denote $\mathcal{P}\preceq\mathcal{Q}$ if $P^{j}_{i}\preceq
Q^{j}_{i}$ for any $i\in[k]$ and $j\in\mathbb{Z}$, and denote
$\mathcal{P}\prec\mathcal{Q}$ if $\mathcal{P}\preceq\mathcal{Q}$ and
$\mathcal{P}\neq\mathcal{Q}$.

Figure 11: Definition of $L(P)$.

###  5.2 Case When $\mathcal{P}\preceq\mathcal{Q}$

In this subsection, we consider the case when $\mathcal{P}\preceq\mathcal{Q}$,
and the general case will be dealt with in Section 5.3. In order to show that
$\mathcal{P}$ is reconfigurable to $\mathcal{Q}$, we show the following lemma.

######  Lemma 5.1.

If $\mathcal{P}\prec\mathcal{Q}$, then there exists a linkage
$\mathcal{P}^{\prime}$ such that
$\mathcal{P}\leftrightarrow\mathcal{P}^{\prime}$ and
$\mathcal{P}\prec\mathcal{P}^{\prime}\preceq\mathcal{Q}$.

###### Proof.

To derive a contradiction, assume that such $\mathcal{P^{\prime}}$ does not
exist. Let $\hat{W}:=\\{\hat{v}\in\hat{V}\mid\hat{v}\in P^{j}_{i}\setminus
Q^{j}_{i}\mbox{ for some }i\in[k]\mbox{ and }j\in\mathbb{Z}\\}$ and let $W$ be
the subset of $V$ corresponding to $\hat{W}$. If $W=\emptyset$, then take an
index $i\in[k]$ such that $P_{i}\neq Q_{i}$ and let
$\mathcal{P}^{\prime}=(P^{\prime}_{1},\dots,P^{\prime}_{k})$ be the set of
paths obtained from $\mathcal{P}$ by replacing $P_{i}$ with $Q_{i}$. Since
$\mathcal{Q}$ is a linkage and all the vertices in $P^{\prime}_{h}$ are
contained in $Q_{h}$ for any $h\in[k]$, $\mathcal{P}^{\prime}$ is a desired
linkage, which contradicts the assumption.

Thus, it suffices to consider the case when $W\neq\emptyset$. Let $u\in W$.
Let $\hat{u}\in\hat{W}$ be a vertex corresponding to $u$ and let $i\in[k]$ and
$j\in\mathbb{Z}$ be the indices such that $\hat{u}\in P^{j}_{i}\setminus
Q^{j}_{i}$. Since $\hat{u}\in P^{j}_{i}\setminus Q^{j}_{i}$ implies
$\hat{u}\in L(Q^{j}_{i})\setminus L(P^{j}_{i})$, there exists a face $\hat{F}$
of $\hat{G}$ such that $\partial{\hat{F}}$ contains an edge of $P^{j}_{i}$
incident to $\hat{u}$ and $\hat{F}\subseteq L(Q^{j}_{i})\setminus
L(P^{j}_{i})$. Define $(P^{j}_{i})^{\prime}$ as the $s^{j}_{i}$-$t^{j}_{i}$
path in $\hat{G}$ with maximal $L((P^{j}_{i})^{\prime})$ subject to
$(P^{j}_{i})^{\prime}\subseteq P^{j}_{i}\cup\partial{\hat{F}}$; see Figure 12.
Note that such a path is uniquely determined and
$P^{j}_{i}\prec(P^{j}_{i})^{\prime}\preceq Q^{j}_{i}$.

Figure 12: The blue thick paths are $P^{j}_{i}$ and $P^{j}_{i+1}$, and the red
dashed path is $(P^{j}_{i})^{\prime}$. There exists a vertex
$\hat{v}\in\partial{\hat{F}}\cap P^{j}_{i+1}$.

Let $P^{\prime}_{i}$ be the $s_{i}$-$t_{i}$ path in $G$ that corresponds to
$(P^{j}_{i})^{\prime}$. If $P^{\prime}_{i}$ is disjoint from $P_{h}$ for any
$h\in[k]\setminus\\{i\\}$, then we can obtain a desired linkage
$\mathcal{P}^{\prime}$ from $\mathcal{P}$ by replacing $P_{i}$ with
$P^{\prime}_{i}$, which contradicts the assumption. Therefore,
$P^{\prime}_{i}$ intersects $P_{h}$ for some $h\in[k]\setminus\\{i\\}$. This
together with $P^{j}_{i}\prec(P^{j}_{i})^{\prime}$ shows that
$(P^{j}_{i})^{\prime}$ intersects $P^{j}_{i+1}$, where $P^{j}_{k+1}$ means
$P^{j+1}_{1}$. Since $P^{j}_{i}$ and $P^{j}_{i+1}$ are vertex-disjoint, the
intersection of $(P^{j}_{i})^{\prime}$ and $P^{j}_{i+1}$ is contained in
$\partial{\hat{F}}$, which implies that $\partial{\hat{F}}\cap P^{j}_{i+1}$
contains a vertex $\hat{v}\in\hat{V}$; see Figure 12 again. Since
$\hat{F}\subseteq L(Q^{j}_{i})$, we obtain $\hat{v}\in L(Q^{j}_{i})\cup
Q^{j}_{i}\subseteq L(Q^{j}_{i+1})$, and hence $\hat{v}\not\in Q^{j}_{i+1}$.
Let $v$ and $F$ be the vertex and the face of $G$ that correspond to $\hat{v}$
and $\hat{F}$, respectively. Then, $\hat{v}\in P^{j}_{i+1}\setminus
Q^{j}_{i+1}$ implies that $\hat{v}\in\hat{W}$ and $v\in W$. Let $J$ be a curve
in $F$ from $u$ to $v$.

By the above argument, for any $u\in W$ on $P_{i}$, there exist a vertex $v\in
W$ on $P_{i+1}$ and a curve $J$ from $u$ to $v$ contained in some face of $G$.
By repeating this argument and by shifting the indices of $P_{i}$ if
necessary, we obtain $v_{i}$ and $J_{i}$ for $i=1,2,\ldots$ such that
$v_{i}\in W$ is on $P_{i}$ (where the index is modulo $k$) and $J_{i}$ is a
curve from $v_{i}$ to $v_{i+1}$ contained in some face. We consider the curve
$J$ obtained by concatenating $J_{1},J_{2},\ldots$ in this order. Since $|W|$
is finite, this curve visits the same point more than once, and hence it
contains a simple closed curve $C^{*}$. Since $C^{*}$ is simple and visits
vertices on $P_{i},P_{i+1},\dots$ in this order, $C^{*}$ surrounds $S$ exactly
once in the clockwise direction; see Figure 13. In particular, $C^{*}$
contains exactly one vertex on $P_{i}$ for each $i\in[k]$. Let $U$ be the set
of vertices in $V$ contained in $C^{*}$. Then, $|U|=k$ and $G\setminus U$ has
no path between $\\{s_{1},\dots,s_{k}\\}$ and $\\{t_{1},\dots,t_{k}\\}$ by the
choice of $C^{*}$. Furthermore, $U$ contains no terminals, because $U\subseteq
W$ and $W$ contains no terminals. Therefore, $U$ is a terminal separator of
size $k$, which contradicts the assumption. ∎

Figure 13: Each blue path represents $P_{i}$. The dotted curve is part of $J$
and the red dotted thick curve is $C^{*}$.

As long as $\mathcal{P}\neq\mathcal{Q}$, we apply this lemma and replace
$\mathcal{P}$ with $\mathcal{P}^{\prime}$, repeatedly. Then, this procedure
terminates when $\mathcal{P}=\mathcal{Q}$, and gives a reconfiguration
sequence from $\mathcal{P}$ to $\mathcal{Q}$. This completes the proof for the
case when $\mathcal{P}\preceq\mathcal{Q}$.

###  5.3 General Case

In this subsection, we consider the case when $\mathcal{P}\preceq\mathcal{Q}$
does not necessarily hold. For $i\in[k]$ and $j\in\mathbb{Z}$, define
$P^{j}_{i}\lor Q^{j}_{i}$ as the $s^{j}_{i}$-$t^{j}_{i}$ path in $\hat{G}$
with maximal $L(P^{j}_{i}\lor Q^{j}_{i})$ subject to $P^{j}_{i}\lor
Q^{j}_{i}\subseteq P^{j}_{i}\cup Q^{j}_{i}$; see Figure 14. Note that such a
path is uniquely determined, $P^{j}_{i}\preceq P^{j}_{i}\lor Q^{j}_{i}$, and
$Q^{j}_{i}\preceq P^{j}_{i}\lor Q^{j}_{i}$. Since $\hat{G}$ is periodic, for
any $j\in\mathbb{Z}$, $P^{j}_{i}\lor Q^{j}_{i}$ corresponds to a common
$s_{i}$-$t_{i}$ walk $P_{i}\lor Q_{i}$ in $G$. We now show that
$\mathcal{P}\lor\mathcal{Q}:=(P_{1}\lor Q_{1},\dots,P_{k}\lor Q_{k})$ is a
linkage in $G$.

Figure 14: Construction of $P^{j}_{i}\lor Q^{j}_{i}$.

######  Lemma 5.2.

$\mathcal{P}\lor\mathcal{Q}$ is a linkage in $G$.

###### Proof.

We first show that $P_{i}\lor Q_{i}$ is a path for each $i\in[k]$. Assume to
the contrary that $P_{i}\lor Q_{i}$ visits a vertex $v\in V$ more than once.
Then, for $j\in\mathbb{Z}$, there exist $j_{1},j_{2}\in\mathbb{Z}$ with
$j_{1}<j_{2}$ such that $P^{j}_{i}\lor Q^{j}_{i}$ contains both $v^{j_{1}}$
and $v^{j_{2}}$. Since the path $P^{j}_{i}\lor Q^{j}_{i}$ is contained in the
subgraph $P^{j}_{i}\cup Q^{j}_{i}$, without loss of generality, we may assume
that $P^{j}_{i}$ contains $v^{j_{2}}$. This shows that $v^{j_{1}}\in
L(P^{j}_{i})\subseteq L(P^{j}_{i}\lor Q^{j}_{i})$, which contradicts that
$v^{j_{1}}$ is contained in $P^{j}_{i}\lor Q^{j}_{i}$.

We next show that $P_{1}\lor Q_{1},\dots,P_{k}\lor Q_{k}$ are pairwise vertex-
disjoint. Assume to the contrary that $P_{i}\lor Q_{i}$ and
$P_{i^{\prime}}\lor Q_{i^{\prime}}$ contain a common vertex $v\in V$ for
distinct $i,i^{\prime}\in[k]$. Since $\hat{G}$ is periodic, there exist
$j,j^{\prime}\in\mathbb{Z}$ such that $P^{j}_{i}\lor Q^{j}_{i}$ and
$P^{j^{\prime}}_{i^{\prime}}\lor Q^{j^{\prime}}_{i^{\prime}}$ contain $v^{0}$
(i.e., the copy of $v$ in $R^{0}$). We may assume that $(j,i)$ is smaller than
$(j^{\prime},i^{\prime})$ in the lexicographical ordering, that is, either
$j<j^{\prime}$ holds or $j=j^{\prime}$ and $i<i^{\prime}$ hold. Since
$P^{j}_{i}\lor Q^{j}_{i}\subseteq P^{j}_{i}\cup Q^{j}_{i}$, we may also assume
that $v^{0}\in P^{j}_{i}$ by changing the roles of $P^{j}_{i}$ and $Q^{j}_{i}$
if necessary. Then, we obtain $v^{0}\in P^{j}_{i}\subseteq
L(P^{j^{\prime}}_{i^{\prime}})\subseteq L(P^{j^{\prime}}_{i^{\prime}}\lor
Q^{j^{\prime}}_{i^{\prime}})$, which contradicts that $v^{0}$ is contained in
$P^{j^{\prime}}_{i^{\prime}}\lor Q^{j^{\prime}}_{i^{\prime}}$. ∎

We also see that $\mu(P_{i}\lor Q_{i},C)=0$ for $i\in[k]$ by definition, and
hence $\mu(\mathcal{P},\mathcal{P}\lor\mathcal{Q})=0$. Since
$\mathcal{P}\preceq\mathcal{P}\lor\mathcal{Q}$ and
$\mu(\mathcal{P},\mathcal{P}\lor\mathcal{Q})=0$, $\cal P$ is reconfigurable to
$\mathcal{P}\lor\mathcal{Q}$ as described in Section 5.2. Similarly, $\cal Q$
is reconfigurable to $\mathcal{P}\lor\mathcal{Q}$, which implies that
$\mathcal{P}\lor\mathcal{Q}$ is reconfigurable to $\cal Q$. By combining them,
we see that $\cal P$ is reconfigurable to $\cal Q$, which completes the proof
of the sufficiency in Theorem 4.2.

##  6 $\mathsf{PSPACE}$-Completeness

We first observe that Disjoint Paths Reconfiguration and Disjoint $s$-$t$
Paths Reconfiguration are in $\mathsf{PSPACE}$ by using
$\mathsf{PSPACE}=\mathsf{NPSPACE}$ (a corollary of Savitch’s theorem [48]). As
a certificate, we receive a reconfiguration sequence. In our polynomial-space
algorithm, we read linkages in the certificate one by one, and check whether
the linkage is indeed a linkage and whether two consecutive linkages are
obtained by a single reconfiguration step. At each step, the working memory
only requires to store the graph $G$ and two consecutive linkages. Thus, the
algorithm runs in polynomial space. This is a non-deterministic algorithm, but
by $\mathsf{PSPACE}=\mathsf{NPSPACE}$, we conclude that the problems belong to
$\mathsf{PSPACE}$.

For the proof of $\mathsf{PSPACE}$-hardness, we reduce the _nondeterministic
constraint logic reconfiguration_ (NCL reconfiguration) to our problem. In the
NCL reconfiguration, we consider an undirected cubic graph, where each edge is
associated with weight one or two and each vertex is incident to three
weight-$2$ edges (called an _OR vertex_) or incident to one weight-$2$ edge
and two weight-$1$ edges (called an _AND vertex_). We call such an undirected
graph an _AND/OR graph_. An _NCL configuration_ is an orientation of the edges
of an AND/OR graph in which at each vertex the total weight of the incoming
arcs is at least two. A _flip_ of an arc is a process of changing the
direction of the arc. In the NCL reconfiguration, we are given two NCL
configurations of an AND/OR graph, and need to determine whether we can obtain
one from the other by a sequence of flips in such a way that all the
intermediate orientations are NCL configurations. It is known that the NCL
reconfiguration is $\mathsf{PSPACE}$-complete [23], even when the AND/OR graph
is planar and of bounded bandwidth [58].

###  6.1 General Graphs and Two Paths

See 1.1

###### Proof.

We have already observed that the problem is in $\mathsf{PSPACE}$. To show the
$\mathsf{PSPACE}$-hardness, we now give a transformation of a given AND/OR
graph $H=(V(H),E(H))$ to an undirected graph $G=(V(G),E(G))$. Each weight-$2$
edge $e=\\{u,v\\}\in E(H)$ of $H$ is mapped to the following _weight- $2$ edge
gadget_ $G_{e}$ (see Figure 15):

$\displaystyle V(G_{e})$
$\displaystyle=\\{w_{e,u},w_{e,v},r_{e,1},r_{e,2}\\},$ $\displaystyle
E(G_{e})$
$\displaystyle=\\{\\{w_{e,u},r_{e,1}\\},\\{w_{e,u},r_{e,2}\\},\\{w_{e,v},r_{e,1}\\},\\{w_{e,v},r_{e,2}\\}\\}.$

Similarly, each weight-$1$ edge $e=\\{u,v\\}\in E(H)$ of $H$ is mapped to the
following _weight- $1$ edge gadget_ $G_{e}$ (see Figure 15):

$\displaystyle V(G_{e})$
$\displaystyle=\\{w_{e,u},w_{e,v},b_{e,1},b_{e,2}\\},$ $\displaystyle
E(G_{e})$
$\displaystyle=\\{\\{w_{e,u},b_{e,1}\\},\\{w_{e,u},b_{e,2}\\},\\{w_{e,v},b_{e,1}\\},\\{w_{e,v},b_{e,2}\\}\\}.$

Figure 15: (Left) A weight-$2$ edge gadget. (Right) A weight-$1$ edge gadget.

Let $v\in V(H)$ be an OR vertex, and $e,f,g\in E(H)$ be three weight-$2$ edges
incident to $v$. Then, $v$ is mapped to the following _OR vertex gadget_
$G_{v}$ (see Figure 16):

$\displaystyle V(G_{v})$
$\displaystyle=\\{w_{e,v},w_{f,v},w_{g,v},b_{v,1},b_{v,2}\\},$ $\displaystyle
E(G_{v})$
$\displaystyle=\\{\\{w_{e,v},b_{v,1}\\},\\{w_{e,v},b_{v,2}\\},\\{w_{f,v},b_{v,1}\\},\\{w_{f,v},b_{v,2}\\},$
$\displaystyle\qquad\\{w_{g,v},b_{v,1}\\},\\{w_{g,v},b_{v,2}\\}\\}.$

Note that the vertices with the same label are identified.

Figure 16: (Left) An OR vertex gadget. (Right) An AND vertex gadget.

An AND vertex $v\in V(H)$ that is incident to one weight-$2$ edge $e$ and two
weight-$1$ edges $f,g$ is mapped to the following _AND vertex gadget_ $G_{v}$
(see Figure 16):

$\displaystyle V(G_{v})$
$\displaystyle=\\{w_{e,v},w_{f,v},w_{g,v},r_{v,1},r_{v,2},b_{v,1},b_{v,2},k_{v}\\},$
$\displaystyle E(G_{v})$
$\displaystyle=\\{\\{w_{e,v},b_{v,1}\\},\\{w_{e,v},b_{v,2}\\},\\{w_{f,v},r_{v,1}\\},\\{w_{g,v},r_{v,2}\\},$
$\displaystyle\qquad\\{r_{v,1},k_{v}\\},\\{r_{v,2},k_{v}\\},\\{b_{v,1},k_{v}\\},\\{b_{v,2},k_{v}\\},\\{w_{f,v},w_{g,v}\\}\\}.$

Define

$V(G)=\\{s,t\\}\cup\bigcup_{v\in V(H)}V(G_{v})\cup\bigcup_{e\in
E(H)}V(G_{e}).$

A vertex of $V(G)$ is _red_ if it is of the form $r_{x,i}$ for some
vertex/edge $x\in V(H)\cup E(H)$ and $i\in\\{1,2\\}$; a vertex of $V(G)$ is
_blue_ if it is of the form $b_{x,i}$ for some vertex/edge $x\in V(H)\cup
E(H)$ and $i\in\\{1,2\\}$; a vertex of $V(G)$ is _white_ if it is of the form
$w_{e,v}$ for some vertex $v\in V(H)$ and edge $e\in E(H)$; a vertex of $V(G)$
is _black_ if it is $s$, $t$ or of the form $k_{v}$ for some vertex $v\in
V(H)$. The number of red vertices is equal to
$2|V^{\mathrm{a}}(H)|+2|E_{2}(H)|$, where $V^{\mathrm{a}}(H)$ is the set of
AND vertices and $E_{2}(H)$ is the set of weight-$2$ edges; The number of blue
vertices is equal to $2|V(H)|+2|E_{1}(H)|$, where $E_{1}(H)$ is the set of
weight-$1$ edges; The number of white vertices is equal to $3|V(H)|=2|E(H)|$;
The number of black vertices is equal to $2+|V^{\mathrm{a}}(H)|$.

Assume that the elements of $V^{\mathrm{a}}(H)\cup E_{2}(H)$ are arbitrarily
ordered as $x_{1},x_{2},\dots,x_{R}$ and the elements of $V(H)\cup E_{1}(H)$
are arbitrarily ordered as $y_{1},y_{2},\dots,y_{B}$. Then, define

$\displaystyle E(G)$ $\displaystyle=\bigcup_{v\in
V(H)}E(G_{v})\cup\bigcup_{e\in E(H)}E(G_{e})$
$\displaystyle\qquad\cup\\{\\{r_{x_{i},2},r_{x_{i+1},1}\\}\mid
i\in\\{1,2,\dots,R-1\\}\\}$
$\displaystyle\qquad\cup\\{\\{b_{y_{i},2},b_{y_{i+1},1}\\}\mid
i\in\\{1,2,\dots,B-1\\}\\}$
$\displaystyle\qquad\cup\\{\\{s,r_{x_{1},1}\\},\\{s,b_{y_{1},1}\\}\\}\cup\\{\\{r_{x_{R},2},t\\},\\{b_{y_{B},2},t\\}\\}.$

This completes the construction of $G$. Figure 17 may help the reader
understand.

We now describe the way how an NCL configuration of $H$ translates to an
$s$-$t$ linkage $\\{P_{1},P_{2}\\}$ of $G$. We force that $P_{1}$ goes through
all the red vertices and $P_{2}$ goes through all the blue vertices. As a
sequence of vertices, $P_{1}$ is constructed as follows.

  1. 1.

The path starts at $s$. Let $r_{x_{0},2}=s$.

  2. 2.

Now we iterate over $i\in\\{1,\dots,R\\}$. As an invariant at the beginning of
the iteration, we assume that we have just visited the vertex $r_{x_{i-1},2}$.
Then, the path continues to $r_{x_{i},1}$. We consider two separate cases.

    1. (a)

Consider the case where $x_{i}=\\{u,v\\}$ is a weight-$2$ edge. Let the edge
be oriented from $u$ to $v$ in the NCL configuration. Then, the path visits
$w_{x_{i},u}$, and continues to $r_{x_{i},2}$.

    2. (b)

Consider the case where $x_{i}$ is an AND vertex that is incident to one
weight-$2$ edge $e$ and two weight-$1$ edges $f$ and $g$. If $e$ is oriented
toward $x_{i}$, then the path visits $k_{x_{i}}$ and continues to
$r_{x_{i},2}$. If $e$ is not oriented toward $x_{i}$, then the path visits
$w_{f,x_{i}},w_{g,x_{i}}$ and continues to $r_{x_{i},2}$.

  3. 3.

After the whole iteration, the path now visits $r_{x_{R},2}$. Then, the path
continues to $t$ and we finish the construction of $P_{1}$.

Similarly, as a sequence of vertices, $P_{2}$ is constructed as follows.

  1. 1.

The path starts at $s$. Let $b_{y_{0},2}=s$.

  2. 2.

Now we iterate over $i\in\\{1,\dots,B\\}$. As an invariant at the beginning of
the iteration, we assume that we have just visited the vertex $b_{y_{i-1},2}$.
Then, the path continues to $b_{y_{i},1}$. We consider three separate cases.

    1. (a)

Consider the case where $y_{i}=\\{u,v\\}$ is a weight-$1$ edge. Let the edge
be oriented from $u$ to $v$ in the NCL configuration. Then, the path visits
$w_{y_{i},u}$, and continues to $b_{y_{i},2}$.

    2. (b)

Consider the case where $y_{i}$ is an OR vertex that is incident to three
weight-$2$ edges $e$, $f$, and $g$. At least one of those edges is directed
toward $y_{i}$. Let $e$ be such an edge. Then, the path visits $w_{e,y_{i}}$
and continues to $b_{y_{i},2}$.

    3. (c)

Consider the case where $y_{i}$ is an AND vertex that is incident to one
weight-$2$ edge $e$ and two weight-$1$ edges $f$ and $g$. If $e$ is oriented
toward $y_{i}$, then the path visits $w_{e,y_{i}}$ and continues to
$b_{y_{i},2}$. If $e$ is not oriented toward $y_{i}$, then the path visits
$k_{y_{i}}$ and continues to $b_{y_{i},2}$.

  3. 3.

After the whole iteration, the path now visits $b_{y_{B},2}$. Then, the path
continues to $t$ and we finish the construction of $P_{2}$.

The construction is illustrated in Figure 17. The constructed $s$-$t$ linkage
$\mathcal{P}=\\{P_{1},P_{2}\\}$ is _created_ from the NCL configuration
$\sigma$. The following claim ensures that the constructed paths are indeed
vertex-disjoint.

Figure 17: Mapping an NCL configuration to an $s$-$t$ linkage
$\\{P_{1},P_{2}\\}$. In the NCL configuration, the vertex label A stands for
an AND vertex, and the vertex label O stands for an OR vertex. The path
$P_{1}$ is colored red and the path $P_{2}$ is colored blue.

######  Claim 6.1.

The paths $P_{1}$ and $P_{2}$ are internally vertex-disjoint.

###### Proof.

The paths $P_{1}$ and $P_{2}$ start at $s$ and ends at $t$. By the
construction, the red vertices are visited by $P_{1}$ only and the blue
vertices are visited by $P_{2}$ only. Hence, if they are not vertex-disjoint,
they will share a white vertex or a black vertex.

Suppose that they share a white vertex. Let one of the shared white vertices
be of the form $w_{e,v}$ for some edge $e\in E(H)$ and an end-vertex $v$ of
$e$.

As the first case, suppose that $v$ is an OR vertex. Note that $e$ is a
weight-$2$ edge in this case. Since $w_{e,v}$ is visited by $P_{1}$, by Step
2(a), $e$ is oriented from $v$ to the other end-vertex of $e$. Since $w_{e,v}$
is visited by $P_{2}$, by Step 2(b), $e$ is oriented toward $v$. Thus, the
orientation of $e$ is in conflict and we reach a contradiction.

As the second case, suppose that $v$ is an AND vertex. We further distinguish
two cases. First, consider the case where $e$ is a weight-$2$ edge. Then,
since $w_{e,v}$ is visited by $P_{1}$, by Step 2(a), $e$ is oriented from $v$
to the other end-vertex of $e$. On the other hand, since $w_{e,v}$ is visited
by $P_{2}$, by Step 2(c), $e$ is oriented toward $v$. Thus, the orientation of
$e$ is in conflict and we reach a contradiction.

Second, consider the case where $e$ is a weight-$1$ edge. Then, since
$w_{e,v}$ is visited by $P_{2}$, by Step 2(a), $e$ is oriented from $v$. On
the other hand, since $w_{e,v}$ is visited by $P_{1}$, by Step 2(b), the
weight-$2$ edge incident to $v$ is not oriented toward $v$. They together mean
that the total weight of incoming arc to $v$ is at most one. This is a
contradiction since the orientation does not meet the requirement to be an NCL
configuration.

Next, suppose that $P_{1}$ and $P_{2}$ share a black vertex. Such a black
vertex only exists in an AND vertex gadget $G_{v}$, where $v$ is an AND vertex
of $H$ that is incident to one weight-$2$ edge $e$ and two weight-$1$ edges
$f$ and $g$. Namely, the black vertex is of the form $k_{v}$. Since $k_{v}$ is
visited by $P_{1}$, by Step 2(b), $e$ is oriented toward $v$. On the other
hand, since $k_{v}$ is visited by $P_{2}$, by Step 2(c), $e$ is not oriented
toward $v$. This is a contradiction.

In all cases, we derive a contradiction. Thus, $P_{1}$ and $P_{2}$ are
internally vertex-disjoint. ∎

We now study how a flip in an orientation in an NCL configuration corresponds
to a constant-length sequence of reconfiguration steps of paths.

######  Claim 6.2.

Let $\mathcal{P}=\\{P_{1},P_{2}\\}$ be an $s$-$t$ linkage of $G$ that is
created from an NCL configuration $\sigma$. If an NCL configuration
$\sigma^{\prime}$ is obtained from $\sigma$ by a flip of a single edge, then
an $s$-$t$ linkage $\mathcal{P}^{\prime}=\\{P^{\prime}_{1},P^{\prime}_{2}\\}$
of $G$ that is created from $\sigma^{\prime}$ can be obtained from
$\mathcal{P}$ by at most a constant number of reconfiguration steps in $G$.

###### Proof.

Assume that we are given an NCL configuration $\sigma$ of $H$. Let
$\mathcal{P}=\\{P_{1},P_{2}\\}$ be an $s$-$t$ linkage of $G$ that is created
from $\sigma$. By the construction, the path $P_{1}$ passes through all the
red vertices; the path $P_{2}$ passes through all the blue vertices.

As the first case, consider a flip of a weight-$1$ edge $f$ that connects two
AND vertices $u,v$ from $(u,v)$ to $(v,u)$. Then, the blue path $P_{2}$ passes
through $b_{f,1},w_{f,u},b_{f,2}$ of the weight-$1$ edge gadget in this order.
Let $P^{\prime}_{2}$ be a blue path that is created from the NCL configuration
obtained after flipping $(u,v$) to $(v,u)$. To obtain an $s$-$t$ linkage
$\\{P_{1},P^{\prime}_{2}\\}$, we replace the part $b_{f,1},w_{f,u},b_{f,2}$ of
$P_{2}$ with $b_{f,1},w_{f,v},b_{f,2}$.

This is possible only if $P_{1}$ does not pass through $w_{f,v}$; we now
observe this is indeed the case. If $P_{1}$ passes through $w_{f,v}$, then by
the construction of $P_{1}$, the path $P_{1}$ passes through
$r_{v,1},w_{f,v},w_{g,v},r_{v,2}$ in this order where $g$ is the other
weight-$1$ edge incident to $v$. This happens only when a unique weight-$2$
edge incident to $v$ is not oriented toward $v$. Therefore, after flipping to
$(v,u)$ the total sum of the incoming edges to $v$ will be $1$. This is a
contradiction to the property of an NCL configuration.

As the second case, consider a flip of a weight-$2$ edge $e$ that connects a
vertex $u$ and an AND vertex $v$ from $(u,v)$ to $(v,u)$. Then, the red path
$P_{1}$ passes through $r_{e,1},w_{e,u},r_{e,2}$ of the weight-$2$ edge gadget
in this order. Let $P^{\prime}_{1}$ be a red path that is created from the
orientation obtained after flipping to $(v,u)$. To obtain a family of
internally vertex-disjoint paths $P^{\prime}_{1},P_{2}$, we want to replace
the part $r_{e,1},w_{e,u},r_{e,2}$ of $P_{1}$ with $r_{e,1},w_{e,v},r_{e,2}$.

This is possible only if $P_{2}$ does not pass through $w_{e,v}$. However,
since $e$ is oriented toward $v$, $P_{2}$ passes through $w_{e,v}$. Thus, in
order to make $w_{e,v}$ vacant, we apply the following operations before the
above transformation. We first replace the part $r_{v,1}$, $k_{v}$, $r_{v,2}$
of $P_{1}$ by $r_{v,1}$, $w_{f,v}$, $w_{g,v}$, $r_{v,2}$, where $f$ and $g$
are weight-$1$ edges incident to $v$. This is possible since $f$ and $g$ are
oriented toward $v$ in $\sigma$. Next, we replace the part $b_{v,1}$,
$w_{e,v}$, $b_{v,2}$ of $P_{2}$ by $b_{v,1}$, $k_{v}$, $b_{v,2}$. This way, we
can make $w_{e,v}$ vacant with two extra reconfiguration steps.

As the third but final case, consider a flip of a weight-$2$ edge $e$ that
connects a vertex $u$ and an OR vertex $v$ from $(u,v)$ to $(v,u)$. Then, the
red path $P_{1}$ passes through $r_{e,1},w_{e,u},r_{e,2}$ of the weight-$2$
edge gadget in this order. Let $P^{\prime}_{1}$ be a red path that is created
from the orientation obtained after flipping to $(v,u)$. To obtain a family of
internally vertex-disjoint paths $P^{\prime}_{1},P_{2}$, we want to replace
the part $r_{e,1},w_{e,u},r_{e,2}$ of $P_{1}$ with $r_{e,1},w_{e,v},r_{e,2}$.

This is possible only if $P_{2}$ does not pass through $w_{e,v}$. If this is
the case, there is no problem. However, in some cases, $P_{2}$ indeed passes
through $w_{e,v}$. Then, we first replace the part $b_{v,1},w_{e,v},b_{v,2}$
with $b_{v,1},w_{f,v},b_{v,2}$ or $b_{v,1},w_{g,v},b_{v,2}$, where $f,g$ are
other weight-$2$ edges incident to $v$, to make $w_{e,v}$ vacant. We now
observe that this extra step can always be done. Suppose not. Then, all the
three vertices $w_{e,v},w_{f,v},w_{g,v}$ are occupied by $P_{2}$. This means
that the edges $e,f,g$ are oriented as they leave $v$, and the total sum of
edges incoming to $v$ is zero. This is a contradiction to the property of an
NCL configuration.

In the second and third cases above, if $u$ is an AND vertex, then we replace
the part $b_{u,1}$, $k_{u}$, $b_{u,2}$ of $P_{2}$ by $b_{u,1}$, $w_{e,u}$,
$b_{u,2}$, and replace the part $r_{u,1}$, $w_{f^{\prime},u}$,
$w_{g^{\prime},u}$, $r_{u,2}$ of $P_{1}$ by $r_{u,1}$, $k_{u}$, $r_{u,2}$,
where $f^{\prime},g^{\prime}$ are other weight-$2$ edges incident to $u$.
Then, we obtain an $s$-$t$ linkage of $G$ that is created from
$\sigma^{\prime}$. ∎

To argue the reverse direction of correspondence, we first observe that a
reconfiguration step maintains the property that the paths go through the red
and blue vertices.

######  Claim 6.3.

Let $\mathcal{P}=\\{P_{1},P_{2}\\}$ be an $s$-$t$ linkage of $G$ such that
$P_{1}$ goes through all the red vertices and $P_{2}$ goes through all the
blue vertices. If an $s$-$t$ linkage
$\mathcal{P}^{\prime}=\\{P^{\prime}_{1},P^{\prime}_{2}\\}$ of $G$ is obtained
by a single reconfiguration step in $G$ from $\mathcal{P}$, then
$P^{\prime}_{1}$ goes through all the red vertices and $P^{\prime}_{2}$ goes
through all the blue vertices.

###### Proof.

A single reconfiguration step changes one of $P_{1}$ and $P_{2}$, but not
both. We distinguish two cases.

First, assume that $P_{1}$ is reconfigured to another path $P^{\prime}_{1}$,
where in this case $P_{2}=P^{\prime}_{2}$. Since all the blue vertices are
occupied by $P_{2}$, the path $P^{\prime}_{1}$ cannot pass through any blue
vertex. The removal of the blue vertices from $G$ results in a graph with the
following property: each red vertex separates $s$ and $t$. Therefore,
$P^{\prime}_{1}$ must go through all the red vertices.

Second, assume that $P_{2}$ is reconfigured to another path $P^{\prime}_{2}$,
where in this case $P_{1}=P^{\prime}_{1}$. Since all the red vertices are
occupied by $P_{1}$, the path $P^{\prime}_{2}$ cannot pass through any red
vertex. The removal of the red vertices from $G$ yields a graph with the
following property: each blue vertex separates $s$ and $t$. Therefore,
$P^{\prime}_{2}$ must go through all the blue vertices. ∎

We now describe a canonical way of constructing an NCL configuration $\sigma$
of $H$ from an $s$-$t$ linkage $\mathcal{P}=\\{P_{1},P_{2}\\}$ of $G$ where
$P_{1}$ goes through all the red vertices and $P_{2}$ goes through all the
blue vertices.

Let $e=\\{u,v\\}$ be a weight-$2$ edge of $H$. The weight-$2$ edge gadget
$G_{e}$ of $e$ has vertices $r_{e,1}$ and $r_{e,2}$ that are visited by
$P_{1}$. The path $P_{1}$ should visit one of $w_{e,u}$ and $w_{e,v}$, but not
both. If $P_{1}$ visits $w_{e,u}$, then the edge $e$ is oriented toward $v$ in
$\sigma$. If $P_{1}$ visits $w_{e,v}$, then the edge $e$ is oriented toward
$u$ in $\sigma$.

Let $e=\\{u,v\\}$ be a weight-$1$ edge of $H$. The weight-$1$ edge gadget
$G_{e}$ of $e$ has vertices $b_{e,1}$ and $b_{e,2}$ that are visited by
$P_{2}$. The path $P_{2}$ should visit one of $w_{e,u}$ and $w_{e,v}$, but not
both. If $P_{2}$ visits $w_{e,u}$, then the edge $e$ is oriented toward $v$ in
$\sigma$. If $P_{2}$ visits $w_{e,v}$, then the edge $e$ is oriented toward
$u$ in $\sigma$.

This finishes the description of the construction of an NCL configuration. We
call the constructed NCL configuration the _canonical NCL configuration
obtained from $\\{P_{1},P_{2}\\}$_. We observe that if
$\mathcal{P}=\\{P_{1},P_{2}\\}$ is an $s$-$t$ linkage of $G$ that is created
from an NCL configuration $\sigma$, then $\sigma$ is the canonical NCL
configuration obtained from $\mathcal{P}$.

######  Claim 6.4.

Let $\mathcal{P}=\\{P_{1},P_{2}\\}$ be an $s$-$t$ linkage of $G$ such that
$P_{1}$ goes through all the red vertices and $P_{2}$ goes through all the
blue vertices. Then, the canonical NCL configuration $\sigma$ obtained from
$\mathcal{P}$ is indeed an NCL configuration of $H$.

###### Proof.

We check that $\sigma$ satisfies the weight requirement at every vertex $v$ of
$H$.

Assume that $v$ is an OR vertex which is incident to three weight-$2$ edges
$e$, $f$, and $g$. We observe that in the OR vertex gadget $G_{v}$, one of
$w_{e,v}$, $w_{f,v}$ and $w_{g,v}$ is not occupied by the red path $P_{1}$.
Suppose not. Then, out of four neighbors of the blue vertex $b_{v,1}$ in
$G_{v}$, the three vertices $w_{e,v}$, $w_{f,v}$ and $w_{g,v}$ are already
occupied. Therefore, the blue path $P_{2}$ cannot be vertex-disjoint with
$P_{1}$. This is a contradiction.

Therefore, in the canonical NCL configuration $\sigma$, one of the edges $e$,
$f$, and $g$ is oriented toward $v$. This means the incoming weight to $v$ is
at least two, and the weight requirement is satisfied at $v$.

Assume that $v$ is an AND vertex which is incident to one weight-$2$ edge $e$
and two weight-$1$ edges $f$ and $g$. We observe that in the AND vertex gadget
$G_{v}$, if $w_{e,v}$ is occupied by $P_{1}$, then $w_{f,v}$ and $w_{g,v}$ are
occupied by $P_{1}$, too. To this end, assume that $w_{e,v}$ is occupied by
$P_{1}$. Since $P_{1}$ and $P_{2}$ are vertex-disjoint, and $b_{v,1}$ and
$b_{v,2}$ are of degree $3$ that share $w_{e,v}$ as one of the common
neighbors, the blue path $P_{2}$ must go through the black vertex $k_{v}$.
Since the red vertices $r_{v,1}$ and $r_{v,2}$ are of degree $3$ that share
$k_{v}$ as a common neighbor, the red path $P_{1}$ must go through $w_{f,v}$
and $w_{g,v}$. This finishes the proof of the observation.

Therefore, if $w_{e,v}$ is not occupied by $P_{1}$, then in the canonical NCL
configuration $\sigma$ the weight-$2$ edge $e$ is oriented toward $v$, in
which case the weight requirement is satisfied at $v$. If not, by the
observation above, $w_{f,v}$ and $w_{g,v}$ are occupied by $P_{1}$. Since
$P_{1}$ and $P_{2}$ are vertex-disjoint, the blue path $P_{2}$ cannot go
through any of $w_{f,v}$ and $w_{g,v}$. This means that in the canonical NCL
configuration $\sigma$ the two weight-$1$ edges $f$ and $g$ are oriented
toward $v$, and in this case the weight requirement is satisfied at $v$. ∎

######  Claim 6.5.

Let $\mathcal{P}=\\{P_{1},P_{2}\\}$ be an $s$-$t$ linkage of $G$ such that
$P_{1}$ goes through all the red vertices and $P_{2}$ goes through all the
blue vertices, and let $\sigma$ be the canonical NCL configuration obtained
from $\mathcal{P}$. Let
$\mathcal{P}^{\prime}=\\{P^{\prime}_{1},P^{\prime}_{2}\\}$ be an $s$-$t$
linkage of $G$ obtained by a single reconfiguration step from $\mathcal{P}$
and $\sigma^{\prime}$ be the canonical NCL configuration obtained from
$\mathcal{P}^{\prime}$. Then, $\sigma^{\prime}$ can be obtained from $\sigma$
by at most $|V(H)|+|E(H)|$ flips in $H$.

###### Proof.

Suppose that we now want to transform $P_{1}$ to $P^{\prime}_{1}$ in such a
way that $P^{\prime}_{1}$ and $P_{2}$ are internally vertex-disjoint $s$-$t$
paths. By Claim 6.3, $P^{\prime}_{1}$ goes through all the red vertices.

Consider the red vertices $r_{e,1}$ and $r_{e,2}$ for an edge $e=\\{u,v\\}\in
E(H)$. Since $P_{1}$ passes through both of them, $P_{1}$ must pass through
exactly one of $w_{e,u}$ and $w_{e,v}$. The same observation applies to
$P^{\prime}_{1}$, too. If $P_{1}$ passes through $w_{e,u}$ and $P_{2}$ does
not pass through $w_{e,v}$, then we may reroute $P_{1}$ to pass through
$w_{e,v}$ instead of $w_{e,u}$ so as to obtain $P^{\prime}_{1}$.

Consider the red vertices $r_{v,1}$ and $r_{v,2}$ for an AND vertex $v\in
V(H)$ that is incident to one weight-$2$ edge $e$ and two weight-$1$ edges $f$
and $g$. Then, $P_{1}$ must pass through either $k_{v}$ or $w_{f,v},w_{g,v}$.
The same observation applies to $P^{\prime}_{1}$, too. If $P_{1}$ passes
through $k_{v}$ and $P_{2}$ passes through neither $w_{f,v}$ nor $w_{g,v}$,
then we may reroute $P_{1}$ to pass through $w_{f,v},w_{g,v}$ so as to obtain
$P^{\prime}_{1}$. If $P_{1}$ passes through $w_{f,v}$ and $w_{g,v}$, and
$P_{2}$ does not pass through $k_{v}$, then we may reroute $P_{1}$ to pass
through $k_{v}$ so as to obtain $P^{\prime}_{1}$.

Rerouting within an AND vertex gadget does not correspond to flips in an
orientation. On the other hand, rerouting within an edge gadget corresponds to
a flip in an orientation. Namely, rerouting $P_{1}$ to pass through $w_{e,v}$
instead of $w_{e,u}$ is mapped to a flip of the direction of $e$. If one
rerouting operation involves the reconnection within several edge gadgets,
then the operation is mapped to a set of flips of the corresponding edges.

We now argue that such a set of flips can be performed sequentially. To this
end, imagine that one rerouting operation of $P_{1}$ to $P^{\prime}_{1}$ is
decomposed into a number of reconfiguration steps each of which involves only
one edge gadget. Then, the sequence of those decomposed reconfiguration steps
together yields $P^{\prime}_{1}$ from $P_{1}$, and each step corresponds to a
single flip in $H$. Since two or more edge gadgets do not share a vertex in
$G$, such a decomposition is well-defined, and we are done.

Similarly, we may study the case where we transform $P_{2}$ to
$P^{\prime}_{2}$ in such a way that $P_{1}$ and $P^{\prime}_{2}$ are
internally vertex-disjoint $s$-$t$ paths. Rerouting within an AND vertex
gadget and an OR vertex gadget is similar, and does not correspond to a flip
in an orientation. On the other hand, rerouting within an edge gadget
corresponds to a flip of the corresponding edge.

When we are able to reroute a path within an edge gadget $G_{e}$ for an edge
$e=\\{u,v\\}\in E(H)$, the other path passes through neither $w_{e,u}$ nor
$w_{e,v}$. This means that, even without $e$, the total weights of incoming
arcs to $u$ and $v$ are at least two, respectively. Therefore, the flip
described above maintains the property that the resulting orientation is again
an NCL configuration.

There can be several gadgets that are involved in one reconfiguration step.
However, the number of such gadgets is at most $|V(H)|+|E(H)|$. Hence, that
reconfiguration step corresponds to at most $|V(H)|+|E(H)|$ flips in $H$. ∎

Let $\sigma^{\prime}$ be the canonical NCL configuration in Claim 6.5, and
$\mathcal{P}^{\prime\prime}=(P^{\prime\prime}_{1},P^{\prime\prime}_{2})$ be
the family of two internally vertex-disjoint $s$-$t$ paths of $G$ that is
created from $\sigma^{\prime}$. Note that $\mathcal{P}^{\prime\prime}$ does
not have to be identical to $\mathcal{P}^{\prime}$. However,
$\mathcal{P}^{\prime\prime}$ can be obtained from $\mathcal{P}^{\prime}$ by at
most $|V(H)|+|V^{\mathrm{a}}(H)|$ reconfiguration steps (recall that
$V^{\mathrm{a}}(H)$ is the set of AND vertices of $H$). This is because the
situations in edge gadgets are identical in $\mathcal{P}^{\prime}$ and
$\mathcal{P}^{\prime\prime}$, and reconfiguration steps would be needed only
around vertex gadgets.

As a summary, we have proved that the reduction is sound, complete, and
polynomially bounded. See Figure 18. We now complete the proof of Theorem 1.1.
Let $\sigma$ and $\tau$ be two NCL configurations. Then, define two $s$-$t$
linkages $\mathcal{P}=(P_{1},P_{2})$ and $\mathcal{Q}=(Q_{1},Q_{2})$ of $G$ as
they are created from $\sigma$ and $\tau$, respectively. Suppose that we may
transform $\sigma$ to $\tau$ by a sequence of flips in such a way that all the
intermediate orientations are NCL configurations. Then, the correspondence
above gives a sequence of reconfiguration steps to transform $\mathcal{P}$ to
$\mathcal{Q}$ so that all the intermediate sets of two $s$-$t$ paths are
internally vertex-disjoint. On the other hand, suppose that we may transform
$\mathcal{P}$ to $\mathcal{Q}$ by reconfiguration steps. Then, the
correspondence above gives a sequence of flips to transform $\sigma$ to $\tau$
so that all the intermediate orientations are NCL configurations. ∎

Figure 18: The correspondence between flips in NCL configurations and
reconfiguration steps for vertex-disjoint paths.

It is useful to note that the reduction can be modified so that $G$ in the
constructed instance of Disjoint $s$-$t$ Paths Reconfiguration has bounded
bandwidth if the AND/OR graph $H$ in a given instance of the NCL
reconfiguration has bounded bandwidth. A brief sketch is given in Appendix C.
This shows that Theorem 1.1 holds even for graphs of bounded bandwidth and
maximum degree four.

###  6.2 Planar Graphs of Bounded Bandwidth with Unbounded $k$

A similar reduction proves the $\mathsf{PSPACE}$-completeness for planar
graphs of bounded bandwidth when the number of paths is unbounded.

See 1.6

###### Proof.

We have already observed that the problem is in $\mathsf{PSPACE}$. To show the
$\mathsf{PSPACE}$-hardness, we now give a transformation of a given planar
AND/OR graph $H=(V(H),E(H))$ of bounded bandwidth to an undirected planar
graph $G=(V(G),E(G))$ of bounded bandwidth. Each edge $e=\\{u,v\\}\in E(H)$ of
$H$ is mapped to the following _edge gadget_ $G_{e}$ (see Figure 19):

$\displaystyle V(G_{e})$ $\displaystyle=\\{w_{e,u},w_{e,v},s_{e},t_{e}\\},$
$\displaystyle E(G_{e})$
$\displaystyle=\\{\\{w_{e,u},s_{e}\\},\\{w_{e,u},t_{e}\\},\\{w_{e,v},s_{e}\\},\\{w_{e,v},t_{e}\\}\\}.$

Figure 19: An edge gadget.

Let $v\in V(H)$ be an OR vertex, and $e,f,g\in E(H)$ be three weight-$2$ edges
incident to $v$. Then, $v$ is mapped to the following _OR vertex gadget_
$G_{v}$ (see Figure 20):

$\displaystyle V(G_{v})$
$\displaystyle=\\{w_{e,v},w_{f,v},w_{g,v},a_{v},b_{v},c_{v},d_{v},s_{v},t_{v},s^{\mathrm{o}}_{v},t^{\mathrm{o}}_{v}\\},$
$\displaystyle E(G_{v})$
$\displaystyle=\\{\\{w_{e,v},a_{v}\\},\\{w_{e,v},b_{v}\\},\\{w_{e,v},t_{v}\\},\\{w_{f,v},a_{v}\\},\\{w_{f,v},s_{v}\\},$
$\displaystyle\qquad\\{w_{g,v},b_{v}\\},\\{w_{g,v},s_{v}\\},\\{a_{v},c_{v}\\},\\{a_{v},d_{v}\\},\\{b_{v},c_{v}\\},\\{b_{v},d_{v}\\},$
$\displaystyle\qquad\\{c_{v},s_{v}\\},\\{c_{v},s^{\mathrm{o}}_{v}\\},\\{c_{v},t^{\mathrm{o}}_{v}\\},\\{d_{v},t_{v}\\},\\{d_{v},s^{\mathrm{o}}_{v}\\},\\{d_{v},t^{\mathrm{o}}_{v}\\}\\}.$

Note that the vertices with the same label are identified.

Figure 20: An OR vertex gadget.

An AND vertex $v\in V(H)$ that is incident to one weight-$2$ edge $e$ and two
weight-$1$ edges $f,g$ is mapped to the following _AND vertex gadget_ $G_{v}$
(see Figure 21):

$\displaystyle V(G_{v})$
$\displaystyle=\\{w_{e,v},w_{f,v},w_{g,v},s_{v},t_{v}\\},$ $\displaystyle
E(G_{v})$
$\displaystyle=\\{\\{w_{e,v},s_{v}\\},\\{w_{e,v},t_{v}\\},\\{w_{f,v},s_{v}\\},\\{w_{g,v},t_{v}\\},\\{w_{f,v},w_{g,v}\\}\\}.$

Figure 21: An AND vertex gadget.

Define

$\displaystyle V(G)$ $\displaystyle=\bigcup_{v\in
V(H)}V(G_{v})\cup\bigcup_{e\in E(H)}V(G_{e}),$ $\displaystyle E(G)$
$\displaystyle=\bigcup_{v\in V(H)}E(G_{v})\cup\bigcup_{e\in E(H)}E(G_{e}).$

This completes the construction of $G$. Figure 22 may help the reader
understand.

We note that if $H$ is planar and of bounded bandwidth, then so is $G$. To see
that $G$ is planar, observe that each gadget can be drawn on the plane without
edge crossing in such a way that the vertices shared with other gadgets are
placed on its outer face. Then, a plane drawing of $G$ can be obtained from a
plane drawing of $H$ by replacing each vertex and edge of $H$ by the
corresponding gadget. To see that the bandwidth of $G$ is bounded, observe
that each gadget is of constant size. Therefore, by giving a slack of constant
width $c$ for each vertex of $H$, we may obtain an injective mapping of the
vertices of $G$ to $\mathbb{Z}$ whose bandwidth is at most $c$ times the
bandwidth of $H$.333The constant $c$ can be chosen as $16$, but this
particular choice is not relevant.

Figure 22: Mapping an NCL configuration to a linkage. In the NCL
configuration, the vertex label A stands for an AND vertex, and the vertex
label O stands for an OR vertex.

In the constructed graph $G$, we consider the following pairs of vertices:

$\\{(s_{e},t_{e})\mid e\in E(H)\\}\cup\\{(s_{v},t_{v})\mid v\in
V(H)\\}\cup\\{(s^{\mathrm{o}}_{v},t^{\mathrm{o}}_{v})\mid v\in
V^{\mathrm{o}}(H)\\},$

where $V^{\mathrm{o}}(H)$ denotes the set of OR vertices in $H$. The number of
pairs is $|E(H)|+|V(H)|+|V^{\mathrm{o}}(H)|$.

We now describe the way how an NCL configuration $\sigma$ of $H$ translates to
a linkage

$\mathcal{P}=\\{P_{e}\mid e\in E(H)\\}\cup\\{P_{v}\mid v\in
V(H)\\}\cup\\{P^{\mathrm{o}}_{v}\mid v\in V^{\mathrm{o}}(H)\\}$

of $G$, where $P_{e}$ joins $s_{e}$ and $t_{e}$ for every $e\in E(H)$, $P_{v}$
joins $s_{v}$ and $t_{v}$ for every $v\in V(H)$, and $P^{\mathrm{o}}_{v}$
joins $s^{\mathrm{o}}_{v}$ and $t^{\mathrm{o}}_{v}$ for every $v\in
V^{\mathrm{o}}(H)$. For convenience, $P_{e}$ is called a _red_ path for every
$e\in E(H)$, and $P^{\mathrm{o}}_{v}$ is called a _blue_ path for every $v\in
V^{\mathrm{o}}(H)$. Similarly, for every $v\in V(H)$, $P_{v}$ is called a
_green_ path if $v$ is an AND vertex, and a _purple_ path if $v$ is an OR
vertex.

First, we specify the red paths $P_{e}$ for all $e=\\{u,v\\}\in E(H)$. The
path $P_{e}$ connects $s_{e}$ and $t_{e}$ and its length is two. Therefore,
there will be a unique middle vertex. If the edge $e$ is oriented from $u$ to
$v$ in the NCL configuration $\sigma$, then the path $P_{e}$ visits $w_{e,u}$
as its middle vertex. If $e$ is oriented from $v$ to $u$ in $\sigma$, then
$P_{e}$ visits $w_{e,v}$ as its middle vertex. This finishes the specification
of the red paths $P_{e}$.

Next, we specify the green paths $P_{v}$ that connect $s_{v}$ and $t_{v}$ for
all AND vertices $v\in V(H)$. Recall that $v$ is incident to a weight-$2$ edge
$e$ and two weight-$1$ edges $f,g$. If $e$ is oriented toward $v$, then
$P_{v}$ passes through $w_{e,v}$ and its length is two. Otherwise, $f$ and $g$
must be oriented toward $v$. Then, $P_{v}$ passes through $w_{f,v}$ and
$w_{g,v}$ and its length is three. This finishes the specification of the
green paths $P_{v}$.

Finally, we specify the purple paths $P_{v}$ that connect $s_{v}$ and $t_{v}$
and the blue paths $P^{\mathrm{o}}_{v}$ that connect $s^{\mathrm{o}}_{v}$ and
$t^{\mathrm{o}}_{v}$ for all OR vertices $v\in V^{\mathrm{o}}(H)$. Recall that
$v$ is incident to three weight-$2$ edges $e,f,g$. We have three cases, which
are not exclusive. If $e$ is oriented toward $v$, then the purple path $P_{v}$
passes through $c_{v},a_{v},w_{e,v}$ (or $c_{v},b_{v},w_{e,v}$), and the blue
path $P^{\mathrm{o}}_{v}$ passes through $d_{v}$. If $f$ is oriented toward
$v$, then $P_{v}$ passes through $w_{f,v}$, $a_{v}$, $d_{v}$, and
$P^{\mathrm{o}}_{v}$ passes through $c_{v}$. If $g$ is oriented toward $v$,
then $P_{v}$ passes through $w_{g,v}$, $b_{v}$, $d_{v}$, and
$P^{\mathrm{o}}_{v}$ passes through $c_{v}$. This finishes the specification
of the purple paths $P_{v}$ and the blue paths $P^{\mathrm{o}}_{v}$. Note that
the lengths of purple paths are always four and the lengths of blue paths are
always two.

This finishes the construction of $\mathcal{P}$. With this construction, we
say that the linkage $\mathcal{P}$ _is created from_ the NCL configuration
$\sigma$.

######  Claim 6.6.

The constructed paths are vertex-disjoint.

###### Proof.

Each path visits vertices in the corresponding gadget only, and within each OR
gadget the two constructed paths do not share vertices by the construction
rule. Therefore, it suffices to examine the situation at identified vertices
between an edge gadget and an AND/OR vertex gadget.

Let $v$ be an OR vertex that are incident to three weight-$2$ edges $e,f,g$.
Assume that the corresponding OR vertex gadget is constructed as above.

Suppose that the vertex $w_{e,v}$ is shared by two of the constructed paths.
One of those paths is the red path $P_{e}$ that connects $s_{e}$ and $t_{e}$;
the other path is the purple path $P_{v}$ that connects $s_{v}$ and $t_{v}$.
Since $P_{e}$ passes through $w_{e,v}$, the edge $e$ is not oriented toward
$v$. On the other hand, since $P_{v}$ passes through $w_{e,v}$, the edge $e$
is oriented toward $v$. This is a contradiction, and thus $w_{e,v}$ is not
shared by two paths.

Suppose that the vertex $w_{f,v}$ is shared by two of the constructed paths.
One of those paths is the red path $P_{f}$, which means that the edge $f$ is
not oriented toward $v$. Then, the other path is the purple path $P_{v}$. By
the construction, it holds that $f$ is oriented toward $v$. This is a
contradiction. The same conclusion holds when $w_{g,v}$ is shared by two
paths.

Let $v$ be an AND vertex that are incident to one weight-$2$ edge $e$ and two
weight-$1$ edges $f,g$. Assume that the corresponding AND vertex gadget is
constructed as above.

Suppose that the vertex $w_{e,v}$ is shared by two of the constructed paths.
One of those paths is the red path $P_{e}$ that connects $s_{e}$ and $t_{e}$;
the other path is the green path $P_{v}$ that connects $s_{v}$ and $t_{v}$.
Since $P_{e}$ passes through $w_{e,v}$, the edge $e$ is not oriented toward
$v$. On the other hand, since $P_{v}$ passes through $w_{e,v}$, the edge $e$
is oriented toward $v$. This is a contradiction, and thus $w_{e,v}$ is not
shared by two paths.

Suppose that the vertex $w_{f,v}$ is shared by two of the constructed paths.
One of those paths is the red path $P_{f}$ that connects $s_{f}$ and $t_{f}$,
which means that the edge $f$ is not oriented toward $v$. The other path is
the green path $P_{v}$ that connects $s_{v}$ and $t_{v}$, which means that $f$
is oriented toward $v$. This is a contradiction. The same conclusion holds
when $w_{g,v}$ is shared by two paths.

In summary, there is no vertex in the instance $G$ that is shared by two or
more constructed paths. ∎

We now study how a flip in an orientation maps to a sequence of
reconfiguration steps of paths.

######  Claim 6.7.

Let $\mathcal{P}$ be a linkage of $G$ that is created from an NCL
configuration $\sigma$. If an NCL configuration $\sigma^{\prime}$ is obtained
from $\sigma$ by an flip of a single edge, then a linkage
$\mathcal{P}^{\prime}$ of $G$ that is created from $\sigma^{\prime}$ can be
obtained from $\mathcal{P}$ by at most a constant number of reconfiguration
steps in $G$.

###### Proof.

Assume that we are given an NCL configuration $\sigma$ of $H$. Let

$\mathcal{P}=\\{P_{e}\mid e\in E(H)\\}\cup\\{P_{v}\mid v\in
V(H)\\}\cup\\{P^{\mathrm{o}}_{v}\mid v\in V^{\mathrm{o}}(H)\\}$

be a linkage of $G$ that is created from $\sigma$. By the construction, each
of the colored paths passes through all the vertices of the corresponding
color.

As the first case, consider a flip of a weight-$1$ edge $f$ that connects two
AND vertices $u,v$ from $(u,v)$ to $(v,u)$. Then, the red path $P_{f}$ passes
through $s_{f},w_{f,u},t_{f}$ of the weight-$1$ edge gadget in this order. The
path $P^{\prime}_{f}$ is obtained by replacing it with $s_{f},w_{f,v},t_{f}$.

This is possible only if $w_{f,v}$ is not passes through by any other paths;
we now observe this is indeed the case. Suppose that $w_{f,v}$ is passed
through by another path. Then, such a path should be a green path $P_{v}$ in
the AND vertex gadget $G_{v}$. When $P_{v}$ passes through $w_{f,v}$, a unique
weight-$2$ edge $e$ incident to $v$ is not oriented toward $v$ in $\sigma$ by
the construction. Therefore, after flipping to $(v,u)$ the total sum of the
incoming edges to $v$ will be $1$. This is a contradiction to the property of
an NCL configuration.

As the second case, consider a flip of a weight-$2$ edge $e$ that connects a
vertex $u$ and an AND vertex $v$ from $(u,v)$ to $(v,u)$. Then, the red path
$P_{e}$ passes through $s_{e},w_{e,u},t_{e}$ of the weight-$2$ edge gadget
$G_{e}$ in this order. The path $P^{\prime}_{e}$ is obtained by replacing it
with $s_{e},w_{e,v},t_{e}$.

This is possible only if $w_{e,v}$ is not passes through by an other paths.
However, since $e$ is oriented toward $v$, a green path $P_{v}$ in the AND
vertex gadget $G_{v}$ passes through $w_{e,v}$. Thus, in order to make
$w_{e,v}$ vacant, we apply the following operations before the above
transformation. Since $e$ can be flipped, after the flip the total sum of the
incoming edges to $v$ should be at least two, which means that the other two
weight-$1$ edges $f$, $g$ that are incident to $v$ should be directed toward
$v$. Therefore, $w_{v,f}$ and $w_{v,g}$ are not occupied by any other paths in
$\mathcal{P}$. This implies that by rerouting the green path $P_{v}$ to pass
through $w_{v,f},w_{v,g}$ before rerouting $P_{e}$ to $P^{\prime}_{e}$ we
obtain the linkage that corresponds to $\sigma^{\prime}$.

As the third but final case, consider a flip of a weight-$2$ edge $e$ that
connects a vertex $u$ and an OR vertex $v$ from $(u,v)$ to $(v,u)$. Then, the
red path $P_{e}$ passes through $s_{e},w_{e,u},t_{e}$ of the edge gadget
$G_{e}$ in this order. The $P^{\prime}_{e}$ is obtained by replacing it with
$s_{e},w_{e,v},t_{e}$.

This is possible only if $w_{e,v}$ is not passed through by any other paths.
If this is the case, there is no problem. However, in some cases, $w_{e,v}$ is
indeed passed through by another path. Then, such a path should be a purple
path $P_{v}$ in the OR vertex gadget $G_{v}$. By construction, the edge $e$ is
oriented toward $v$ in $\sigma$. Since $e$ can be flipped, after the flip the
total sum of the incoming edges to $v$ should be at least two, which means
that one of the other two weight-$2$ edges $f$, $g$ that are incident to $v$
should be directed toward $v$. Therefore, $w_{v,f}$ or $w_{v,g}$ is not
occupied by any other paths in $\mathcal{P}$. This implies that by rerouting
the purple path $P_{v}$ to pass through $w_{v,f}$ or $w_{v,g}$ before
rerouting $P_{e}$ to $P^{\prime}_{e}$, possibly with two more reconfiguration
steps involving the blue path $P^{\mathrm{o}}_{v}$, we obtain the linkage that
corresponds to $\sigma^{\prime}$.

In the second and third cases above, if $u$ is an AND vertex, then we reroute
a green path $P_{u}$ in the AND vertex gadget $G_{u}$ to pass through
$w_{e,u}$. Then, we obtain a linkage $\mathcal{P}^{\prime}$ of $G$ that is
created from $\sigma^{\prime}$. ∎

To argue the reverse direction of correspondence, we describe a canonical way
of constructing an NCL configuration $\sigma$ of $H$ from a linkage
$\mathcal{P}$ of $G$.

Let $e=\\{u,v\\}$ be an edge of $H$. We note that a path connecting $s_{e}$
and $t_{e}$ cannot go through both of $w_{e,u}$ and $w_{e,v}$ due to the
vertex-disjointness of the paths in $\mathcal{P}$. If $P_{e}$ goes through
$w_{e,u}$, then the edge $e$ is oriented toward $v$ in $\sigma$. If $P_{e}$
goes through $w_{e,v}$, then the edge $e$ is oriented toward $u$ in $\sigma$.
We call the obtained orientation $\sigma$ the _canonical NCL configuration
obtained from $\mathcal{P}$_.

######  Claim 6.8.

Let $\mathcal{P}$ be a linkage of $G$. Then, the canonical NCL configuration
$\sigma$ obtained from $\mathcal{P}$ is indeed an NCL configuration of $H$.

###### Proof.

We check that $\sigma$ satisfies the weight requirement at every vertex $v$ of
$H$.

Let $v$ be an OR vertex of $H$ that is incident to three weight-$2$ edges $e$,
$f$ and $g$. The corresponding OR vertex gadget is given as in Figure 20.
Since the blue path in the gadget $G_{v}$ contains a vertex $c_{v}$ or
$d_{v}$, the purple path in $G_{v}$ contains at least one of $w_{e,v}$,
$w_{f,v}$ and $w_{g,v}$. This shows that one of $w_{e,v}$, $w_{f,v}$ and
$w_{g,v}$ is not occupied by any red paths. Therefore, in the canonical NCL
configuration $\sigma$, one of the edges $e$, $f$ and $g$ is oriented toward
$v$. This means that the weight requirement is satisfied at $v$.

Next, let $v$ be an AND vertex of $H$ that is incident to one weight-$2$ edge
$e$ and two weight-$1$ edges $f$ and $g$. The green path between $s_{v}$ to
$t_{v}$ either goes through $w_{e,v}$ or $w_{f,v},w_{g,v}$. If it goes through
$w_{e,v}$, then the red path $P_{e}$ does not go through $w_{e,v}$ due to
vertex-disjointness. In this case, the weight-$2$ edge $e$ is oriented toward
$v$ in $\sigma$. If the green path goes through $w_{f,v}$ and $w_{g,v}$, then
the red paths $P_{f}$ and $P_{g}$ do not go through $w_{f,v}$ and $w_{g,v}$,
respectively. In this case, the two weight-$1$ edges $f$ and $g$ are oriented
toward $v$ in $\sigma$. Hence, in both cases, the weight requirement is
satisfied at $v$. ∎

######  Claim 6.9.

Let $\mathcal{P}$ be a linkage of $G$ and $\sigma$ be the canonical NCL
configuration obtained from $\mathcal{P}$. Let a linkage
$\mathcal{P}^{\prime}$ be obtained by a single reconfiguration step from
$\mathcal{P}$ and $\sigma^{\prime}$ be the canonical NCL configuration
obtained from $\mathcal{P}^{\prime}$. Then, $\sigma^{\prime}$ can be obtained
from $\sigma$ by at most one flip in $H$.

###### Proof.

We distinguish cases by colors of paths that are reconfigured by one step.

First, consider a case where $\mathcal{P}$ and $\mathcal{P}^{\prime}$ differ
by one red path associated with an edge gadget $G_{e}$. Assume that $P_{e}$ is
reconfigured to $P^{\prime}_{e}$. Without loss of generality, assume that
$P_{e}$ passes through $s_{e},w_{e,u},t_{e}$, and $P^{\prime}_{e}$ passes
through $s_{e},w_{e,v},t_{e}$ in this order. Then, to obtain $\sigma^{\prime}$
from $\sigma$ we just need to flip the direction of the edge $e$.

Next, consider a case where $\mathcal{P}$ and $\mathcal{P}^{\prime}$ differ by
one path that is not a red path. Then, the canonical NCL configuration
$\sigma^{\prime}$ obtained from $\mathcal{P}^{\prime}$ is identical to
$\sigma$. Therefore, we need no flip to construct $\sigma^{\prime}$. ∎

Let $\sigma^{\prime}$ be the canonical NCL configuration in Claim 6.9, and
$\mathcal{P}^{\prime\prime}$ be the linkage created from $\sigma^{\prime}$.
Note that $\mathcal{P}^{\prime\prime}$ does not have to be identical to
$\mathcal{P}^{\prime}$. However, $\mathcal{P}^{\prime\prime}$ can be obtained
from $\mathcal{P}^{\prime}$ by $O(|V(H)|)$ reconfiguration steps. This is
because the situations in edge gadgets are identical in $\mathcal{P}^{\prime}$
and $\mathcal{P}^{\prime\prime}$, and reconfiguration steps would be needed
only around vertex gadgets.

As a summary, we have proved that the reduction is sound, complete, and
polynomially bounded. See Figure 23. We now complete the proof of Theorem 1.6.
Let $\sigma$ and $\tau$ be two NCL configurations. Then, define two linkages
$\mathcal{P}$ and $\mathcal{Q}$ as they correspond to $\sigma$ and $\tau$,
respectively. Suppose that we may transform $\sigma$ to $\tau$ by a sequence
of flips in such a way that all the intermediate orientations are NCL
configurations. Then, the correspondence above gives a sequence of
reconfiguration steps to transform $\mathcal{P}$ to $\mathcal{Q}$ so that all
the intermediate families of paths are vertex-disjoint. On the other hand,
suppose that we may transform $\mathcal{P}$ to $\mathcal{Q}$ by
reconfiguration steps. Then, the correspondence above gives a sequence of
flips to transform $\sigma$ to $\tau$ so that all the intermediate
orientations are NCL configurations. ∎

Figure 23: The correspondence between flips in NCL configurations and
reconfiguration steps for vertex-disjoint paths.

##  7 Concluding Remarks

We leave several open problems for future research. We proved that Disjoint
Paths Reconfiguration can be solved in polynomial time when the problem is
restricted to the two-face instances. On the other hand, we do not know
whether Disjoint Paths Reconfiguration in planar graphs can be solved in
polynomial time for fixed $k$, and even when $k=2$, if we drop the requirement
that inputs are two-face instances.

We did not try to minimize the number of reconfiguration steps when a
reconfiguration sequence exists. It is an open problem whether a shortest
reconfiguration sequence can be found in polynomial time for Disjoint Paths
Reconfiguration restricted to planar two-face instances.

A natural extension of our studies is to consider a higher-genus surface. As a
preliminary result, in Appendix A, we give a proof (sketch) to show that when
the number $k$ of curves is two, the reconfiguration is _always_ possible for
any connected orientable closed surface $\Sigma_{g}$ of genus $g\geq 1$. Note
that this result does not refer to graphs embedded on $\Sigma_{g}$, but only
refers to the case when curves can pass through any points on the surface. It
is not clear what we can say for Disjoint Paths Reconfiguration for graphs
embedded on $\Sigma_{g}$, $g\geq 1$.

## References

  * [1] I. Adler, S. G. Kolliopoulos, P. K. Krause, D. Lokshtanov, S. Saurabh, and D. M. Thilikos.  Irrelevant vertices for the planar disjoint paths problem.  Journal of Combinatorial Theory, Series B, 122:815–843, 2017.  doi:10.1016/j.jctb.2016.10.001.
  * [2] S. A. Amiri, S. Dudycz, M. Parham, S. Schmid, and S. Wiederrecht.  On polynomial-time congestion-free software-defined network updates.  In 2019 IFIP Networking Conference, Networking 2019, Warsaw, Poland, May 20-22, 2019, pages 1–9. IEEE, 2019.  doi:10.23919/IFIPNetworking.2019.8816833.
  * [3] S. A. Amiri, S. Dudycz, S. Schmid, and S. Wiederrecht.  Congestion-free rerouting of flows on DAGs.  In I. Chatzigiannakis, C. Kaklamanis, D. Marx, and D. Sannella, editors, 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, volume 107 of LIPIcs, pages 143:1–143:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.  doi:10.4230/LIPIcs.ICALP.2018.143.
  * [4] J. Asplund, K. D. Edoh, R. Haas, Y. Hristova, B. Novick, and B. Werner.  Reconfiguration graphs of shortest paths.  Discret. Math., 341(10):2938–2948, 2018.  doi:10.1016/j.disc.2018.07.007.
  * [5] J. Asplund and B. Werner.  Classification of reconfiguration graphs of shortest path graphs with no induced 4-cycles.  Discret. Math., 343(1):111640, 2020.  doi:10.1016/j.disc.2019.111640.
  * [6] P. S. Bonsma.  The complexity of rerouting shortest paths.  Theor. Comput. Sci., 510:1–12, 2013.  doi:10.1016/j.tcs.2013.09.012.
  * [7] P. S. Bonsma.  Rerouting shortest paths in planar graphs.  Discret. Appl. Math., 231:95–112, 2017.  doi:10.1016/j.dam.2016.05.024.
  * [8] G. Borradaile, A. Nayyeri, and F. Zafarani.  Towards single face shortest vertex-disjoint paths in undirected planar graphs.  In Proceedings of 23rd Annual European Symposium on Algorithms (ESA), volume 9294 of Lecture Notes in Computer Science, pages 227–238, 2015.  doi:10.1007/978-3-662-48350-3_20.
  * [9] J. Chuzhoy and D. H. K. Kim.  On approximating node-disjoint paths in grids.  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM), volume 40 of LIPIcs, pages 187–211, 2015.  doi:10.4230/LIPIcs.APPROX-RANDOM.2015.187.
  * [10] J. Chuzhoy, D. H. K. Kim, and S. Li.  Improved approximation for node-disjoint paths in planar graphs.  In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 556–569, 2016.  doi:10.1145/2897518.2897538.
  * [11] J. Chuzhoy, D. H. K. Kim, and R. Nimavat.  New hardness results for routing on disjoint paths.  SIAM J. Comput., 51(2):17–189, 2022.  doi:10.1137/17M1146580.
  * [12] J. Chvatalova and J. Opatrny.  The bandwidth problem and operations on graphs.  Discret. Math., 61(2-3):141–150, 1986.  doi:10.1016/0012-365X(86)90086-5.
  * [13] É. Colin de Verdière and A. Schrijver.  Shortest vertex-disjoint two-face paths in planar graphs.  ACM Transactions on Algorithms, 7(2):1–12, 2011.  doi:10.1145/1921659.1921665.
  * [14] M. Cygan, D. Marx, M. Pilipczuk, and M. Pilipczuk.  The planar directed $k$-vertex-disjoint paths problem is fixed-parameter tractable.  In 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2013), pages 197–206, 2013.  doi:10.1109/FOCS.2013.29.
  * [15] S. Datta, S. Iyer, R. Kulkarni, and A. Mukherjee.  Shortest $k$-disjoint paths via determinants.  In 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018), volume 122, pages 19:1–19:21, 2018.  doi:10.4230/LIPIcs.FSTTCS.2018.19.
  * [16] J. Enoch, K. Fox, D. Mesica, and S. Mozes.  A faster algorithm for maximum flow in directed planar graphs with vertex capacities.  In H. Ahn and K. Sadakane, editors, 32nd International Symposium on Algorithms and Computation, ISAAC 2021, December 6-8, 2021, Fukuoka, Japan, volume 212 of LIPIcs, pages 72:1–72:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.  doi:10.4230/LIPIcs.ISAAC.2021.72.
  * [17] J. Erickson and A. Nayyeri.  Shortest non-crossing walks in the plane.  In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 297–308, 2011.  doi:10.1137/1.9781611973082.25.
  * [18] B. Farb and D. Margalit.  A primer on mapping class groups, volume 49 of Princeton Mathematical Series.  Princeton University Press, Princeton, NJ, 2012.
  * [19] L. Ford and D. Fulkerson.  Maximal flow through a network.  Canadian Journal of Mathematics, 8:399–404, 1956.  doi:10.4153/CJM-1956-045-5.
  * [20] S. Fortune, J. Hopcroft, and J. Wyllie.  The directed subgraph homeomorphism problem.  Theoretical Computer Science, 10(2):111–121, 1980.  doi:10.1016/0304-3975(80)90009-2.
  * [21] A. Frank.  Packing paths, circuits, and cuts — a survey.  In Paths, flows, and VLSI-layout, pages 47–100. Springer, 1990\.
  * [22] K. Gajjar, A. V. Jha, M. Kumar, and A. Lahiri.  Reconfiguring shortest paths in graphs.  CoRR, abs/2112.07499, 2021.  arXiv:2112.07499, doi:10.48550/arXiv.2112.07499.
  * [23] R. A. Hearn and E. D. Demaine.  PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation.  Theor. Comput. Sci., 343(1-2):72–96, 2005.  doi:10.1016/j.tcs.2005.05.008.
  * [24] 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.  Theor. Comput. Sci., 412(12-14):1054–1065, 2011.  doi:10.1016/j.tcs.2010.12.005.
  * [25] T. Ito, N. Kakimura, N. Kamiyama, Y. Kobayashi, and Y. Okamoto.  Reconfiguration of maximum-weight $b$-matchings in a graph.  J. Comb. Optim., 37(2):454–464, 2019.  doi:10.1007/s10878-018-0289-3.
  * [26] M. Kaminski, P. Medvedev, and M. Milanic.  Shortest paths between shortest paths.  Theor. Comput. Sci., 412(39):5205–5210, 2011.  doi:10.1016/j.tcs.2011.05.021.
  * [27] H. Kaplan and Y. Nussbaum.  Maximum flow in directed planar graphs with vertex capacities.  Algorithmica, 61(1):174–189, 2011.  doi:10.1007/s00453-010-9436-7.
  * [28] R. M. Karp.  On the computational complexity of combinatorial problems.  Networks, 5(1):45–68, 1975.  doi:10.1002/net.1975.5.1.45.
  * [29] S. Khuller and J. Naor.  Flow in planar graphs with vertex capacities.  Algorithmica, 11(3):200–225, 1994.  doi:10.1007/BF01240733.
  * [30] Y. Kobayashi and K. Otsuki.  Max-flow min-cut theorem and faster algorithms in a circular disk failure model.  In 2014 IEEE Conference on Computer Communications (INFOCOM), pages 1635–1643, 2014.  doi:10.1109/INFOCOM.2014.6848100.
  * [31] Y. Kobayashi and C. Sommer.  On shortest disjoint paths in planar graphs.  Discrete Optimization, 7(4):234–245, 2010.  doi:10.1016/j.disopt.2010.05.002.
  * [32] S. G. Kolliopoulos and C. Stein.  Approximating disjoint-path problems using packing integer programs.  Math. Program., 99(1):63–87, 2004.  doi:10.1007/s10107-002-0370-6.
  * [33] M. R. Kramer.  The complexity of wire-routing and finding minimum area layouts for arbitrary VLSI circuits.  Advances in Computing Research, 2:129–146, 1984.
  * [34] J. F. Lynch.  The equivalence of theorem proving and the interconnection problem.  ACM SIGDA Newsletter, 5(3):31–36, 1975.  doi:10.1145/1061425.1061430.
  * [35] C. Mcdiarmid, B. Reed, A. Schrijver, and B. Shepherd.  Induced circuits in planar graphs.  Journal of Combinatorial Theory, Series B, 60(2):169–176, 1994\.  doi:10.1006/jctb.1994.1011.
  * [36] C. McDiarmid, B. A. Reed, A. Schrijver, and B. Shepherd.  Non-interfering network flows.  In Proceedings of the Third Scandinavian Workshop on Algorithm Theory (SWAT), page 245–257, 1992.  doi:10.1007/3-540-55706-7_21.
  * [37] K. Menger.  Zur allgemeinen Kurventheorie.  Fundamenta Mathematicae, 10:96–115, 1927.
  * [38] N. Nishimura.  Introduction to reconfiguration.  Algorithms, 11(4):52, 2018.  doi:10.3390/a11040052.
  * [39] H. Okamura.  Multicommodity flows in graphs.  Discrete Applied Mathematics, 6(1):55–62, 1983.  doi:10.1016/0166-218X(83)90100-2.
  * [40] H. Okamura and P. D. Seymour.  Multicommodity flows in planar graphs.  Journal of Combinatorial Theory, Series B, 31(1):75–81, 1981.  doi:10.1016/S0095-8956(81)80012-3.
  * [41] K. Otsuki, Y. Kobayashi, and K. Murota.  Improved max-flow min-cut algorithms in a circular disk failure model with application to a road network.  Eur. J. Oper. Res., 248(2):396–403, 2016.  doi:10.1016/j.ejor.2015.07.035.
  * [42] E. Papadopoulou.  $k$-pairs non-crossing shortest paths in a simple polygon.  Int. J. Comput. Geom. Appl., 9(6):533–552, 1999.  doi:10.1142/S0218195999000315.
  * [43] B. Reed.  Rooted routing in the plane.  Discrete Applied Mathematics, 57:213–227, 1995.  doi:10.1016/0166-218X(94)00104-L.
  * [44] B. Reed, N. Robertson, A. Schrijver, and P. Seymour.  Finding disjoint trees in planar graphs in linear time.  In Contemporary Mathematics 147, pages 295–301. American Mathematical Society, 1993.  doi:10.1090/conm/147/01180.
  * [45] N. Robertson and P. D. Seymour.  Graph minors. VI. Disjoint paths across a disc.  Journal of Combinatorial Theory, Series B, 41(1):115–138, 1986\.  doi:10.1016/0095-8956(86)90031-6.
  * [46] N. Robertson and P. D. Seymour.  Graph minors. VII. Disjoint paths on a surface.  Journal of Combinatorial Theory, Series B, 45(2):212–254, 1988\.  doi:10.1016/0095-8956(88)90070-6.
  * [47] N. Robertson and P. D. Seymour.  Graph minors. XIII. The disjoint paths problem.  Journal of combinatorial theory, Series B, 63(1):65–110, 1995.  doi:10.1006/jctb.1995.1006.
  * [48] W. J. Savitch.  Relationships between nondeterministic and deterministic tape complexities.  J. Comput. Syst. Sci., 4(2):177–192, 1970.  doi:10.1016/S0022-0000(70)80006-X.
  * [49] A. Schrijver.  Finding $k$ disjoint paths in a directed planar graph.  SIAM Journal on Computing, 23(4):780–788, 1994.  doi:10.1137/S0097539792224061.
  * [50] P. D. Seymour.  Disjoint paths in graphs.  Discrete Mathematics, 29:293–309, 1980.  doi:10.1016/0012-365X(80)90158-2.
  * [51] Y. Shiloach.  A polynomial solution to the undirected two paths problem.  Journal of the ACM, 27(3):445–456, 1980.  doi:10.1145/322203.322207.
  * [52] A. Srinivas and E. Modiano.  Finding minimum energy disjoint paths in wireless ad-hoc networks.  Wireless Networks, 11(4):401–417, 2005.  doi:10.1007/s11276-005-1765-0.
  * [53] H. Suzuki, T. Akama, and T. Nishizeki.  Algorithms for finding internally disjoint paths in a planar graph.  Electronics and Communications in Japan (Part III: Fundamental Electronic Science), 72(10):55–67, 1989.  doi:10.1002/ecjc.4430721006.
  * [54] H. Suzuki, T. Akama, and T. Nishizeki.  Finding Steiner forests in planar graphs.  In Proceedings of the first annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 444–453, 1990.
  * [55] J. Takahashi, H. Suzuki, and T. Nishizeki.  Algorithms for finding non-crossing paths with minimum total length in plane graphs.  In Proceedings of Third International Symposium on Algorithms and Computation (ISAAC), volume 650 of Lecture Notes in Computer Science, pages 400–409, 1992.  doi:10.1007/3-540-56279-6_92.
  * [56] C. Thomassen.  2-linked graphs.  European Journal of Combinatorics, 1:371–378, 1980.  doi:10.1016/S0195-6698(80)80039-4.
  * [57] J. van den Heuvel.  The complexity of change.  In S. R. Blackburn, S. Gerke, and M. Wildon, editors, Surveys in Combinatorics 2013, volume 409 of London Mathematical Society Lecture Note Series, pages 127–160. Cambridge University Press, 2013.  doi:10.1017/CBO9781139506748.005.
  * [58] T. C. van der Zanden.  Parameterized complexity of graph constraint logic.  In T. Husfeldt and I. A. Kanj, editors, 10th International Symposium on Parameterized and Exact Computation, IPEC 2015, September 16-18, 2015, Patras, Greece, volume 43 of LIPIcs, pages 282–293. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015.  doi:10.4230/LIPIcs.IPEC.2015.282.
  * [59] Y. Wang.  Max flows in planar graphs with vertex capacities.  ACM Trans. Algorithms, 18(1), 2022.  doi:10.1145/3504032.
  * [60] M. Wrochna.  Reconfiguration in bounded bandwidth and tree-depth.  J. Comput. Syst. Sci., 93:1–10, 2018.  doi:10.1016/j.jcss.2017.11.003.

##  Appendix A Curves on Closed Surfaces

Let $\Sigma_{g}$ denote a connected orientable closed surface of genus $g$.
For instance, $\Sigma_{0}$ is a 2-sphere $S^{2}$ and $\Sigma_{1}$ is a torus.
In contrast to the 2-sphere case, when $k=2$, the reconfiguration is always
possible on $\Sigma_{g}$ for $g\geq 1$.

######  Theorem A.1.

Let $\mathcal{P}=(P_{1},P_{2})$ and $\mathcal{Q}=(Q_{1},Q_{2})$ be linkages on
$\Sigma_{g}$ for $g\geq 1$. Then, $\mathcal{P}$ is always reconfigurable to
$\mathcal{Q}$.

###### Proof Sketch.

A small perturbation allows us to assume that the curves intersect
transversally. The proof is by induction on the number of intersection points
of $\mathcal{P}$ and $\mathcal{Q}$, say $n$. The case $n=4$ is obvious since
they intersect only at the endpoints. Suppose that the statement holds up to
$n-1$. We first cut the surface $\Sigma_{g}$ along $\mathcal{P}$ and
$\mathcal{Q}$. Let $S$ be a connected component. Then, $\partial S$ is a
disjoint union of alternating cycles of edges derived from $\mathcal{P}$ and
$\mathcal{Q}$. If $\partial S$ has a $2$-cycle, then one can eliminate this
cycle by a single step. On the other hand, if $\partial S$ has at least six
edges, then there are two edges derived from $P_{i}$ for some $i=1,2$, and
thus one can find another $\mathcal{P}^{\prime}$ such that the number of
intersections between the curves in $\mathcal{P}^{\prime}$ and $\mathcal{Q}$
is less than $n$.

Therefore, we shall consider the case where $\partial S$ is a $4$-cycle and
show that there is a connected component $S$ such that the genus of the closed
surface obtained by capping its boundary with disks is at least $1$. Then, one
finds a desired $\mathcal{P}^{\prime}$ after some steps. Assume that there is
no such an $S$, that is, all connected components are disks, and hence we have
a cell decomposition of $\Sigma_{g}$. Let $m$ be the number of $2$-cells,
namely disks. Then, the numbers of $1$\- and $0$-cells are $2m$ and $m+2$,
respectively. It follows that the Euler characteristic of $\Sigma_{g}$ is
$(m+2)-2m+m=2$, and thus $g=0$ (see [18, Section 1.1.1] for example). This is
a contradiction. ∎

##  Appendix B $\mu(P_{i},Q_{j})$ Takes the Same Value

In this section, we only consider piecewise smooth curves and paths on a
plane. For an oriented curve $C$, let $\overline{C}$ denote the curve with the
opposite orientation. We first summarize basic properties of $\mu$ that follow
from definition.

  1. (A1)

$\mu(C_{1},C_{2})=-\mu(C_{2},C_{1})=-\mu(C_{1},\overline{C}_{2})$ for any
oriented curves $C_{1}$ and $C_{2}$.

  2. (A2)

Suppose that $C_{1}\cup C_{2}$ is an oriented curve obtained by concatenating
two oriented curves $C_{1}$ and $C_{2}$, and let $C_{3}$ be another oriented
curve. Then, $\mu(C_{1}\cup C_{2},C_{3})=\mu(C_{1},C_{3})+\mu(C_{2},C_{3})$
and $\mu(C_{3},C_{1}\cup C_{2})=\mu(C_{3},C_{1})+\mu(C_{3},C_{2})$.

  3. (A3)

$\mu(C_{1},C_{2})=0$ for any oriented closed curves $C_{1}$ and $C_{2}$ (by
the Jordan curve theorem).

By using these properties, we show that $\mu(P_{i},Q_{j})$ takes the same
value in a two-face instance.

######  Lemma B.1.

In a two-face instance $(G,\mathcal{P},\mathcal{Q})$ of Disjoint Paths
Reconfiguration, $\mu(P_{i},Q_{j})$ takes the same value for any distinct
$i,j\in[k]$.

###### Proof.

Let $s_{k+1}$ and $s_{k+2}$ be points on $\partial{S}$ such that
$s_{k},s_{k+1},s_{k+2}$, and $s_{1}$ lie on $\partial S$ clockwise in this
order. Similarly, let $t_{k+1}$ and $t_{k+2}$ be points on $\partial{T}$ such
that $t_{k},t_{k+1},t_{k+2}$, and $t_{1}$ lie on $\partial T$ clockwise in
this order. Then, there exist simple curves $P_{k+1}$ from $s_{k+1}$ to
$t_{k+1}$ and $P_{k+2}$ from $s_{k+2}$ to $t_{k+2}$ such that
$\\{P_{1},\dots,P_{k},P_{k+1},P_{k+2}\\}$ forms a linkage in
$\mathbb{R}^{2}\setminus(S\cup T)$. Similarly, let $Q_{k+1}$ and $Q_{k+2}$ be
simple curves such that $\\{Q_{1},\dots,Q_{k},Q_{k+1},Q_{k+2}\\}$ forms a
linkage in $\mathbb{R}^{2}\setminus(S\cup T)$. In what follows, we show that
$\mu(P_{i},Q_{j})=\mu(P_{k+1},Q_{k+2})$ for any distinct $i,j\in[k]$.

Let $i,j\in[k]$ with $i\neq j$. Let $C_{s}$ be a curve in $S$ from $s_{k+1}$
to $s_{i}$, and let $C_{t}$ be a curve in $T$ from $t_{i}$ to $t_{k+1}$. Since
$P_{i}\cup C_{t}\cup\overline{P_{k+1}}\cup C_{s}$ and $\overline{P_{j}}\cup
Q_{j}$ are oriented closed curves, by (A3), we obtain $\mu(P_{i}\cup
C_{t}\cup\overline{P_{k+1}}\cup C_{s},\overline{P_{j}}\cup Q_{j})=0$. Since
$\overline{P_{j}}\cap(P_{i}\cup C_{t}\cup\overline{P_{k+1}}\cup
C_{s})=\emptyset$ and $Q_{j}\cap(C_{s}\cup C_{t})=\emptyset$, this together
with (A2) shows that $\mu(P_{i},Q_{j})+\mu(\overline{P_{k+1}},Q_{j})=0$. By
(A1), we obtain $\mu(P_{i},Q_{j})=\mu(P_{k+1},Q_{j})$.

By the same argument, we can show that
$\mu(P_{k+1},Q_{j})=\mu(P_{k+1},Q_{k+2})$. Therefore, we obtain
$\mu(P_{i},Q_{j})=\mu(P_{k+1},Q_{k+2})$ for any distinct $i,j\in[k]$, which
completes the proof. ∎

##  Appendix C Variation of the Reduction for Theorem 1.1.

In this section, we briefly sketch the modification of the proof for Theorem
1.1 to show that the $\mathsf{PSPACE}$-completeness of Disjoint $s$-$t$ Paths
Reconfiguration also holds for graphs of bounded bandwidth.

The basic line of reduction is identical to the proof for Theorem 1.1. We
require the constructed graph $G$ to have bounded bandwidth if the AND/OR
graph $H$ in a given instance of the NCL reconfiguration has bounded
bandwidth.

To ensure that $G$ has bounded bandwidth, we only change the construction of
two paths, the red path $P_{1}$ and the blue path $P_{2}$. In the original
proof of Theorem 1.1, we have a choice of the ordering along which $P_{1}$
goes through all the AND vertex gadgets and weight-$2$ edge gadgets, and
$P_{2}$ goes through all the AND vertex gadgets, OR vertex gadgets and
weight-$1$ edge gadgets. We will exploit this freedom.

Since $H$ has bounded bandwidth, there exists an injective map $\pi\colon
V(H)\to\mathbb{Z}$ such that $|\pi(u)-\pi(v)|\leq c$ for some constant $c$.
Let $H^{\circ}$ be the graph that is obtained from $H$ by subdividing each
edge of $H$, i.e., replacing each edge of $H$ by a path of length two. We
construct an injective map $\pi^{\circ}\colon V(H^{\circ})\to\mathbb{Z}$ as
follows. For each vertex $v\in V(H)$, set $\pi^{\circ}(v)=4\pi(v)$. For a
vertex $w\in V(H^{\circ})$ that is used for subdividing an edge $\\{u,v\\}\in
E(H)$, where $\pi(u)<\pi(v)$, we set $\pi^{\circ}(w)$ as
$\pi^{\circ}(w)\in\\{\pi(u)+1,\pi(u)+2,\pi(u)+3\\}$. This is possible since
the AND/OR graph $H$ is $3$-regular. Observe that the bandwidth of
$\pi^{\circ}$ is at most $4c+3$. For more information on the bandwidth of
graphs obtained by graph operations, see [12].

Now, we replace each vertex of $H^{\circ}$ by the corresponding gadget given
in the proof of Theorem 1.1. To ease the presentation, we add one isolated
blue vertex to each weight-$2$ edge gadget, one isolated red vertex to each
weight-$1$ edge gadget, and one isolated red vertex to each OR vertex gadget
so that each gadget contains at least one red and at least one blue vertices.
Note that each gadget is of constant order (at most eight), even after adding
isolated vertices. Therefore, this replacement may increase the bandwidth at