# Shortest Two Disjoint Paths in Conservative Graphs

Ildikó Schlotter1,2

( 1Centre for Economic and Regional Studies, Hungary
2Budapest University of Technology and Economics, Hungary
)

###### Abstract

We consider the following problem that we call the Shortest Two Disjoint Paths
problem: given an undirected graph $G=(V,E)$ with edge weights
$w:E\rightarrow\mathbb{R}$, two terminals $s$ and $t$ in $G$, find two
internally vertex-disjoint paths between $s$ and $t$ with minimum total
weight. As shown recently by Schlotter and Sebő (2022), this problem becomes
$\mathsf{NP}$-hard if edges can have negative weights, even if the weight
function is conservative, i.e., there are no cycles in $G$ with negative total
weight. We propose a polynomial-time algorithm that solves the Shortest Two
Disjoint Paths problem for conservative weights in the case when the negative-
weight edges form a constant number of trees in $G$.

##  1 Introduction

Finding disjoint paths between given terminals is a fundamental problem in
algorithmic graph theory and combinatorial optimization. Besides its
theoretical importance, it is also motivated by numerous applications in
transportation, VLSI design, and network routing. In the Disjoint Paths
problem, we are given $k$ terminal pairs $(s_{i},t_{i})$ for
$i\in\\{1,\dots,k\\}$ in an undirected graph $G$, and the task is to find
pairwise vertex-disjoint paths $P_{1},\dots,P_{k}$ so that $P_{i}$ connects
$s_{i}$ with $t_{i}$ for each $i\in\\{1,\dots,k\\}$. This problem was shown to
be $\mathsf{NP}$-hard by Karp [10] when $k$ is part of the input, and remains
$\mathsf{NP}$-hard even on planar graphs [13]. Robertson and Seymour [14]
proved that there exists an $f(k)n^{3}$ algorithm for Disjoint Paths with $k$
terminal pairs, where $n$ is the number of vertices in $G$ and $f$ some
computable function; this celebrated result is among the most important
achievements of graph minor theory. In the Shortest Disjoint Paths problem we
additionally require that $P_{1},\dots,P_{k}$ have minimum total length (in
terms of the number of edges). For fixed $k$, the complexity of this problem
is one of the most important open questions in the area. Even the case for
$k=2$ had been open for a long time, until Björklund and Husfeldt [3] gave a
randomized polynomial-time algorithm for it in 2019. For directed graphs the
problem becomes much harder: the Directed Disjoint Paths problem is
$\mathsf{NP}$-hard already for $k=2$. The Disjoint Paths problem and its
variants have also received considerable attention when restricted to planar
graphs [7, 6, 11, 1, 5, 16, 12].

The variant of Disjoint Paths when $s_{1}=\dots=s_{k}=s$ and
$t_{1}=\dots=t_{k}=t$ is considerably easier, since one can find $k$ pairwise
(openly vertex- or edge-) disjoint paths between $s$ and $t$ using a max-flow
computation. Applying standard techniques for computing a minimum-cost flow
(see e.g. [17]), one can even find $k$ pairwise disjoint paths between $s$ and
$t$ with minimum total weight, given non-negative weights on the edges. Notice
that if negative weights are allowed, then flow techniques break down for
undirected graphs: in order to construct an appropriate flow network based on
our undirected graph $G$, the standard technique is to direct each edge of $G$
in both directions; however, if edges can have negative weight, then this
operation creates negative cycles consisting of two arcs, an obstacle for
computing a minimum-cost flow. Recently, Schlotter and Sebő [15] have shown
that this issue is a manifestation of a complexity barrier: finding two openly
disjoint paths with minimum total weight between two vertices in an undirected
edge-weighted graph is $\mathsf{NP}$-hard, even if weights are _conservative_
(i.e., no cycle has negative total weight) and each edge has weight in
$\\{-1,1\\}$.111In fact, Schlotter and Sebő use an equivalent formulation of
the problem where, instead of finding two openly disjoint paths between $s$
and $t$, the task is to find two vertex-disjoint paths between
$\\{s_{1},s_{2}\\}$ and $\\{t_{1},t_{2}\\}$ for four vertices
$s_{1},s_{2},t_{1},t_{2}\in V$. Note that negative edge weights occur in
network problems due to various reasons: for example, they might arise as a
result of some reduction (e.g., deciding the feasibility of certain scheduling
problems with deadlines translates into finding negative-weight cycles), or as
a result of data that is represented on a logarithmic scale. We remark that
the Single-Source Shortest Paths problem is the subject of active research for
the case when negative edges are allowed; see Bernstein et al. [2] for an
overview of the area and their state-of-the-art algorithm running in near-
linear time on directed graphs.

Our contribution. We consider the following problem which concerns finding
paths between two fixed terminals (as opposed to the classic Shortest Disjoint
Paths problem):

Shortest Two Disjoint Paths: Input: An undirected graph $G=(V,E)$, a weight
function $w\colon E\to\mathbb{R}$ that is conservative on $G$, and two
vertices $s$ and $t$ in $G$. Task: Find two paths $P_{1}$ and $P_{2}$ between
$s$ and $t$ with $V(P_{1})\cap V(P_{2})=\\{s,t\\}$ that minimizes
$w(P_{1})+w(P_{2})$.

A _solution_ for an instance $(G,w,s,t)$ of Shortest Two Disjoint Paths is a
pair of $(s,t)$-paths that are openly disjoint, i.e., do not share vertices
other than their endpoints.

From the $\mathsf{NP}$-hardness proof for Shortest Two Disjoint Paths by
Schlotter and Sebő [15] it follows that the problem remains $\mathsf{NP}$-hard
even if the set of negative-weight edges forms a perfect matching. Motivated
by this intractability, we focus on the “opposite” case when the subgraph of
$G$ spanned by the set $E^{-}=\\{e\in E:w(e)<0\\}$ of negative-weight edges,
denoted by $G[E^{-}]$, has only few connected components.222See Section 2 for
the precise definition of a subgraph spanned by an edge set. Note that since
$w$ is conservative on $G$, the graph $G[E^{-}]$ is acyclic. Hence, if $c$
denotes the number of connected components in $G[E^{-}]$, then $G[E^{-}]$ in
fact consists of $c$ trees.

We can think of our assumption that $c$ is constant as a compromise for
allowing negative-weight edges but requiring that they be confined to a small
part of the graph. For a motivation, consider a network where negative-weight
edges arise as some rare anomaly. Such an anomaly may occur when, in a certain
part of a computer network, some information can be collected while traversing
the given edge. If such information concerns, e.g., the detection of
(possibly) faulty nodes or edges in the network, then it is not unreasonable
to assume that these faults are concentrated to a certain part of the network,
due to underlying physical causes that are responsible for the fault.

Ideally, one would aim for an algorithm that is fixed-parameter tractable when
parameterized by $c$; however, already the case $c=1$ turns out to be
challenging. We prove the following result, which can be thought of as a first
step towards an FPT algorithm:

######  Theorem 1.

For each constant $c\in\mathbb{N}$, Shortest Two Disjoint Paths can be solved
in polynomial time on instances where the set of negative edges spans $c$
trees in $G$.

Our algorithm first applies standard flow techniques to find minimum-weight
solutions among those that have a simple structure in the sense that there is
no negative tree in $G[E^{-}]$ used by both paths. To deal with more complex
solutions where there is at least one tree $T$ in $G[E^{-}]$ used by both
paths, we use recursion to find two openly disjoint paths from $s$ to $T$, and
from $T$ to $t$; to deal with the subpaths of the solution that heavily use
negative edges from $T$, we apply an intricate dynamic programming method that
is based on significant insight into the structural properties of such
solutions.

Organization. We give all necessary definitions in Section 2. In Section 3 we
make initial observations about optimal solutions for an instance $(G,w,s,t)$
of Shortest Two Disjoint Paths, and we also present a lemma of key importance
that will enable us to create solutions by combining partial solutions that
are easier to find (Lemma 10). We present the algorithm proving our main
result, Theorem 1, in Section 4. In Section 4.1 we give a general description
of our algorithm, and explain which types of solutions can be found using
flow-based techniques. We proceed in Section 4.2 by establishing structural
observation that we need to exploit in order to find those types of solutions
where more advanced techniques are necessary. Section 4.3 contains our dynamic
programming method for finding partial solutions which, together with Lemma
10, form the heart of our algorithm. We assemble the proof of Theorem 1 in
Section 4.4 using our findings in the previous sections, and finally pose some
questions for further research in Section 5.

##  2 Notation

For a positive integer $\ell$, we use $[\ell]\coloneqq\\{1,2,\dots,\ell\\}$.
For two subsets $X$ and $Y$ of some universe, let $X\Delta Y=(X\setminus
Y)\cup(Y\setminus X)$ denote their symmetric difference.

Let a graph $G$ be a pair $(V,E)$ where $V$ and $E$ are the set of vertices
and edges, respectively. For two vertices $u$ and $v$ in $V$, an edge
connecting $u$ and $v$ is denoted by $uv$ or $vu$.

For a set of $X$ of vertices (or edges), let $G-X$ denote the subgraph of $G$
obtained by deleting the vertices (or edges, respectively) of $X$; if
$X=\\{x\\}$ then we may simply write $G-x$ instead of $G-\\{x\\}$. Given a set
$U\subseteq V$ of vertices in $G$, the subgraph of $G$ _induced by_ $U$ is the
graph $G-(V\setminus U)$. Given a set $F\subseteq E$ of edges in $G$, we
denote by $V(F)$ the vertices incident to some edge of $F$. The subgraph of
$G$ _spanned by_ $F$ is the graph $(V(F),F)$; we denote this subgraph as
$G[F]$.

A _walk_ $W$ in $G$ is a series $e_{1},e_{2},\dots,e_{\ell}$ of edges in $G$
for which there exist vertices $v_{0},v_{1},\dots,v_{\ell}$ in $G$ such that
$e_{i}=v_{i-1}v_{i}$ for each $i\in[\ell]$; note that both vertices and edges
may appear repeatedly on a walk. We denote by $V(W)$ the set of vertices
_contained by_ or _appearing on_ $W$, that is,
$V(W)=\\{v_{0},v_{1},\dots,v_{\ell}\\}$. The _endpoints_ of $W$ are $v_{0}$
and $v_{\ell}$, or in other words, it is a _$(v_{0},v_{\ell})$ -walk_, while
all vertices on $W$ that are not endpoints are _inner vertices_. If
$v_{0}=v_{\ell}$, then we say that $W$ is a _closed walk_.

A _path_ is a walk on which no vertex appears more than once. By a slight
abuse of notation, we will usually treat a path as a _set_
$\\{e_{1},e_{2},\dots,e_{\ell}\\}$ of edges for which there exist distinct
vertices $v_{0},v_{1},\dots,v_{\ell}$ in $G$ such that $e_{i}=v_{i-1}v_{i}$
for each $i\in[\ell]$. For any $i$ and $j$ with $0\leq i\leq j\leq\ell$ we
will write $P[v_{i},v_{j}]$ for the _subpath_ of $P$ between $v_{i}$ and
$v_{j}$, consisting of edges $e_{i+1},\dots,e_{j}$. Note that since we
associate no direction with $P$, we have $P[v_{i},v_{j}]=P[v_{j},v_{i}]$.
Given two vertices $s$ and $t$, an $(s,t)$-path is a path whose endpoints are
$s$ and $t$. Similarly, for two subsets $S$ and $T$ of vertices, an
$(S,T)$-path is a path with one endpoint in $S$ and the other endpoint in $T$.

We say that two paths are _vertex-_ or _edge-disjoint_ , if they do not share
a common vertex or edge, respectively. Two paths are _openly disjoint_ , if
they share no common vertices apart from possibly their endpoints. Given
vertices $s_{1},s_{2},t_{1},$ and $t_{2}$, we say that two
$(\\{s_{1},s_{2}\\},\\{t_{1},t_{2}\\})$-paths are _permissively disjoint_ , if
a vertex $v$ can only appear on both paths if either $v=s_{1}=s_{2}$ or
$v=t_{1}=t_{2}$. Two paths properly intersect, if they share at least one
edge, but neither is the subpath of the other.

A _cycle_ in $G$ is a set $\\{e_{1},e_{2},\dots,e_{\ell}\\}$ of distinct edges
in $G$ such that $e_{1},e_{2},\dots,e_{\ell-1}$ form a path in $G-e_{\ell}$
whose endpoints are connected by $e_{\ell}$. A set $T\subseteq E$ of edges in
$G$ is _connected_ , if for every pair of edges $e$ and $e^{\prime}$ in $T$,
there is a path contained in $T$ containing both $e$ and $e^{\prime}$. If $T$
is connected and _acyclic_ , i.e., contains no cycle, then $T$ is a _tree_ in
$G$. Given two vertices $a$ and $b$ in a tree $T$, we denote by $T[a,b]$ the
unique path contained in $T$ whose endpoints are $a$ and $b$. For an edge
$uv\in T$ and a path $P$ within $T$ such that $uv\notin P$, we say that $v$
_is closer to $P$_ in $T$ than $u$, if $v\in V(T[u,p])$ for some vertex $p\in
V(P)$.

Given a weight function $w\colon E\to\mathbb{R}$ on the edge set of $G$, we
define the _weight_ of any edge set $F\subseteq E$ as $w(F)=\sum_{e\in
F}w(e)$. We extend this notion for any pair $\mathcal{F}=(F_{1},F_{2})$ of
edge sets by letting $w(\mathcal{F})=w(F_{1})+w(F_{2})$. The restriction of
$w$ to an edge set $F\subseteq E$, i.e., the function whose domain is $F$ and
has value $w(f)$ on each $f\in F$, is denoted by $w_{|F}$. We say that $w$
(or, to make the dependency on $G$ explicit, the weighted graph $(G,w)$) is
_conservative_ , if no cycle in $G$ has negative total weight.

##  3 Structural Observations

Let $G=(V,E)$ be an undirected graph with a conservative weight function
$w:E\rightarrow\mathbb{R}$. Let $E^{-}=\\{e\in E:w(e)<0\\}$ denote the set of
negative edges, and $\mathcal{T}$ the set of negative trees they form. More
precisely, let $\mathcal{T}$ be the set of connected components in the
subgraph $G[E^{-}]$; the acyclicity of each $T\in\mathcal{T}$ follows from the
conservativeness of $w$. For any subset $\mathcal{T}^{\prime}$ of
$\mathcal{T}$, we use the notation
$E(\mathcal{T}^{\prime})=\bigcup_{T\in\mathcal{T}^{\prime}}E(T)$ and
$V(\mathcal{T}^{\prime})=\bigcup_{T\in\mathcal{T}^{\prime}}V(T)$.

In Section 3.1 we gather a few useful properties of conservative weight
functions. In Section 3.2 we collect observations on how an optimal solution
can use different trees in $\mathcal{T}$. We close the section with a lemma of
key importance in Section 3.3 that enables us to compose solutions by
combining two path pairs without violating our requirement of disjointness.

###  3.1 Implications of Conservative Weights

The next two lemmas establish implications of the conservativeness of our
weight function. Lemma 2 concerns closed walks, while Lemma 3 considers paths
running between two vertices on some negative tree in $\mathcal{T}$. These
lemmas will be useful in proofs where a given hypothetical solution is
“edited” – by removing certain subpaths from it and replacing them with paths
within some negative tree – in order to obtain a specific form without
increasing its weight.

######  Lemma 2.

If $W$ is a closed walk that does not contain any edge with negative weight
more than once, then $w(W)\geq 0$.

###### Proof.

Let $Z$ be the set of edges that includes an edge $e$ of the graph if and only
if $e$ appears an odd number of times on $W$. Note that since any edge used at
least twice in $W$ has non-negative weight, we know $w(Z)\leq w(W)$. Moreover,
since $W$ is a walk, each vertex $v\in V$ has an even degree in the graph
$(V,Z)$. Therefore, $(V,Z)$ is the union of edge-disjoint cycles, and the
conservativeness of $w$ implies $w(Z)\geq 0$. ∎

######  Lemma 3.

Let $x,y,x^{\prime},y^{\prime}$ be four distinct vertices on a tree $T$ in
$\mathcal{T}$.

(1)

If $Q$ is an $(x,y)$-walk in $G$ that does not use any edge with negative
weight more than once, then $w(Q)\geq w(T[x,y])$.
Moreover, if $T[x,y]\not\subseteq Q$, then the inequality is strict.

(2)

If $Q$ is an $(x,y)$-path, $Q^{\prime}$ is an $(x^{\prime},y^{\prime})$-path,
and $Q$ and $Q^{\prime}$ are vertex-disjoint, then
$w(Q)+w(Q^{\prime})\geq w(T[x,y]\Delta T[x^{\prime},y^{\prime}])$.
Moreover, if $T[x,y]$ and $T[x^{\prime},y^{\prime}]$ properly intersect, then
the inequality is strict.

###### Proof.

We first start with describing a useful procedure. The input of this procedure
is a set $F\subseteq E$ that can be partitioned into a set $\mathcal{F}$ of
mutually vertex-disjoint paths, each with both endpoints on $T$, and its
output is a new weight function $w_{F}$ on $E$ fulfilling $w(F)=w_{F}(F)$.

Initially, we set $w_{F}\equiv w$. A _$T$ -leap_ in $F$ is a path in
$\mathcal{F}$ that has both endpoints on $T$, has no inner vertices on $T$,
and contains no edge of $T$. We consider each $T$-leap in $F$ one-by-one. So
let $L$ be a $T$-leap in $F$ with endpoints $a$ and $b$. We define the
_shadow_ of $L$ as the edge set $F\cap T[a,b]$. Then for each edge $f$ in the
shadow of $L$ for which $w_{Q}(f)=w(f)$, we set $w_{F}(f):=0$ and we decrease
$w_{F}(L)$ by $|w(f)|$; we may do this by decreasing $w_{F}$ on the edges of
$L$ in any way as long as the total weight of $L$ is decreased by $|w(f)|$.
Since $w$ is conservative, $w(L)+w(T[a,b])\geq 0$ by Lemma 2, and thus
$w(L)\geq|w(T[a,b])|\geq\sum\\{|w(f)|:f\textrm{ is in the shadow of }L\\}$.
Therefore, after performing this operation for each edge in the shadow of $L$,
$w_{F}(L)\geq 0$ remains true. Applying these changes for each $T$-leap in
$F$, the resulting weight function $w_{F}$ fulfills (i) $w_{F}(F)=w(F)$, (ii)
$w_{F}(L)\geq 0$ for each $T$-leap $L$ in $F$, and that (iii) $w_{F}(f)=0$ for
each edge $f$ in the shadow of $F$.

To show statement (1) of the lemma, let $Q$ be an $(x,y)$-walk in $G$. Observe
that we can assume w.l.o.g. that $Q$ is an $(x,y)$-path: if $Q$ contains
cycles, then we can repeatedly delete any cycle from $Q$, possibly of length
2, so that in the end we obtain an $(x,y)$-path whose weight is at most the
weight of $Q$ by Lemma 2, since $w$ is conservative and no edge with negative
weight is contained more than once in $Q$. Observe that any edge of $Q\cap T$
that is not in the shadow of any $T$-leap on $Q$ must lie on $T[x,y]$: indeed,
for any edge $uv\in Q\cap T$ that lies outside $T[x,y]$, with $v$ being closer
to $T[x,y]$ than $u$ in $T$, either $Q[u,x]$ or $Q[u,y]$ needs to use a
$T$-leap that contains $uv$ in its shadow. Hence, for the function $w_{Q}$
obtained by the above procedure (for $F=Q$) we get

$\displaystyle w(Q)=w_{Q}(Q)$ $\displaystyle=\sum_{f\in Q\cap
T[x,y]}w_{Q}(f)+\sum_{f\in Q\cap T\setminus T[x,y]}w_{Q}(f)+\sum_{f\in
Q\setminus T}w_{Q}(f)$ $\displaystyle\geq w(Q\cap
T[x,y])+0+\sum_{\begin{subarray}{c}\text{$L$: $L$ is a}\\\ \text{$T$-leap
on~{}$Q$}\end{subarray}}w_{Q}(L)$ $\displaystyle\geq w(T[x,y]).$

Observe also that equality is only possible if $w(Q\cap T[x,y])=w(T[x,y])$,
which in turn happens only if $T[x,y]\subseteq Q$.

To prove statement (2), assume that $Q$ and $Q^{\prime}$ are as in the
statement. Observe that any edge $f$ in $(Q\cup Q^{\prime})\cap T$ that is not
contained in $T[x,y]\Delta T[x^{\prime},y^{\prime}]$ must be in the shadow of
some $T$-leap in $Q\cup Q^{\prime}$: indeed, if $f$ is not in $T[x,y]\cup
T[x^{\prime},y^{\prime}]$, then this follows by the same arguments we used for
statement (1), and if $f\in T[x,y]\cap T[x^{\prime},y^{\prime}]$, then either
$f\in Q$ in which case it must be in the shadow of a $T$-leap on $Q^{\prime}$,
or $f\in Q^{\prime}$ in which case it is in the shadow of a $T$-leap on $Q$,
as $Q$ and $Q^{\prime}$ are vertex-disjoint. Considering the function
$w_{Q\cup Q^{\prime}}$ obtained by the above procedure, we therefore know

$\displaystyle w(Q\cup Q^{\prime})\,$ $\displaystyle=\,w_{Q\cup
Q^{\prime}}(Q\cup Q^{\prime})$ $\displaystyle=\sum_{\begin{subarray}{c}f\in
Q\cup Q^{\prime}\text{ and}\\\\[2.0pt] f\in T[x,y]\triangle
T[x^{\prime},y^{\prime}]\end{subarray}}w_{Q}(f)+\sum_{\begin{subarray}{c}f\in
Q\cup Q^{\prime}\text{ and}\\\\[2.0pt] f\notin T[x,y]\triangle
T[x^{\prime},y^{\prime}]\end{subarray}}w_{Q}(f)+\sum_{f\in Q\cup
Q^{\prime}\setminus T}w_{Q}(f)$ $\displaystyle\geq w\Big{(}(Q\cup
Q^{\prime})\cap(T[x,y]\triangle
T[x^{\prime},y^{\prime}])\Big{)}+0+\sum_{\begin{subarray}{c}\text{$L$: $L$ is
a }\\\\[1.0pt] \text{$T$-leap in~{}$Q\cup Q^{\prime}$ }\end{subarray}}w_{Q\cup
Q^{\prime}}(L)$ $\displaystyle\geq\,w(T[x,y]\triangle
T[x^{\prime},y^{\prime}]).$ (1)

To prove the last statement of the lemma, assume that $T[x,y]$ properly
intersects $T[x^{\prime},y^{\prime}]$. Since $Q$ and $Q^{\prime}$ are vertex-
disjoint, this implies that there exists an edge $f^{\star}$ in $T[x,y]\cap
T[x^{\prime},y^{\prime}]$ that is not contained in $Q\cup Q^{\prime}$ (because
neither $Q$ nor $Q^{\prime}$ can entirely contain $T[x,y]\cap
T[x^{\prime},y^{\prime}]$). Note that $Q$ must contain a leap $L^{\star}$ for
which the cycle induced by $L$ contains $f^{\star}$ (in fact, the same is true
for $Q^{\prime}$). Since $f^{\star}\notin Q_{1}\cup Q_{2}$, we have that
$f^{\star}$ is not in the shadow of $L^{\star}$, which implies that $w_{Q\cup
Q^{\prime}}(L^{\star})\geq-w(f^{\star})>0$. Consequently, inequality (1) is
strict. ∎

###  3.2 Solution Structure on Negative Trees

We first observe a simple property of minimum-weight solutions.

######  Definition 4 (Locally cheapest path pairs).

Let $s_{1},s_{2},t_{1},t_{2}$ be vertices in $G$, and let $P_{1}$ and $P_{2}$
be two permissively disjoint $(\\{s_{1},s_{2}\\},\\{t_{1},t_{2}\\})$-paths. A
path $T[u,v]$ in some $T\in\mathcal{T}$ is called a _shortcut_ for $P_{1}$ and
$P_{2}$, if $u$ and $v$ both appear on the same path, either $P_{1}$ or
$P_{2}$, and there is no inner vertex or edge of $T[u,v]$ contained in
$P_{1}\cup P_{2}$. We will call $P_{1}$ and $P_{2}$ _locally cheapest_ , if
there is no shortcut for them.

The idea behind this concept is the following. Suppose that $P_{1}$ and
$P_{2}$ are permissively disjoint
$(\\{s_{1},s_{2}\\},\\{t_{1},t_{2}\\})$-paths, and $T[u,v]$ is a shortcut for
$P_{1}$ and $P_{2}$. Suppose that $u$ and $v$ both lie on $P_{i}$ (for some
$i\in[2]$), and let $P^{\prime}_{i}$ be the path obtained by replacing
$P_{i}[u,v]$ with $T[u,v]$; we refer to this operation as _amending_ the
shortcut $T[u,v]$. Then $P^{\prime}_{i}$ is also permissively disjoint from
$P_{3-i}$ and, since Lemma 2 implies $w(P_{i}[u,v])\geq-w(T[u,v])>0$, has
weight less than $w(P_{i})$. Hence, we have the following observation.

######  Observation 5.

Let $P_{1}$ and $P_{2}$ be two permissively disjoint
$(\\{s_{1},s_{2}\\},\\{t_{1},t_{2}\\})$-paths admitting a shortcut
$T[z,z^{\prime}]$. Suppose that $z$ and $z^{\prime}$ are on the path, say,
$P_{1}$. Let $P^{\prime}_{1}$ be the path obtained by amending
$T[z,z^{\prime}]$ on $P_{1}$. Then $P^{\prime}_{1}$ and $P_{2}$ are
permissively disjoint $(\\{s_{1},s_{2}\\},\\{t_{1},t_{2}\\})$-paths and
$w(P^{\prime}_{1})<w(P_{1})$.

######  Corollary 6.

Any minimum-weight solution for $(G,w,s,t)$ is a pair of locally cheapest
paths.

For two paths $P_{1}$ and $P_{2}$, we define $\texttt{Amend}(P_{1},P_{2})$ as
the result of amending all shortcuts on $P_{1}$ and $P_{2}$ in some
arbitrarily fixed order. Observe that if shortcuts only appear on one of the
paths among $P_{1}$ and $P_{2}$, then $\texttt{Amend}(P_{1},P_{2})$ does not
depend on the order in which we amend the shortcuts. Shortcuts can be found
simply by traversing all trees $T\in\mathcal{T}$ and checking their
intersection with $P_{1}$ and $P_{2}$. This way, $\texttt{Amend}(P_{1},P_{2})$
can be computed in linear time.

For convenience, for any $(s,t)$-path $P$ and vertices $u,v\in V(P)$ we say
that $u$ _precedes_ $v$ on $P$, or equivalently, $v$ _follows_ $u$ on $P$, if
$u$ lies on $P[s,v]$. When defining a vertex as the “first” (or “last”) vertex
with some property on $P$ or on a subpath $P^{\prime}$ of $P$ then, unless
otherwise stated, we mean the vertex on $P$ or on $P^{\prime}$ that is closest
to $s$ (or farthest from $s$, respectively) that has the given property.

The following lemma shows that if two paths in a minimum-weight solution both
use negative trees $T$ and $T^{\prime}$ for some $T,T^{\prime}\in\mathcal{T}$
then, roughly speaking, they must traverse $T$ and $T^{\prime}$ in the same
order; otherwise one would be able to replace the subpaths of the solution
running between $T$ and $T^{\prime}$ by two paths, one within $T$ and one
within $T^{\prime}$, of smaller weight.

######  Lemma 7.

Let $P_{1}$ and $P_{2}$ be two openly disjoint $(s,t)$-paths of minimum total
weight, and let $T$ and $T^{\prime}$ be distinct trees in $\mathcal{T}$.
Suppose that $v_{1},v_{2},v^{\prime}_{1}$ and $v^{\prime}_{2}$ are vertices
such that $v_{i}\in V(T)\cap V(P_{i})$ and $v^{\prime}_{i}\in
V(T^{\prime})\cap V(P_{i})$ for $i\in[2]$, with $v_{1}$ preceding
$v^{\prime}_{1}$ on $P_{1}$. Then $v_{2}$ precedes $v^{\prime}_{2}$ on
$P_{2}$.

###### Proof.

Suppose for contradiction that the lemma does not hold, and assume that
$v_{1},v_{2},v^{\prime}_{1}$ and $v^{\prime}_{2}$ are as required by the
lemma, but $v_{2}$ does not precede $v^{\prime}_{2}$ on $P_{2}$. We may also
assume that $(v_{1},v_{2},v^{\prime}_{1},v^{\prime}_{2})$ forms a minimal
counterexample in the sense that
$|T[v_{1},v_{2}]|+|T^{\prime}[v^{\prime}_{1},v^{\prime}_{2}]|$ is as small as
possible. Since $P_{1}$ and $P_{2}$ have minimum total weight, by Corollary 6
we know that they are locally cheapest.

We claim that $T[v_{1},v_{2}]$ contains no vertex of $P_{1}\cup P_{2}$ as an
inner vertex. Assuming the contrary, let $u$ denote the first inner vertex on
$T[v_{1},v_{2}]$, when traversed from $v_{1}$ to $v_{2}$, that lies on
$P_{1}\cup P_{2}$. First, if $u$ lies on $P_{1}[s,v^{\prime}_{1}]$, then
$(u,v_{2},v^{\prime}_{1},v^{\prime}_{2})$ is a counterexample for the lemma
with
$|T[u,v_{2}]|+|T^{\prime}[v^{\prime}_{1},v^{\prime}_{2}]|<|T[v_{1},v_{2}]|+|T^{\prime}[v^{\prime}_{1},v^{\prime}_{2}]|$,
contradicting our assumption on $(v_{1},v_{2},v^{\prime}_{1},v^{\prime}_{2})$.
Similarly, if $u$ lies on $P_{2}[v^{\prime}_{2},t]$, then
$(v_{1},u,v^{\prime}_{1},v^{\prime}_{2})$ is a counterexample for the lemma
with
$|T[v_{1},u]|+|T^{\prime}[v^{\prime}_{1},v^{\prime}_{2}]|<|T[v_{1},v_{2}]|+|T^{\prime}[v^{\prime}_{1},v^{\prime}_{2}]|$,
again contradicting our assumption on
$(v_{1},v_{2},v^{\prime}_{1},v^{\prime}_{2})$. Assume now $u$ lies on
$P_{1}[v^{\prime}_{1},t]$. Then $T[v_{1},u]$ contains no inner vertex
belonging to $P_{1}\cup P_{2}$ by the definition of $u$, and is therefore a
shortcut for $P_{1}$ and $P_{2}$, contradicting the fact that they are locally
cheapest. Hence, it must the case that $u$ lies on $P_{2}[s,v^{\prime}_{2}]$.
Notice that $v^{\prime}_{2}$ lies on $P_{2}[u,v_{2}]$, and hence
$T[u,v_{2}]\not\subseteq P_{2}$ by $v^{\prime}_{2}\notin V(T)$. Since $P_{1}$
and $P_{2}$ are locally cheapest, $T[u,v_{2}]$ does not contain a shortcut,
and so $T[u,v_{2}]$ must contain a vertex $z$ of $P_{1}$. On the one hand, if
$z$ lies on $P_{1}[s,v^{\prime}_{1}]$, then
$(z,v_{2},v^{\prime}_{1},v^{\prime}_{2})$ is a counterexample for the lemma
with
$|T[z,v_{2}]|+|T^{\prime}[v^{\prime}_{1},v^{\prime}_{2}]|<|T[v_{1},v_{2}]|+|T^{\prime}[v^{\prime}_{1},v^{\prime}_{2}]|$;
on the other hand, if $z$ lies on $P_{1}[v^{\prime}_{1},t]$, then
$(v^{\prime}_{1},v^{\prime}_{2},z,u)$ is a counterexample for the lemma with
$|T^{\prime}[v^{\prime}_{1},v^{\prime}_{2}]|+|T[z,u]|<|T[v_{1},v_{2}]|+|T^{\prime}[v^{\prime}_{1},v^{\prime}_{2}]|$.
In either case, we get a contradiction.

By symmetry, we also obtain that $T^{\prime}[v^{\prime}_{1},v^{\prime}_{2}]$
contains no vertex of $P_{1}\cup P_{2}$ as an inner vertex. Consider the
closed walk

$W=P_{1}[v_{1},v^{\prime}_{1}]\cup
T^{\prime}[v^{\prime}_{1},v^{\prime}_{2}]\cup P_{2}[v^{\prime}_{2},v_{2}]\cup
T[v_{2},v_{1}].$

By the facts we just proved, $T[v_{1},v_{2}]\cup
T^{\prime}[v^{\prime}_{1},v^{\prime}_{2}]$ shares no vertices with $P_{1}\cup
P_{2}$ except the endpoints, so by the disjointness of $P_{1}$ and $P_{2}$ we
know that no edge of $E^{-}$ is contained more than once in $W$. Hence, Lemma
2 yields $w(W)\geq 0$.

Define the paths $S_{1}$ and $S_{2}$ as

$\displaystyle S_{1}$ $\displaystyle=P_{1}[s,v_{1}]\cup T[v_{1},v_{2}]\cup
P_{2}[v_{2},t];$ $\displaystyle S_{2}$
$\displaystyle=P_{2}[s,v^{\prime}_{2}]\cup
T^{\prime}[v^{\prime}_{2},v^{\prime}_{1}]\cup P_{1}[v^{\prime}_{1},t].$

Observe that $S_{1}$ and $S_{2}$ are two openly disjoint $(s,t)$-paths with
weight

$\displaystyle w(S_{1})+$ $\displaystyle
w(S_{2})=w(P_{1})+w(P_{2})+w(T[v_{1},v_{2}]\cup
T^{\prime}[v^{\prime}_{1},v^{\prime}_{2}])-w(P_{1}[v_{1},v^{\prime}_{1}]\cup
P_{2}[v^{\prime}_{2},v_{2}])$
$\displaystyle=w(P_{1})+w(P_{2})+w(T[v_{1},v_{2}]\cup
T^{\prime}[v^{\prime}_{1},v^{\prime}_{2}])-w\left(W\setminus(T[v_{1},v_{2}]\cup
T^{\prime}[v^{\prime}_{1},v^{\prime}_{2}])\right)$
$\displaystyle<w(P_{1})+w(P_{2})$

where we used that $w(T[v_{1},v_{2}]\cup
T^{\prime}[v^{\prime}_{1},v^{\prime}_{2}])<0$ and hence
$w(W\setminus(T[v_{1},v_{2}]\cup
T^{\prime}[v^{\prime}_{1},v^{\prime}_{2}]))>0$. This contradicts our
assumption that $P_{1}$ and $P_{2}$ have minimum total weight. ∎

The following lemma is a consequence of Corollary 6 and Lemma 7, and considers
a situation when one of the paths in an optimal solution visits a negative
tree $T\in\mathcal{T}$ at least twice, and visits some
$T^{\prime}\in\mathcal{T}\setminus\\{T\\}$ in between.

######  Lemma 8.

Let $P_{1}$ and $P_{2}$ be two openly disjoint $(s,t)$-paths of minimum total
weight, and let $T$ and $T^{\prime}$ be distinct trees in $\mathcal{T}$.
Suppose that $v_{1},v^{\prime}_{2}$, and $v_{3}$ are vertices appearing in
this order on $P_{1}$ when traversed from $s$ to $t$, and suppose
$v_{1},v_{3}\in V(T)$ while $v^{\prime}_{2}\in V(T^{\prime})$. Then

  * •

$V(P_{2})\cap V(T)\neq\emptyset$;

  * •

$V(P_{2})\cap V(T^{\prime})=\emptyset$;

  * •

no vertex of $V(P_{1})\cap V(T^{\prime})$ precedes $v_{1}$ or follows $v_{3}$
on $P_{1}$.

###### Proof.

First note that $P_{1}$ and $P_{2}$ are locally cheapest by Corollary 6. Since
$v^{\prime}_{2}\notin V(T)$ but $v_{2}$ lies on $P_{1}[v_{1},v_{3}]$, we know
$T[v_{1},v_{3}]\not\subseteq P_{1}$, and thus $T[v_{1},v_{3}]$ must contain a
vertex of $P_{2}$, say $u$, as otherwise it admits a shortcut.

Second, assume for contradiction that there exists a vertex $u^{\prime}\in
V(P_{2})\cap V(T^{\prime})$. On the one hand, if $u$ precedes $u^{\prime}$ on
$P_{2}$, then by Lemma 7 $v_{3}$ should precede $v^{\prime}_{2}$ on $P_{1}$,
contradicting our assumptions. On the other hand, if $u^{\prime}$ precedes $u$
on $P_{2}$, then by Lemma 7 $v^{\prime}_{2}$ should precede $v_{1}$ on
$P_{1}$, contradicting our assumptions.

Third, assume that $V(P_{1})\cap V(T^{\prime})$ contains a vertex $u^{\prime}$
that either precedes $v_{1}$ or follows $v_{3}$ on $P_{1}$. Note that either
$v_{1}$ or $v_{3}$ lies between $v^{\prime}_{2}$ and $u^{\prime}$ on $P_{1}$,
and thus $T[u^{\prime},v^{\prime}_{2}]\not\subseteq P_{1}$. However,
$T[u^{\prime},v^{\prime}_{2}]$ cannot contain any vertex of $P_{2}$ (as we
have just proved), and therefore $T[u^{\prime},v^{\prime}_{2}]$ contains a
shortcut, contradicting the fact that $P_{1}$ and $P_{2}$ are locally
cheapest. ∎

We say that two paths $P_{1}$ and $P_{2}$ are _in contact_ at $T$, if there is
a tree $T\in\mathcal{T}$ and two distinct vertices $v_{1}$ and $v_{2}$ in $T$
such that $v_{1}$ lies on $P_{1}$, and $v_{2}$ lies on $P_{2}$. Lemmas 7 and 8
imply the following fact that will enable us to use recursion in our algorithm
to find solutions that consist of two paths in contact.

######  Lemma 9.

Let $P_{1}$ and $P_{2}$ be two openly disjoint $(s,t)$-paths of minimum total
weight, and assume that they are in contact at some tree $T\in\mathcal{T}$.
For $i\in[2]$, let $a_{i}$ and $b_{i}$ denote the first and last vertices of
$P_{i}$ on $T$ when traversed from $s$ to $t$. Then we can partition
$\mathcal{T}\setminus\\{T\\}$ into
$(\mathcal{T}_{s},\mathcal{T}_{0},\mathcal{T}_{t})$ such that for each
$T^{\prime}\in\mathcal{T}\setminus\\{T\\}$ and $i\in[2]$ it holds that

(i)

if $P_{i}[s,a_{i}]$ contains a vertex of $T^{\prime}$, then
$T^{\prime}\in\mathcal{T}_{s}$

(ii)

if $P_{i}[b_{i},t]$ contains a vertex of $T^{\prime}$, then
$T^{\prime}\in\mathcal{T}_{t}$

(iii)

if $P_{i}[a_{i},b_{i}]$ contains a vertex of $T^{\prime}$, then
$T^{\prime}\in\mathcal{T}_{0}$.

###### Proof.

Let $\mathcal{T}_{s}$ contain those trees in $\mathcal{T}\setminus\\{T\\}$
that share a vertex with $P_{1}[s,a_{1}]$ or $P_{2}[s,a_{2}]$. Similarly, let
$\mathcal{T}_{t}$ contain those trees in $\mathcal{T}\setminus\\{T\\}$ that
share a vertex with $P_{1}[b_{1},t]$ or $P_{2}[b_{2},t]$. Then (i) and (ii)
hold by definition. We also let
$\mathcal{T}_{0}=\mathcal{T}\setminus(\mathcal{T}_{s}\cup\mathcal{T}_{t}\cup\\{T\\})$.

Let us consider a tree $T^{\prime}\in\mathcal{T}_{s}$; then there is a vertex
$v^{\prime}\in V(T^{\prime})$ contained on $P_{1}[s,a_{1}]$ or on
$P_{2}[s,a_{2}]$. We claim that $P_{1}[a_{1},t]\cup P_{1}[a_{2},t]$ shares no
vertex with $T^{\prime}$. For the sake of contradiction, let us assume that
$u^{\prime}\in V(T^{\prime})\cap V(P_{1}[a_{1},t]\cup P_{1}[a_{2},t])$. First,
if $v^{\prime}$ and $u^{\prime}$ are on the same path, $P_{1}$ or $P_{2}$,
then this contradicts Lemma 8: since both paths share vertices with $T$,
neither of them can visit $T$ in between $v^{\prime}$ and $u^{\prime}$.
Second, if $v^{\prime}$ and $u^{\prime}$ are on different paths, then this
contradicts Lemma 7, since one of the paths visits $T^{\prime}$ before $T$,
and the other visits $T$ before $T^{\prime}$. This implies that
$\mathcal{T}_{s}\cap\mathcal{T}_{t}=\emptyset$; in particular,
$(\mathcal{T}_{s},\mathcal{T}_{0},\mathcal{T}_{t})$ is a partitioning of
$\mathcal{T}$. Additionally, we get that no tree
$T^{\prime}\in\mathcal{T}_{s}$ may contain a vertex on $P_{1}[a_{1},b_{1}]$ or
on $P_{2}[a_{2},b_{2}]$. Observe that by symmetry, the same holds for any tree
$T^{\prime}\in T_{t}$; hence (iii) follows. ∎

Given a solution $(P_{1},P_{2})$ whose paths are in contact at some tree
$T\in\mathcal{T}$, a partition of $\mathcal{T}\setminus\\{T\\}$ is _$T$
-valid_ with respect to $(P_{1},P_{2})$, if it satisfies the conditions of
Lemma 9.

###  3.3 Combining Path Pairs

The following lemma will be a crucial ingredient in our algorithm, as it
enables us to combine “partial solutions” without violating the requirement of
vertex-disjointness.

######  Lemma 10.

Let $p_{1},p_{2},q_{1},q_{2}$ be vertices in $G$, and let $T\in\mathcal{T}$
contain vertices $v_{1}$ and $v_{2}$ with $v_{1}\neq v_{2}$. Let $P_{1}$ and
$P_{2}$ be two permissively disjoint
$(\\{p_{1},p_{2}\\},\\{v_{1},v_{2}\\})$-paths in $G$, and let $Q_{1}$ and
$Q_{2}$ be two permissively disjoint
$(\\{v_{1},v_{2}\\},\\{q_{1},q_{2}\\})$-paths in $G$ that are locally
cheapest. Assume also that we can partition $\mathcal{T}$ into two sets
$\mathcal{T}_{1}$ and $\mathcal{T}_{2}$ with $T\in\mathcal{T}_{2}$ such that

(i)

$V(T)\cap V(P_{1}\cup P_{2})=\\{v_{1},v_{2}\\}$, and

(ii)

$P_{1}\cup P_{2}$ contains no edge of $E(\mathcal{T}_{2})$, and $Q_{1}\cup
Q_{2}$ contains no edge of $E(\mathcal{T}_{1})$.

Then we can find in linear time two permissively disjoint
$(\\{p_{1},p_{2}\\},\\{q_{1},q_{2}\\})$-paths $S_{1}$ and $S_{2}$ in $G$ such
that $w(S_{1})+w(S_{2})\leq w(P_{1})+w(P_{2})+w(Q_{1})+w(Q_{2})$.

###### Proof.

W.l.o.g. we may assume that $P_{i}$ is a $(p_{i},v_{i})$-path and $Q_{i}$ is a
$(v_{i},q_{i})$-path for both $i\in[2]$. Let $y_{i}$ be the first vertex on
$P_{i}$ when traversed from $p_{i}$ to $v_{i}$ that is contained in
$V(Q_{1}\cup Q_{2})$. We distinguish between three cases as follows.

Case A: $y_{1}\in V(Q_{1})$ and $y_{2}\in V(Q_{2})$. In this case let
$S_{i}=P_{i}[p_{i},y_{i}]\cup Q_{i}[y_{i},q_{i}]$ for $i\in[2]$. Observe that
$S_{1}$ and $S_{2}$ are two permissively disjoint
$(\\{p_{1},p_{2}\\},\\{q_{1},q_{2}\\})$-paths: this follows from the
definition of $y_{1}$ and $y_{2}$, and our assumptions on the disjointness of
the paths $P_{1}$ and $P_{2}$, as well as that of $Q_{1}$ and $Q_{2}$. Note
also that for any $i\in[2]$, the path $S_{i}$ can be obtained from $P_{i}\cup
Q_{i}$ by deleting the paths $P_{i}[y_{i},v_{i}]$ and $Q_{i}[v_{i},y_{i}]$.
Observe that $W_{i}=P_{i}[y_{i},v_{i}]\cup Q_{i}[v_{i},y_{i}]$ is a closed
walk. Due to (ii), no edge of $E^{-}$ may appear both on $P_{i}$ and on
$Q_{i}$. Hence, the walk $W_{i}$ does not contain any edge of $E^{-}$ more
than once, and so by Lemma 2 we get $w(W_{i})\geq 0$. This implies
$w(S_{i})=w(P_{i})+w(Q_{i})-w(W_{i})\leq w(P_{i})+w(Q_{i})$, proving the lemma
for Case A.

Case B: $y_{1}\in V(Q_{2})$ and $y_{2}\in V(Q_{1})$. In this case let
$S_{i}=P_{i}[s_{i},y_{i}]\cup Q_{3-i}[y_{i},q_{3-i}]$ for $i\in[2]$. One can
observe as in the previous case that $S_{1}$ and $S_{2}$ are two permissively
disjoint $(\\{p_{1},p_{2}\\},\\{q_{1},q_{2}\\})$-paths. Note also that for any
$i\in[2]$, the path $S_{i}$ can be obtained from $P_{i}\cup Q_{3-i}$ by
deleting the paths $P_{i}[y_{i},v_{i}]$ and $Q_{3-i}[v_{3-i},y_{i}]$. Hence we
get

$S_{1}\cup S_{2}=P_{1}\cup P_{2}\cup Q_{1}\cup
Q_{2}\setminus(P_{1}[y_{1},v_{1}]\cup Q_{1}[v_{1},y_{2}]\cup
P_{2}[y_{2},v_{2}]\cup Q_{2}[v_{2},y_{1}]).$

Observe that $W=P_{1}[y_{1},v_{1}]\cup Q_{1}[v_{1},y_{2}]\cup
P_{2}[y_{2},v_{2}]\cup Q_{2}[v_{2},y_{1}]$ is a closed walk. Due to the
disjointness of $P_{1}$ and $P_{2}$, we know that $P_{1}$ shares no edge with
$P_{2}$; similarly, $Q_{1}$ shares no edge with $Q_{2}$. Moreover, $P_{1}\cup
P_{2}$ shares no edge of $E^{-}$ with $Q_{1}\cup Q_{2}$ due to (ii).
Therefore, no edge of $E^{-}$ may appear more than once on $W$. Thus by Lemma
2 we get $w(W)\geq 0$. This implies

$w(S_{1})+w(S_{2})=w(P_{1})+w(P_{2})+w(Q_{1})+w(Q_{2})-w(W)\leq
w(P_{1})+w(P_{2})+w(Q_{1})+w(Q_{2}),$

proving the lemma for Case B.

Case C: If $y_{1}$ and $y_{2}$ both lie on the same path from $Q_{1}$ and
$Q_{2}$. By symmetry, we may assume that they both lie on $Q_{1}$. Suppose
that $y_{1}$ comes before $y_{2}$ when $Q_{1}$ is traversed starting from
$v_{1}$; the case when $y_{2}$ precedes $y_{1}$ can be dealt with in an
analogous manner.

######  Claim 11.

We can find a path $T[u,u^{\prime}]$ in linear time such that $u$ lies on
$Q_{1}\setminus Q_{1}[y_{2},q_{1}]$, $u^{\prime}$ lies on $Q_{2}$, and no
other vertex of $T[u,u^{\prime}]$ appears on $Q_{1}\cup Q_{2}$.

Proof: Recall that $y_{1}\in V(P_{1})$ implies that either $y_{1}=v_{1}$ or
$y_{1}\notin V(T)$.

First assume $y_{1}=v_{1}$, and consider the path $T[v_{1},v_{2}]$. Since
$Q_{1}$ and $Q_{2}$ may only share $q_{1}$ and $q_{2}$ (in case they
coincide), but $y_{2}\notin V(T)$, it must be the case that when travelling
through $T[v_{1},v_{2}]$ from $v_{1}$, we exit $Q_{1}$ at some vertex $u$,
meaning that the edge following $u$ on this path does not belong to $Q_{1}$.
Proceeding within $T[v_{1},v_{2}]$ towards $v_{2}$, at some point we enter a
vertex of $Q_{2}$, let $u^{\prime}$ denote this vertex. Observe that
$T[u,u^{\prime}]$ contains no vertex of $Q_{2}$ as an inner vertex by
definition. Moreover, it also cannot contain a vertex of $Q_{1}$ as an inner
vertex. Indeed, supposing that some vertex $z\in V(Q_{1})$ is an inner vertex
of $T[u,u^{\prime}]$, the path $T[u,z]$ would be a shortcut, contradict our
assumption that $Q_{1}$ and $Q_{2}$ are locally cheapest. Note also that by
$y_{2}\notin V(T)$ we also know that $u\notin Q_{1}[y_{2},q_{1}]$. Hence, the
claim holds.

Assume now $y_{1}\notin V(T)$. Then we start by walking on $Q_{1}$ from
$y_{1}$ towards $v_{1}$ until we reach a vertex of $T$ (note that, by our
assumption, $y_{2}$ is not on this path, and note also $v_{1}\in V(T)$), and
from that point on, we travel towards $v_{2}\in V(T)$ within $T$. Following
the procedure described in the previous case, we can define $u$ and
$u^{\prime}$ as the vertices where we exit $Q_{1}$ and enter $Q_{2}$,
respectively, and we can argue $T[u,u^{\prime}]$ is disjoint from $Q_{1}\cup
Q_{2}$ apart from its endpoints. Again, notice that $y_{2}$ cannot lie on the
walk from $y_{1}$ towards $u$, and so $u$ lies on $Q_{1}\setminus
Q_{1}[y_{2},q_{1}]$ and the claim holds. $\lhd$

Using Claim 11, we can now define $S_{1}$ and $S_{2}$. Let $T[u,u^{\prime}]$
be the path guaranteed by the claim. We distinguish between two cases,
depending on the place of $u$ on $Q_{1}$; see Figure 1 for an illustration.

Case
C/1:$p_{1}$$p_{2}$$y_{1}$$y_{2}$$q_{2}$$q_{1}$$v_{1}$$v_{2}$$u^{\prime}$$u$$P_{1}$$P_{2}$$Q_{1}$$Q_{2}$$T$$W$

Case
C/2:$p_{1}$$p_{2}$$y_{1}$$y_{2}$$q_{2}$$q_{1}$$v_{1}$$v_{2}$$u^{\prime}$$u$$P_{1}$$P_{2}$$Q_{1}$$Q_{2}$$T$$W_{1}$$W_{2}$

Figure 1: Illustration for Case C in the proof of Lemma 10. Paths $P_{1}$ and
$P_{2}$ are shown in blue, paths $Q_{1}$ and $Q_{2}$ in green, and edges of
$T$ in purple. Closed walks $W$ (in Case C/1), $W_{1}$ and $W_{2}$ (in Case
C/2) are depicted with coral red, dashed lines.

Case C/1: Assume that $u$ lies on $Q_{1}[v_{1},y_{1}]$. Define

$\displaystyle S_{1}$ $\displaystyle=P_{1}[p_{1},y_{1}]\cup Q_{1}[y_{1},u]\cup
T[u,u^{\prime}]\cup Q_{2}[u^{\prime},q_{2}],$ (2) $\displaystyle S_{2}$
$\displaystyle=P_{2}[p_{2},y_{2}]\cup Q_{1}[y_{2},q_{1}].$ (3)

Observe that $S_{1}$ and $S_{2}$ are two permissively disjoint
$(\\{p_{1},p_{2}\\},\\{q_{1},q_{2}\\})$-paths: this follows from the
definition of $y_{1}$ and $y_{2}$, our assumptions on the disjointness of the
paths $P_{1}$ and $P_{2}$, as well as that of $Q_{1}$ and $Q_{2}$, from the
properties of $T[u,u^{\prime}]$, and from our assumption (i).

Consider the closed walk

$W:=P_{1}[y_{1},v_{1}]\cup Q_{1}[v_{1},u]\cup T[u,u^{\prime}]\cup
Q_{2}[u^{\prime},v_{2}]\cup P_{2}[v_{2},y_{2}]\cup Q_{1}[y_{2},y_{1}].$

Note that $W$ does not contain any edge of $E^{-}$ more than once due to our
assumption (ii), the properties of $T[u,u^{\prime}]$, and the disjointness of
$P_{1}$ and $P_{2}$, as well as that of $Q_{1}$ and $Q_{2}$. Hence we get
$w(W)\geq 0$ by Lemma 2. Observe that Equations 2 and 3 yield

$\displaystyle S_{1}\cup S_{2}$ $\displaystyle=(P_{1}\cup P_{2}\cup Q_{1}\cup
Q_{2})\setminus(W\setminus T[u,u^{\prime}])\cup T[u,u^{\prime}].$

By $w(W)\geq 0$ and $w(T[u,u^{\prime}])<0$ this implies
$w(S_{1})+w(S_{2})<(P_{1})+w(P_{2})+w(Q_{1})+w(Q_{2})$, proving the lemma for
Case C/1.

Case C/2: Assume now that $u$ lies on $Q_{1}[y_{1},y_{2}]$.333The reader might
observe that the proof of Claim 11 implies that in this case only
$v_{1}=y_{1}$ is possible, but we do not use this fact in the proof of Lemma
10. Define $S_{1}$ and $S_{2}$ exactly as in Equations 2 and 3; again, $S_{1}$
and $S_{2}$ are two permissively disjoint
$(\\{p_{1},p_{2}\\},\\{q_{1},q_{2}\\})$-paths. Consider the closed walks

$\displaystyle W_{1}$ $\displaystyle=P_{1}[y_{1},v_{1}]\cup
Q_{1}[v_{1},y_{1}],$ $\displaystyle W_{2}$ $\displaystyle=Q_{1}[u,y_{2}]\cup
P_{2}[y_{2},v_{2}]\cup Q_{2}[v_{2},u^{\prime}]\cup T[u^{\prime},u],$

and observe that, owing to the same reasons as in the previous case, neither
$W_{1}$ nor $W_{2}$ contains an edge of $E^{-}$ more than once. Hence, we get
$w(W_{1}\cup W_{2})\geq 0$ by Lemma 2. Observe that Equations 2 and 3 yield

$\displaystyle S_{1}\cup S_{2}$ $\displaystyle=(P_{1}\cup P_{2}\cup Q_{1}\cup
Q_{2})\setminus(W_{1}\cup W_{2}\setminus T[u,u^{\prime}])\cup
T[u,u^{\prime}].$

By $w(W_{1}\cup W_{2})\geq 0$ and $w(T[u,u^{\prime}])<0$ this implies
$w(S_{1})+w(S_{2})<w(P_{1})+w(P_{2})+w(Q_{1})+w(Q_{2})$, proving the lemma for
Case C/2. ∎

##  4 Polynomial-Time Algorithm for Constant $|\mathcal{T}|$

This section contains the algorithm proving our main result, Theorem 1. Let
$(G,w,s,t)$ be our instance of Shortest Two Disjoint Paths with input graph
$G=(V,E)$, and assume that the set $E^{-}$ of negative edges spans $c$ trees
in $G$ for some constant $c$. We present a polynomial-time algorithm that
computes a solution for $(G,w,s,t)$ with minimum total weight, or correctly
concludes that no solution exists for $(G,w,s,t)$. The running time of our
algorithm is $O(n^{2c+9})$ where $n=|V|$, so in the language of parameterized
complexity, our algorithm is in $\mathsf{XP}$ with respect to the parameter
$c$.

In Section 4.1 we present the main ideas and definitions necessary for our
algorithm, and provide its high-level description together with some further
details. We will distinguish between so-called _separable_ and _non-separable_
solutions. Finding an optimal and separable solution will be relatively easy,
requiring extensive guessing but only standard techniques for computing
minimum-cost flows. By contrast, finding an optimal but non-separable solution
is much more difficult. Therefore, in Section 4.2 we collect useful properties
of optimal, non-separable solutions. The observations of Section 4.2 form the
basis for an important subroutine necessary for finding optimal, non-separable
solutions; this subroutine is presented in Section 4.3. We close the section
by providing a detailed pseudo-code description of our algorithm, and proving
Theorem 1 in Section 4.4.

###  4.1 The Algorithm

We distinguish between two types of solutions for our instance $(G,w,s,t)$ of
Shortest Two Disjoint Paths.

######  Definition 12 (Separable solution).

Let $(P_{1},P_{2})$ be a solution for $(G,w,s,t)$. We say that $P_{1}$ and
$P_{2}$ are _separable_ , if either

  * •

they are _not in contact_ , i.e., there is no tree $T\in\mathcal{T}$ that
shares distinct vertices with both $P_{1}$ and $P_{2}$, or

  * •

there is a _unique_ tree $T\in\mathcal{T}$ such that $P_{1}$ and $P_{2}$ are
in contact at $T$, but the intersection of $T$ with both $P_{1}$ and $P_{2}$
is a path, possibly containing only a single vertex;

otherwise they are _non-separable_.

In Section 4.1.1 we show how to find an optimal, separable solution, whenever
such a solution exists for $(G,w,s,t)$. Section 4.1.2 deals with the case when
we need to find an optimal, non-separable solution. Our algorithm for the
latter case is more involved, and relies on a subroutine that is based on
dynamic programming and is developed throughout Sections 4.2 and 4.3. The
existence of this subroutine (namely, Algorithm PermDisjoint) is stated in
Corollary 44.

####  4.1.1 Finding Separable Solutions

Suppose that $(P_{1},P_{2})$ is a minimum-weight solution for $(G,w,s,t)$ that
is separable. The following definition establishes conditions when we are able
to apply a simple strategy for finding a minimum-weight solution using well-
known flow techniques.

######  Definition 13 (Strongly separable solution).

Let $(P_{1},P_{2})$ be a solution for $(G,w,s,t)$. We say that $P_{1}$ and
$P_{2}$ are _strongly separable_ , if they are separable and they are either
not in contact at any tree of $\mathcal{T}$, or they are contact at a tree of
$\mathcal{T}$ that contains $s$ or $t$.

Suppose that $P_{1}$ and $P_{2}$ are either not in contact, or they are in
contact at a tree of $\mathcal{T}$ that contains $s$ or $t$. Let
$\mathcal{T}^{\not\ni s,t}$ denote the set of all trees in $\mathcal{T}$ that
contain neither $s$ nor $t$. For each $T\in\mathcal{T}^{\not\ni s,t}$ that
shares a vertex with $P_{i}$ for some $i\in[2]$, we define $a_{T}$ as the
first vertex on $P_{i}$ (when traversed from $s$ to $t$) that is contained in
$T$; note that $T$ cannot share vertices with both $P_{1}$ and $P_{2}$ as they
are strongly separable, so $P_{i}$ is uniquely defined.

Our approach is the following: we guess the vertex $a_{T}$ for each
$T\in\mathcal{T}^{\not\ni s,t}$, and then compute a minimum-cost flow in an
appropriately defined network. More precisely, for each possible choice of
vertices $Z=\\{z_{T}\in V(T):T\in\mathcal{T}^{\not\ni s,t}\\}$, we build a
network $N_{Z}$ as follows.

######  Definition 14 (Flow network $N_{Z}$ for strongly separable solutions).

Given a set $Z\subseteq V$ such that $Z\cap V(T)\\{z_{T}\\}$ for each
$T\in\mathcal{T}^{\not\ni s,t}$, we create $N_{Z}$ as follows. We direct each
non-negative edge in $G$ in both directions. Then for each
$T\in\mathcal{T}^{\not\ni s,t}$, we direct the edges of $T$ away from
$z_{T}$.444Directing a tree $T$ away from a vertex $z\in V(T)$ means that an
edge $uv$ in $T$ becomes an arc $(u,v)$ if and only if $T[z,u]$ has fewer
edges than $T[z,v]$; directing $T$ towards $z$ is defined analogously. If some
$T\in\mathcal{T}$ contains $s$, then we direct all edges of $T$ away from $s$;
similarly, if some $T\in\mathcal{T}$ contains $t$, then we direct all edges of
$T$ towards $t$. We assign a capacity of $1$ to each arc and to each
vertex555The standard network flow model can be adjusted by well-known
techniques to allow for vertex capacities. in the network except for $s$ and
$t$, and we retain the cost function $w$ (meaning that we define
$w(\overrightarrow{e})$ as $w(e)$ for any arc $\overrightarrow{e}$ obtained by
directing some edge $e$). We let $s$ and $t$ be the source and the sink in
$N_{Z}$, respectively.

######  Lemma 15.

If there exists a strongly separable solution for $(G,w,s,t)$ with weight $k$,
then there exists a flow of value 2 having cost $k$ in the network $N_{Z}$ for
some choice of $Z\subseteq V$ containing exactly one vertex from each tree in
$\mathcal{T}^{\not\ni s,t}$. Conversely, a flow of value 2 and cost $k$ in the
constructed network $N_{Z}$ for some $Z$ yields a solution for $(G,w,s,t)$
with weight at most $k$.

###### Proof.

Suppose first that $(P_{1},P_{2})$ is a minimum-weight solution for our
instance, and suppose that either $P_{1}$ and $P_{2}$ are not in contact, or
they are in contact at a tree of $\mathcal{T}$ that contains $s$ or $t$. Let
$\overrightarrow{P_{1}}$ and $\overrightarrow{P_{2}}$ denote the paths
obtained by directing the edges $P_{1}$ and $P_{2}$, respectively, as they are
traversed from $s$ to $t$.

First, since $P_{1}$ and $P_{2}$ are separable, we know that the intersection
of each of these paths with any tree $T\in\mathcal{T}$ either consists of at
most one vertex, or it is a single path within $T$. If some $T\in\mathcal{T}$
contains $s$ (or $t$), then it is clear that the intersection of $P_{1}$ and
$P_{2}$ with $T$ consists of two subpaths of $T$ starting at $s$ (ending at
$t$, respectively); hence, they are contained as directed paths in $N_{Z}$ for
any choice of $Z$, because all edges of $T$ are directed away from $s$
(towards $t$, respectively). Now, consider a tree $T\in\mathcal{T}^{\not\ni
s,t}$ that shares a vertex with $P_{1}$ or $P_{2}$. As $P_{1}$ and $P_{2}$
cannot be in contact at $T$ as they are strongly separable, only one of
$P_{1}$ and $P_{2}$ may share a vertex with $T$. Let $P_{i}$ denote this path,
and $a_{T}$ the first vertex on $P_{i}$ contained in $T$. Then directing the
edges of $T$ away from $a_{T}$ yields an orientation in which the intersection
of $P_{i}$ with $T$ is present as a directed path. Summarizing all this, it
follows that $\overrightarrow{P_{1}}$ and $\overrightarrow{P_{2}}$ are paths
contained in the network $N_{Z}$ defined by
$Z^{\star}=\\{a_{T}:T\in\mathcal{T}^{\not\ni s,t}\\}$. Thus, there exists a
flow of value 2 with cost $w(P_{1})+w(P_{2})$ in the network $N_{Z^{\star}}$.

For the other direction, assume that there is a flow of value 2 in $N_{Z}$ for
some vertex set $Z$ containing a vertex from each tree in
$\mathcal{T}^{\not\ni s,t}$. Such a flow must flow through two openly disjoint
path from $s$ to $t$, due to the unit capacities in $N_{Z}$. Moreover, by the
conservativeness of $w$ (and since each edge of $T$ is directed in only one
direction), there are no cycles with negative total cost in the network. This
implies that the cost of these two paths is at most the cost of our flow.
Hence, the lemma follows. ∎

Next, we show how to deal with the case when a minimum-weight solution
$(P_{1},P_{2})$ is separable, but not strongly separable; then there is a
unique tree $T\in\mathcal{T}$ at which $P_{1}$ and $P_{2}$ are in contact. In
such a case, we can simply delete an edge from $T$ in a way that paths $P_{1}$
and $P_{2}$ cease to be in contact in the resulting instance. This way, we can
reduce our problem to the case when there is a strongly separable optimal
solution; note, however, that the number of trees spanned by the negative
edges (our parameter $c$) increases by $1$.

######  Lemma 16.

If there exists a separable, but not strongly separable solution for
$(G,w,s,t)$ with weight $k$, then there exists an edge $e\in E^{-}$ such that
setting $G^{\prime}=G-e$ and $E^{\prime}=E\setminus\\{e\\}$, the instance
$(G^{\prime},w_{|E^{\prime}},s,t)$ admits a strongly separable solution with
weight at most $k$. Conversely, a solution for
$(G^{\prime},w_{|E^{\prime}},s,t)$ is also a solution for $(G,w,s,t)$ with the
same weight.

###### Proof.

If $P_{1}$ and $P_{2}$ are separable but not strongly separable, then there
exists a tree $T\in\mathcal{T}$ that contains a vertex from both paths but
neither $s$ nor $t$. Since $P_{1}$ and $P_{2}$ are separable, they both
intersect $T$ in a path (containing possibly only a single vertex); let
$P^{T}_{1}$ and $P^{T}_{2}$ denote these paths. Due to the permissive
disjointness of $P_{1}$ and $P_{2}$ and since $s,t\notin V(T)$, the paths
$P^{T}_{1}$ and $P^{T}_{2}$ are vertex-disjoint. Consequently, there exists an
edge $e\in T\setminus(P_{1}\cup P_{2})$ such that $P^{T}_{1}$ and $P^{T}_{2}$
are in different components of $T-e$. Thus, setting $G^{\prime}=G-e$ and
$E^{\prime}=E\setminus\\{e\\}$, we get that $P_{1}$ and $P_{2}$ are not in
contact in the instance $(G^{\prime},w_{|E^{\prime}},s,t)$, since they are not
in contact in $(G,w,s,t)$ at any negative tree other than $T$ (by Definition
12). Hence, they form a strongly separable solution for
$(G^{\prime},w_{|E^{\prime}},s,t)$, proving the first statement of the lemma.

The second statement of the lemma is trivial. ∎

Thanks to Lemmas 15 and 16, if there exists a minimum-weight solution for
$(G,w,s,t)$ that is separable, then we can find some minimum-weight solution
using standard algorithms for computing minimum-cost flows. In Section 4.1.2
we explain how we can find a minimum-weight non-separable solution for
$(G,w,s,t)$.

####  4.1.2 Finding Non-separable Solutions

To find a minimum-weight solution for $(G,w,s,t)$ that is not separable, we
need a more involved approach. We now provide a high-level presentation of our
algorithm for finding a non-separable solution of minimum weight. We remark
that Algorithm STDP contains a pseudocode; however, we believe that it is best
to read the following description first.

Step 1.

We guess certain properties of a minimum-weight non-separable solution
$(P_{1},P_{2})$: First, we guess a tree $T\in\mathcal{T}$ that shares distinct
vertices both with $P_{1}$ and $P_{2}$, i.e., a tree at which $P_{1}$ and
$P_{2}$ are in contact. Second, we guess a partition
$(\mathcal{T}_{s},\mathcal{T}_{0},\mathcal{T}_{t})$ of
$\mathcal{T}\setminus\\{T\\}$ that is $T$-valid with respect to
$(P_{1},P_{2})$.

Step 2.

If $\mathcal{T}_{s}\neq\emptyset$, then we guess the first vertex of $P_{1}$
and of $P_{2}$ contained in $V(T)$, denoted by $a_{1}$ and $a_{2}$,
respectively. We use recursion to compute two permissively disjoint
$(s,\\{a_{1},a_{2}\\})$-paths using only the negative trees in
$\mathcal{T}_{s}$, and to compute two permissively disjoint
$(\\{a_{1},a_{2}\\},t)$-paths using only the negative trees in
$\mathcal{T}\setminus\mathcal{T}_{s}$. Observe that by
$\mathcal{T}_{s}\neq\emptyset$ and $T\in\mathcal{T}\setminus\mathcal{T}_{s}$,
we search for these paths in graphs that contain only a strict subset of the
negative trees in $\mathcal{T}$, meaning that our parameter $c$ strictly
decreases in both constructed sub-instances. We combine the obtained pairs of
paths into a solution by using Lemma 10.
We proceed in a similar fashion when $\mathcal{T}_{t}\neq\emptyset$.

Step 3.

If $\mathcal{T}_{s}=\mathcal{T}_{t}=\emptyset$, then for both $i\in[2]$ we
guess the first and last vertex of $P_{i}$ contained in $V(T)$, denoted by
$a_{i}$ and $b_{i}$, respectively. We apply standard flow techniques to
compute two $(s,\\{a_{1},a_{2}\\})$-paths and two
$(\\{b_{1},b_{2}\\},t)$-paths with no inner vertices in $V(\mathcal{T})$ that
are pairwise permissively disjoint. Then, we apply the polynomial-time
algorithm we devise for computing a pair of permissively disjoint
$(\\{a_{1},a_{2}\\},\\{b_{1},b_{2}\\})$-paths in $G$. This algorithm is the
cornerstone of our method, and is based on important structural observations
that allow for efficient dynamic programming. We combine the obtained pairs of
paths into a solution by applying Lemma 10.

Step 4.

We output a solution of minimum weight among all solutions found in Steps 2
and 3.

Let us now provide more details about these steps; see also Algorithm STDP.

##### Step 1: Initial guesses on $\mathcal{T}$.

There are $c=|\mathcal{T}|$ possibilities to choose $T$ from $\mathcal{T}$,
and there are $3^{c-1}$ further possibilities to partition
$\mathcal{T}\setminus\\{T\\}$ into
$(\mathcal{T}_{s},\mathcal{T}_{0},\mathcal{T}_{t})$, yielding $c3^{c-1}$
possibilities in total for our guesses.

##### Step 2: Applying recursion.

To apply recursion in Step 2 when $\mathcal{T}_{s}\neq\emptyset$, we guess two
distinct vertices $a_{1}$ and $a_{2}$ in $T$, and define the following sub-
instances.

######  Definition 17 (Sub-instances for $\mathcal{T}_{s}\neq\emptyset$).

For some $\emptyset\neq\mathcal{T}_{s}\subseteq\mathcal{T}$ and distinct
vertices $a_{1}$ and $a_{2}$, let us first create a graph $G_{s}$ by adding a
new vertex $a^{\star}$, and connecting it to each of $a_{1}$ and $a_{2}$ with
an edge of weight $w_{a^{\star}}=|w(T[a_{1},a_{2}])|/2$. We create instances
$I_{s}^{1}$ and $I_{s}^{2}$ as follows:

  * •

to get $I_{s}^{1}$, we delete $E(\mathcal{T}\setminus\mathcal{T}_{s})$ and
$V(\mathcal{T}\setminus\mathcal{T}_{s})\setminus\\{a_{1},a_{2}\\}$ from
$G_{s}$, and designate $s$ and $a^{\star}$ as our two terminals;

  * •

to get $I_{s}^{2}$, we delete $V(\mathcal{T}_{s})$ from $G_{s}$, and designate
$a^{\star}$ and $t$ as our two terminals.

We use recursion to solve Shortest Two Disjoint Paths on sub-instances
$I_{s}^{1}$ and $I_{s}^{2}$. Note that conservativeness is maintained for both
$I_{s}^{1}$ and $I_{s}^{2}$, due to our choice of $w_{a^{\star}}$ and
statement (1) of lemma 3. If both sub-instances admit solutions, we obtain two
permissively disjoint $(s,\\{a_{1},a_{2}\\})$-paths
$Q^{\scalebox{0.5}{$\nearrow$}}_{1}$ and $Q^{\scalebox{0.5}{$\nearrow$}}_{2}$
from our solution to $I_{s}^{1}$ by deleting the vertex $a^{\star}$.
Similarly, we obtain two permissively disjoint $(\\{a_{1},a_{2}\\},t)$-paths
$Q^{\scalebox{0.5}{$\searrow$}}_{1}$ and $Q^{\scalebox{0.5}{$\searrow$}}_{2}$
from our solution to $I_{s}^{2}$ by deleting the vertex $a^{\star}$. Next we
use Lemma 10 to create a solution for our original instance $(G,w,s,t)$ using
paths
$Q^{\scalebox{0.5}{$\nearrow$}}_{1},Q^{\scalebox{0.5}{$\nearrow$}}_{2},Q^{\scalebox{0.5}{$\searrow$}}_{1}$,
and $Q^{\scalebox{0.5}{$\searrow$}}_{2}$.

If $\mathcal{T}_{t}\neq\emptyset$, then we proceed similarly: after guessing
two distinct vertices $b_{1}$ and $b_{2}$ in $T$, we use a construction
analogous to Definition 17.

######  Definition 18 (Sub-instances for $\mathcal{T}_{t}\neq\emptyset$).

For some $\emptyset\neq\mathcal{T}_{s}\subseteq\mathcal{T}$ and distinct
vertices $b_{1}$ and $b_{2}$, let us first create a graph $G_{t}$ by adding a
new vertex $b^{\star}$, and connecting it to each of $b_{1}$ and $b_{2}$ with
an edge of weight $w_{b^{\star}}=|w(T[b_{1},b_{2}])|/2$. We create instances
$I_{t}^{1}$ and $I_{t}^{2}$ as follows:

  * •

to get $I_{t}^{1}$, we delete $V(\mathcal{T}_{t})$ from $G_{t}$, and designate
$s$ and $b^{\star}$ as our two terminals;

  * •

to get $I_{t}^{2}$, we delete $E(\mathcal{T}\setminus\mathcal{T}_{t})$ and
$V(\mathcal{T}\setminus\mathcal{T}_{t})\setminus\\{b_{1},b_{2}\\}$ from
$G_{t}$ and designate $b^{\star}$ and $t$ as our two terminals.

We use recursion to solve Shortest Two Disjoint Paths on sub-instances
$I_{t}^{1}$ and $I_{t}^{2}$; again, conservativeness is ensured for
$I_{t}^{1}$ and $I_{t}^{2}$ by our choice of $w_{b^{\star}}$ and statement (1)
of lemma 3. If both sub-instances admit solutions, we obtain two permissively
disjoint $(s,\\{b_{1},b_{2}\\})$-paths $Q^{\scalebox{0.5}{$\nearrow$}}_{1}$
and $Q^{\scalebox{0.5}{$\nearrow$}}_{2}$ from our solution to $I_{t}^{1}$ by
deleting the vertex $b^{\star}$. Similarly, we obtain two permissively
disjoint $(\\{b_{1},b_{2}\\},t)$-paths $Q^{\scalebox{0.5}{$\searrow$}}_{1}$
and $Q^{\scalebox{0.5}{$\searrow$}}_{2}$ from our solution to $I_{t}^{2}$ by
deleting the vertex $b^{\star}$. Again, we use Lemma 10 to create a solution
for our original instance $(G,w,s,t)$ using paths
$Q^{\scalebox{0.5}{$\nearrow$}}_{1},Q^{\scalebox{0.5}{$\nearrow$}}_{2},Q^{\scalebox{0.5}{$\searrow$}}_{1}$,
and $Q^{\scalebox{0.5}{$\searrow$}}_{2}$.

We state the correctness of Step 2 in the following lemma:

######  Lemma 19.

Suppose that $(P_{1},P_{2})$ is a minimum-weight solution for $(G,w,s,t)$ such
that

  * •

$P_{1}$ and $P_{2}$ are in contact at some $T\in\mathcal{T}$,

  * •

$a_{i}$ and $b_{i}$ are the first and last vertices of $P_{i}$ contained in
$T$, respectively, for $i\in[2]$, and

  * •

$(\mathcal{T}_{s},\mathcal{T}_{0},\mathcal{T}_{s})$ is a $T$-valid partition
w.r.t. $(P_{1},P_{2})$.

Then instances $I_{s}^{1}$ and $I_{s}^{2}$ admit solutions whose total weight
(summed over all four paths) is $w(P_{1})+w(P_{2})+4w_{a^{\star}}$.
Furthermore, given a solution $\mathcal{S}_{i}$ for $I_{s}^{i}$ for both
$i\in[2]$, we can compute in linear time a solution for $(G,w,s,t)$ of weight
at most $w(\mathcal{S}_{1})+w(\mathcal{S}_{2})-4w_{a^{\star}}$.
The same holds when substituting $I_{s}^{1},I_{s}^{2},$ and $w_{a^{\star}}$
with $I_{t}^{1},I_{t}^{2}$, and $w_{b^{\star}}$ in these claims.

###### Proof.

Since $(\mathcal{T}_{s},\mathcal{T}_{0},\mathcal{T}_{t})$ is a $T$-valid
partition for $(P_{1},P_{2})$, as defined by the conditions in Lemma 9, we
know that $P_{i}[s,a_{i}]$ contains no vertices from
$V(\mathcal{T}_{t}\cup\mathcal{T}_{0}\setminus\\{T\\})$. By the definition of
$a_{i}$, the only vertex on $P_{i}[s,a_{i}]$ contained in $V(T)$ is $a_{i}$.
Thus, $P_{1}[s,a_{1}]$ and $P_{2}[s,a_{2}]$ are paths in $I_{s}^{1}$; adding
the edges $a_{1}a^{\star}$ and $a_{2}a^{\star}$, each of weight
$w_{a^{\star}}$, to these paths yields two permissively disjoint
$(s,a^{\star})$-paths in $I_{s}^{1}$. Similarly, $P_{1}[a_{1},t]$ and
$P_{2}[a_{2},t]$ are paths in $I_{s}^{2}$ due to the definition of a $T$-valid
partition; adding the edges $a_{1}a^{\star}$ and $a_{2}a^{\star}$ to them
yields two permissively disjoint $(a^{\star},t)$-paths in $I_{s}^{2}$.
Clearly, the total weight of these four paths (two in $I_{s}^{1}$ and two in
$I_{s}^{2}$) is exactly $w(P_{1})+w(P_{2})+4w_{a^{\star}}$.

As described in Step 2, a solution $\mathcal{S}_{1}$ for $I_{s}^{1}$ yields
two permissively disjoint $(s,\\{a_{1},a_{2}\\})$-paths
$Q^{\scalebox{0.5}{$\nearrow$}}_{1}$ and $Q^{\scalebox{0.5}{$\nearrow$}}_{2}$
of weight $w(\mathcal{S}_{1})-2w_{a^{\star}}$, where the term
$-2w_{a^{\star}}$ is due to the deletion of edges $a_{1}a^{\star}$ and
$a_{2}a^{\star}$. Similarly, a solution $\mathcal{S}_{2}$ for $I_{s}^{2}$
yields two permissively disjoint $(\\{a_{1},a_{2}\\},t)$-paths
$Q^{\scalebox{0.5}{$\searrow$}}_{1}$ and $Q^{\scalebox{0.5}{$\searrow$}}_{2}$
of weight $w(\mathcal{S}_{2})-2w_{a^{\star}}$.

We can assume that both these path pairs are locally cheapest, as otherwise we
can amend all shortcuts on them while preserving permissive disjointness and
without increasing their weight. Thus we can apply Lemma 10 by setting
$p_{1}=p_{2}=s$, $\\{v_{1},v_{2}\\}=\\{a_{1},a_{2}\\}$, $q_{1}=q_{2}=t$,
$P_{i}=Q^{\scalebox{0.5}{$\nearrow$}}_{i}$ and
$Q_{i}=Q^{\scalebox{0.5}{$\searrow$}}_{i}$ for $i\in[2]$,
$\mathcal{T}_{1}=\mathcal{T}_{s}$ and
$\mathcal{T}_{2}=\mathcal{T}\setminus\mathcal{T}_{s}$. Note that the
conditions Lemma 10 hold, since (i) $Q^{\scalebox{0.5}{$\nearrow$}}_{1}\cup
Q^{\scalebox{0.5}{$\nearrow$}}_{2}$ contains no vertices of $T$ other than
$a_{1}$ and $a_{2}$, and (ii) $Q^{\scalebox{0.5}{$\nearrow$}}_{1}\cup
Q^{\scalebox{0.5}{$\nearrow$}}_{2}$ contains no edge of
$\mathcal{T}_{t}\cup\mathcal{T}_{0}\cup\\{T\\}$, while
$Q^{\scalebox{0.5}{$\searrow$}}_{1}\cup Q^{\scalebox{0.5}{$\searrow$}}_{2}$
contains no edge of $\mathcal{T}_{s}$. Therefore, Lemma 10 yields two
permissively disjoint $(s,t)$-paths with weight at most
$\sum_{i=1}^{2}w(Q^{\scalebox{0.5}{$\nearrow$}}_{i})+w(Q^{\scalebox{0.5}{$\searrow$}}_{i})=w(\mathcal{S}_{1})+w(\mathcal{S}_{1})-4w_{a^{\star}}$.

To see the first claim for subinstances $I_{t}^{1}$ and $I_{t}^{2}$, one can
use analogous arguments in a straightforward manner to prove that $I_{t}^{1}$
and $I_{t}^{2}$ admits solutions whose total weight is at most
$w(P_{1})+w(P_{2})+4w_{b^{\star}}$. To show the second statement, it is clear
that a solution for $I_{t}^{1}$ and for $I_{t}^{2}$ yields two permissively
disjoint $(s,\\{b_{1},b_{2}\\})$-paths $Q^{\scalebox{0.5}{$\nearrow$}}_{1}$
and $Q^{\scalebox{0.5}{$\nearrow$}}_{2}$ and two permissively disjoint
$(\\{b_{1},b_{2}\\},t)$-paths $Q^{\scalebox{0.5}{$\searrow$}}_{1}$ and
$Q^{\scalebox{0.5}{$\searrow$}}_{2}$, and we can assume that these path pairs
are locally cheapest. Thus we can we apply Lemma 10, but note that we need to
set $p_{1}=p_{2}=t$, $q_{1}=q_{2}=s$, $\\{v_{1},v_{2}\\}=\\{b_{1},b_{2}\\}$,
$P_{i}=Q^{\scalebox{0.5}{$\searrow$}}_{i}$ and
$Q_{i}=Q^{\scalebox{0.5}{$\nearrow$}}_{i}$ for $i\in[2]$,
$\mathcal{T}_{1}=\mathcal{T}_{t}$ and
$\mathcal{T}_{2}=\mathcal{T}\setminus\mathcal{T}_{t}$. It is straightforward
to verify using the arguments of the previous paragraph that Lemma 10 then
yields a solution for $(G,w,s,t)$ with the desired bound on the weight. ∎

##### Step 3: Applying flow techniques and dynamic programming.

We now describe Step 3 in more detail, which concerns the case when
$\mathcal{T}_{s}=\mathcal{T}_{t}=\emptyset$.

First, we guess vertices $a_{1},b_{1},a_{2},$ and $b_{2}$; the intended
meaning of these vertices is that $a_{i}$ and $b_{i}$ are the first and last
vertices of $P_{i}$ contained in $V(T)$, for both $i\in[2]$. We only consider
guesses that are _reasonable_ , meaning that they satisfy the following
conditions:

  * •

if $s\in V(T)$, then $s=a_{1}=a_{2}$, otherwise $a_{1}\neq a_{2}$;

  * •

if $t\in V(T)$, then $t=b_{1}=b_{2}$, otherwise $b_{1}\neq b_{2}$;

  * •

$T[a_{1},b_{1}]$ and $T[a_{2},b_{2}]$ share at least one edge.

Then we compute four paths from $\\{s,t\\}$ to $\\{a_{1},b_{1},a_{2},b_{2}\\}$
in the graph
$G-E(\mathcal{T})-(V(\mathcal{T})\setminus\\{a_{1},a_{2},b_{1},b_{2}\\})$ with
minimum weight such that two paths have $s$ as an endpoint, the other two have
$t$ as an endpoint, and no other vertex appears on more than one path. To this
end, we define the following network and compute a minimum-cost flow of value
4 in it.

######  Definition 20 (Flow network $N_{(a_{1},b_{1},a_{2},b_{2})}$ for non-
separable solutions.).

Given vertices $a_{1},b_{1},a_{2},$ and $b_{2}$, we create
$N_{(a_{1},b_{1},a_{2},b_{2})}$ as follows. First, we delete all edges in
$E^{-}$ and all vertices in
$V(\mathcal{T})\setminus\\{a_{1},a_{2},b_{1},b_{2}\\}$ from $G$, and direct
each edge in $G$ in both directions. We then add new vertices $s^{\star}$ and
$t^{\star}$, along with arcs $(s^{\star},s)$ and $(s^{\star},t)$ of capacity
$2$, and arcs $(a_{i},t^{\star})$ and $(b_{i},t^{\star})$ for $i=1,2$ with
capacity 1.666In the degenerate case when $s=a_{1}=a_{2}$ or $t=b_{1}=b_{2}$
this yields two parallel arcs from $s$ or $t$ to $t^{\star}$.  We assign
capacity 1 to all other arcs, and also to each vertex of
$V(G)\setminus\\{s,t\\}$. All newly added arcs will have cost $0$, otherwise
we retain the cost function $w$. We let $s^{\star}$ and $t^{\star}$ be the
source and the sink in $N_{(a_{1},b_{1},a_{2},b_{2})}$, respectively.

Next, we compute two $(\\{a_{1},a_{2}\\},\\{b_{1},b_{2}\\})$-paths $Q_{1}$ and
$Q_{2}$ in $G$ with minimum total weight that are permissively disjoint. A
polynomial-time computation for this problem, building on structural
observations from Section 4.2, is provided in Section 4.3 (see Corollary 44).
Finally, we apply Lemma 10 (in fact, twice) to obtain a solution to our
instance $(G,w,s,t)$ based on a minimum-cost flow of value 4 in
$N_{(a_{1},b_{1},a_{2},b_{2})}$ and paths $Q_{1}$ and $Q_{2}$. We finish this
section with Lemma 21, stating the correctness of Step 3.

######  Lemma 21.

Suppose that $(P_{1},P_{2})$ is a minimum-weight solution for $(G,w,s,t)$ such
that

  * •

$P_{1}$ and $P_{2}$ are non-separable, and in contact at some
$T\in\mathcal{T}$,

  * •

$a_{i}$ and $b_{i}$ are the first and last vertices of $P_{i}$ contained in
$T$, respectively, for $i\in[2]$, and

  * •

$(\emptyset,\mathcal{T}\setminus\\{T\\},\emptyset)$ is a $T$-valid partition
w.r.t. $(P_{1},P_{2})$.

Let $Q_{1}$ and $Q_{2}$ be two permissively disjoint
$(\\{a_{1},a_{2}\\},\\{b_{1},b_{2}\\})$-paths in $G$ with minimum total
weight. Then the following holds:
If $w^{\star}$ is the minimum cost of a flow of value 4 in the network
$N_{(a_{1},b_{1},a_{2},b_{2})}$, then $w^{\star}+w(Q_{1})+w(Q_{2})\leq
w(P_{1})+w(P_{2})$. Conversely, given a flow of value 4 in the network
$N_{(a_{1},b_{1},a_{2},b_{2})}$ with cost $w^{\star}$, together with paths
$Q_{1}$ and $Q_{2}$, we can find a solution for $(G,w,s,t)$ with cost at most
$w^{\star}+w(Q_{1})+w(Q_{2})$ in linear time.

###### Proof.

Suppose that $(P_{1},P_{2})$ is a non-separable solution for our instance
fulfilling the conditions of the lemma, and $Q_{1}$ and $Q_{2}$ are two
permissively disjoint $(\\{a_{1},a_{2}\\},\\{b_{1},b_{2}\\})$-paths in $G$.
Clearly, $P_{1}[a_{1},b_{1}]$ and $P_{2}[a_{2},b_{2}]$ are permissively
disjoint, so we have

$w(Q_{1})+w(Q_{2})\leq w(P_{1}[a_{1},b_{1}])+w(P_{2}[a_{2},b_{2}]).$ (4)

The four paths $P_{i}[s,a_{i}]$ and $P_{i}[b_{i},t]$, $i\in[2]$, do not share
vertices other than $s$ and $t$, and since
$(\emptyset,\mathcal{T}\setminus\\{T\\},\emptyset)$ is a $T$-valid partition
w.r.t. $(P_{1},P_{2})$, we know that they do not contain any vertex of
$V(T)\setminus\\{a_{1},a_{2},b_{1},b_{2}\\}$ (recall condition (iii) of Lemma
9). Therefore, these four paths are present (as directed paths) in
$N_{(a_{1},b_{1},a_{2},b_{2})}$, and together with the arcs incident to
$s^{\star}$ and $t^{\star}$ yield a flow of value 4 in
$N_{(a_{1},b_{1},a_{2},b_{2})}$. This implies
$w^{\star}\leq\sum_{i\in[2]}w(P_{i}[s,a_{i}])+w(P_{i}[b_{i},t])$, which
together with (4) yields

$\displaystyle w^{\star}+w(Q_{1})+w(Q_{2})$
$\displaystyle\leq\sum_{i\in[2]}\bigg{(}w(P_{i}[s,a_{i}])+w(P_{i}[b_{i},t])\bigg{)}+w(P_{1}[a_{1},b_{1}])+w(P_{2}[a_{2},b_{2}])$
$\displaystyle=w(P_{1})+w(P_{2}),$

as required. This proves the first statement of the lemma.

For the other direction, we first show the following claim.

######  Claim 22.

$T[a_{1},b_{1}]$ and $T[a_{2},b_{2}]$ share at least one edge.

Proof: Suppose for the sake of contradiction that the claim does not hold.
Note that $T[a_{1},b_{1}]$ and $T[a_{2},b_{2}]$ may only share an endpoint if
$a_{1}=a_{2}=s$ or if $b_{1}=b_{2}=t$. Thus, if $T[a_{1},b_{1}]$ and
$T[a_{2},b_{2}]$ share no edge, then replacing the subpaths
$P_{1}[a_{1},b_{1}]$ and $P_{2}[a_{2},b_{2}]$ with $T[a_{1},b_{1}]$ and
$T[a_{2},b_{2}]$, respectively, yields a solution
$(P^{\prime}_{1},P^{\prime}_{2})$ for $(G,w,s,t)$. where
$P^{\prime}_{1}=P_{1}\setminus P_{1}[a_{1},b_{1}]\cup T[a_{1},b_{1}]$ and
$P^{\prime}_{2}=P_{1}\setminus P_{2}[a_{2},b_{2}]\cup T[a_{2},b_{2}]$. By
statement (1) of Lemma 3 we know that $w(P_{1}[a_{1},b_{1}])\geq
w(T[a_{1},b_{1}])$ and $w(P_{2}[a_{2},b_{2}])\geq w(T[a_{2},b_{2}])$, which
implies $w(P^{\prime}_{1})+w(P^{\prime}_{2})\leq w(P_{1})+w(P_{2})$. Since
$(P_{1},P_{2})$ is a minimum-weight solution for $(G,w,s,t)$, we know that
equality must hold. Using the last sentence in statement (1) of Lemma 3, this
implies $P_{1}[a_{1},b_{1}]\supseteq T[a_{1},b_{1}]$ and
$P_{2}[a_{2},b_{2}]\supseteq T[a_{2},b_{2}]$. As $P_{1}$ and $P_{2}$ are
paths, we immediately get $P_{1}[a_{1},b_{1}]=T[a_{1},b_{1}]$ and
$P_{2}[a_{2},b_{2}]=T[a_{2},b_{2}]$.

Recall that $(\emptyset,\mathcal{T}\setminus\\{T\\},\emptyset)$ is a $T$-valid
partition with respect to $(P_{1},P_{2})$. Thus, $P_{1}\cap
V(T^{\prime})=\emptyset$ for any
$T^{\prime}\in\mathcal{T}\setminus\\{\mathcal{T}\\}$ follows from
$P_{1}[a_{1},b_{1}]=T[a_{1},b_{1}]$ and $P_{2}[a_{2},b_{2}]=T[a_{2},b_{2}]$.
However, in this case $P_{1}$ and $P_{2}$ are separable, a contradiction
proving the claim. $\lhd$

Consider now a flow $f$ of value 4 in $N_{(a_{1},b_{1},a_{2},b_{2})}$. Let
$P^{f}_{s,1}$ and $P^{f}_{s,2}$ ($P^{f}_{t,1}$ and $P^{f}_{t,2}$) be the two
paths indicated by $f$ from $s$ (from $t$, respectively) to two vertices of
$\\{a_{1},b_{1},a_{2},b_{2}\\}$. Let $X=\mathcal{T}[a_{1},b_{1}]\cap
T[a_{2},b_{2}]$. If $a_{1}$ and $a_{2}$ are not in the same connected
component of $T\setminus X$, then switch the names of $a_{2}$ and $b_{2}$.
This way, we ensure that $a_{1}$ and $a_{2}$ are in the same connected
component of $T\setminus X$. In particular, $T[a_{1},a_{2}]$ and
$T[b_{1},b_{2}]$ share no edges. We now distinguish between two cases.

Case A: if the set of the endpoints of $P^{f}_{s,1}$ and $P^{f}_{s,2}$ is
$\\{s,a_{i},b_{j}\\}$ for some $i,j\in[2]$. Then, clearly, the set of
endpoints of $P^{f}_{t,1}$ and $P^{f}_{t,2}$ is $\\{t,a_{3-i},b_{3-j}\\}$.
Hence, the union of the paths $T[a_{1},a_{2}]$ and $T[b_{1},b_{2}]$ (using
only edges of $E(T)$) as well as the four paths $P^{f}_{s,i}$ and
$P^{f}_{t,i}$ for $i\in[2]$ (using only edges of $E(G)\setminus E^{-}$) yields
two openly disjoint $(s,t)$-paths $S_{1}$ and $S_{2}$. Moreover, by the second
statement of Lemma 3 we get

$w(S_{1})+w(S_{2})=w^{\star}+w(T[a_{1},a_{2}])+w(T[b_{1},b_{2}])\leq
w^{\star}+w(Q_{1})+w(Q_{2}).$

Note that the paths $S_{1}$ and $S_{2}$ can be computed in linear time, given
our flow of value 4. Hence, the second statement of the lemma holds in this
case.

Case B: if the set of the endpoints of $P^{f}_{s,1}$ and $P^{f}_{s,2}$ is
$\\{s,a_{1},a_{2}\\}$ (the case when the two paths starting from $s$ lead to
$b_{1}$ and $b_{2}$ is symmetric). Then the set of the endpoints of
$P^{f}_{t,1}$ and $P^{f}_{t,2}$ is $\\{t,b_{1},b_{2}\\}$. We need to apply
Lemma 10 twice.

First, if $a_{1}\neq a_{2}$, then we apply Lemma 10 for paths $P^{f}_{s,1}$,
$P^{f}_{s,2}$, $Q_{1}$ and $Q_{2}$, i.e., setting $s=p_{1}=p_{2}$,
$\\{v_{1},v_{2}\\}=\\{a_{1},a_{2}\\}$, $\\{q_{1},q_{2}\\}=\\{b_{1},b_{2}\\}$,
$\mathcal{T}_{1}=\emptyset$ and $\mathcal{T}_{2}=\mathcal{T}$. Note that the
conditions of Lemma 10 hold: by the definition of the network
$N_{(a_{1},b_{1},a_{2},b_{2})}$ we know that $P^{f}_{s,1}\cup P^{f}_{s,2}$
contains no edge of $E^{-}$ and no vertices of $T$ other than $a_{1}$ and
$a_{2}$; moreover, $Q_{1}$ and $Q_{2}$ are locally cheapest
$(\\{a_{1},a_{2}\\},\\{b_{1},b_{2}\\})$-paths, as they have minimum total
weight (recall Observation 5). Hence, we obtain in linear time two
permissively disjoint $(s,\\{b_{1},b_{2}\\})$-paths $Q^{\prime}_{1}$ and
$Q^{\prime}_{2}$ in $G$ whose weight is at most
$\sum_{i\in[2]}w(P^{f}_{s,i})+w(Q_{i})$. If $a_{1}=a_{2}$, then we also know
$s=a_{1}=a_{2}$, and thus $P^{f}_{s,1}$ and $P^{f}_{s,2}$ are paths of length
0. In this case we simply define $Q^{\prime}_{1}=Q_{1}$ and
$Q^{\prime}_{2}=Q_{2}$.

We next check whether $Q^{\prime}_{1}$ and $Q^{\prime}_{2}$ are locally
cheapest, and if not, we apply Observation 5 to compute
$\texttt{Amend}(Q^{\prime}_{1},Q^{\prime}_{2})$, obtaining two locally
cheapest, permissively disjoint $(s,\\{b_{1},b_{2}\\})$-paths
$Q^{\prime\prime}_{1}$ and $Q^{\prime\prime}_{2}$ with weight at most
$w(Q^{\prime}_{1})+w(Q^{\prime}_{2})$. By our remarks following Observation 5,
this can be done in linear time.

If $b_{1}\neq b_{2}$, then we apply Lemma 10 once again, for paths
$P^{f}_{t,1}$, $P^{f}_{t,2}$, $Q^{\prime\prime}_{1}$ and
$Q^{\prime\prime}_{2}$, i.e., setting $t=p_{1}=p_{2}$,
$\\{v_{1},v_{2}\\}=\\{b_{1},b_{2}\\}$, $s=q_{1}=q_{2}$,
$\mathcal{T}_{1}=\emptyset$ and $\mathcal{T}_{2}=\mathcal{T}$. Observe again
that the conditions of Lemma 10 hold: by the definition of the network
$N_{(a_{1},b_{1},a_{2},b_{2})}$ we know that $P^{f}_{t,1}\cup P^{f}_{t,2}$
contains no edge of $E^{-}$ and no vertices of $T$ other than $b_{1}$ and
$b_{2}$; moreover, $Q^{\prime\prime}_{1}$ and $Q^{\prime\prime}_{2}$ are
locally cheapest $(\\{b_{1},b_{2}\\},s)$-paths. Hence, we obtain in linear
time two permissively disjoint $(t,s)$-paths $S_{1}$ and $S_{2}$ in $G$ such
that

$\displaystyle w(S_{1})+w(S_{2})$
$\displaystyle\leq\sum_{i\in[2]}w(P^{f}_{t,i})+w(Q^{\prime\prime}_{i})\leq\sum_{i\in[2]}w(P^{f}_{t,i})+w(Q^{\prime}_{i})$
(5) $\displaystyle\leq\sum_{i\in[2]}w(P^{f}_{t,i})+w(Q_{i})+w(P^{f}_{s,i})$
$\displaystyle=w^{\star}+w(Q_{1})+w(Q_{2}).$

Thus, $S_{1}$ and $S_{2}$ form a solution for our instance of Shortest Two
Disjoint Paths with weight at most $w^{\star}+w(Q_{1})+w(Q_{2})$, as promised.

If $b_{1}=b_{2}$, then we also know $t=b_{1}=b_{2}$, and thus $P^{f}_{t,1}$
and $P^{f}_{t,2}$ are paths of length 0. In this case $Q^{\prime\prime}_{1}$
and $Q^{\prime\prime}_{2}$ are two permissively disjoint $(s,t)$-paths, so we
simply define $S_{1}=Q^{\prime\prime}_{1}$ and $S_{2}=Q^{\prime\prime}_{2}$.
Note that Inequality 5 still holds, and thus $S_{1}$ and $S_{2}$ form a
solution for $(G,w,s,t)$with weight at most $w^{\star}+w(Q_{1})+w(Q_{2})$ as
promised.

Note that applying Lemma 10 (twice) and amending all shortcuts in a pair of
paths can be performed in linear time. This finishes the proof of the lemma. ∎

###  4.2 Properties of a Non-separable Solution

Let us now turn our attention to the subroutine lying at the heart of our
algorithm for Shortest Two Disjoint Paths: an algorithm that, given two source
terminals and two sink terminals on some tree $T\in\mathcal{T}$, computes two
permissively disjoint paths from the two source terminals to the two sink
terminals, with minimum total weight. It is straightforward to see that any
non-separable solution whose paths are in contact at $T$ contains such a pair
of paths. Therefore, as described in Section 4.1.2, finding such paths is a
necessary step to computing an optimal, non-separable solution for our
instance $(G,w,s,t)$. This section contains observations about the properties
of such paths.

Let us now formalize our setting. Let $a_{1},a_{2},b_{1},$ and $b_{2}$ be
vertices on a fixed tree $T\in\mathcal{T}$ such that $T[a_{1},b_{1}]$ and
$T[a_{2},b_{2}]$ intersect in a path $X$ (with at least one edge), with one
component of $T\setminus X$ containing $a_{1}$ and $a_{2}$, and the other
containing $b_{1}$ and $b_{2}$. Let the vertices on $X$ be $x_{1},\dots,x_{r}$
with $x_{1}$ being the closest to $a_{1}$ and $a_{2}$. We will use the
notation $A_{i}=T[a_{i},x_{1}]$ and $B_{i}=T[b_{i},x_{r}]$ for each $i\in[2]$.
For each $i\in[r]$, let $T_{i}$ be the maximal subtree of $T$ containing
$x_{i}$ but no other vertex of $X$. We also define $T_{(i,j)}=\bigcup_{i\leq
h\leq j}T_{h}$ for some $i$ and $j$ with $1\leq i\leq j\leq r$.

For convenience, for any path $Q$ that has $a_{i}\in\\{a_{1},a_{2}\\}$ as its
endpoint, we will say that $Q$ _starts_ at $a_{i}$ and _ends_ at its other
endpoint. Accordingly, for vertices $u,v\in V(Q)$ we say that $u$ _precedes_
$v$ on $Q$, or equivalently, $v$ _follows_ $u$ on $Q$, if $u$ lies on
$Q[a_{i},v]$. When defining a vertex as the “first” (or “last”) vertex with
some property on $Q$ or on a subpath $Q^{\prime}$ of $Q$ then, unless
otherwise stated, we mean the vertex on $Q$ or on $Q^{\prime}$ that is closest
to $a_{i}$ (or farthest from $a_{i}$, respectively) that has the given
property.

We begin with the following observation about the paths $A_{1}$, $A_{2}$,
$B_{1}$, and $B_{2}$.

######  Lemma 23.

Let $Q_{1}$ and $Q_{2}$ be two permissively disjoint
$(\\{a_{1},a_{2}\\},\\{b_{1},b_{2}\\})$-paths in $G$ with minimum total
weight. For each $i\in[2]$, neither $V(A_{i})\setminus\\{x_{1}\\}$ nor
$V(B_{i})\setminus\\{x_{r}\\}$ can contain vertices both from $Q_{1}$ and
$Q_{2}$.

###### Proof.

W.l.o.g. we suppose $a_{i},b_{i}\in V(Q_{i})$ for $i\in[2]$. See Figure 2 for
an illustration of the proof. For the sake of contradiction, assume first that
there is a vertex on $A_{i}$ other than $x_{1}$ that is contained in
$Q_{3-i}$; by symmetry, we may also assume that $i=1$. Note that in this case
$a_{1}\neq a_{2}$. Let $z$ be the vertex of $Q_{2}$ that is closest to $a_{1}$
on $T[a_{1},x_{1}]$; then $V(T[a_{1},z])\cap V(Q_{2})=\\{z\\}$. Moreover, for
each vertex $z^{\prime}$ on $T[a_{1},z]$ that is on $Q_{1}$, we must have
$T[a_{1},z^{\prime}]\subseteq Q_{1}$, because $Q_{1}$ and $Q_{2}$ are locally
cheapest.

$a_{1}$$a_{2}$$b_{1}$$b_{2}$$z$$y$$x_{1}$$x_{r}$$A_{1}$$Q_{1}$$Q_{2}$ Figure
2: Illustration for the proof of Claim 27. Edges within $T$ are depicted using
solid lines, edges not in $T$ using dashed lines. Paths $Q_{1}$ and $Q_{2}$
are shown in blue and in green, respectively. We highlighted the closed walk
$W$ in coral red.

Since $z\in V(Q_{2})$ and $z$ is not on $T[a_{2},b_{2}]$, using that $Q_{1}$
and $Q_{2}$ are locally cheapest, we know that there exists a vertex of
$Q_{1}$ on $T[a_{2},b_{2}]$. Let $y$ be the vertex of $Q_{1}$ on
$T[a_{2},b_{2}]$ that is closest to $a_{2}$; then $V(T[a_{2},y])\cap
V(Q_{1})=\\{y\\}$. As before, for each vertex $y^{\prime}$ on $T[a_{2},y]$
that is on $Q_{2}$, we must have $T[a_{2},y^{\prime}]\subseteq Q_{2}$, because
$Q_{1}$ and $Q_{2}$ are locally cheapest.

These facts imply that $Q_{1}[y,b_{1}]$ shares no vertices with $T[a_{1},z]$,
and similarly, $Q_{2}[z,b_{2}]$ shares no vertices with $T[a_{2},y]$. Define
paths

$\displaystyle S_{1}$ $\displaystyle=T[a_{1},z]\cup Q_{2}[z,b_{2}],$
$\displaystyle S_{2}$ $\displaystyle=T[a_{2},y]\cup Q_{1}[y,b_{1}].$

Observe that $S_{1}$ and $S_{2}$ are permissively disjoint
$(\\{a_{1},a_{2}\\},\\{b_{1},b_{2}\\})$-paths due to the permissive
disjointness of $Q_{1}$ and $Q_{2}$, and our observation above.

Using statement (2) of Lemma 3 for paths $Q_{1}[a_{1},y]$ and
$Q_{2}[a_{2},z]$, we obtain

$\displaystyle w(S_{1})+w(S_{2})$
$\displaystyle=w(T[a_{1},z])+w(Q_{2}[z,b_{2}])+w(T[a_{2},y])+w(Q_{1}[y,b_{1}])$
$\displaystyle<w(Q_{1}[a_{1},y])+w(Q_{2}[a_{2},z])+w(Q_{2}[z,b_{2}])+w(Q_{1}[y,b_{1}])$
$\displaystyle=w(Q_{1})+w(Q_{2})$

where the inequality follows from the fact that $T[a_{1},y]$ and $T[a_{2},z]$
properly intersect each other (since both contain $x_{1}$). This contradicts
our definition of $Q_{1}$ and $Q_{2}$. Thus, for each $i\in[2]$, we have
proved that $Q_{1}$ and $Q_{2}$ cannot both contain vertices of
$V(A_{i})\setminus\\{x_{1}\\}$.

The second claim of the lemma follows by symmetry (i.e., by switching the
roles of $A_{i}$ and $B_{i}$ as well as that of $x_{1}$ and $x_{r}$). ∎

Using Lemmas 2, 3 and 23, we can establish the following properties of a non-
separable minimum-weight solution.

######  Definition 24 ($X$-monotone path).

A path $Q$ starting at $a_{1}$ or $a_{2}$ is _$X$ -monotone_ if for any
vertices $u_{1}$ and $u_{2}$ on $Q$ such that $u_{1}\in V(T_{j_{1}})$ and
$u_{2}\in V(T_{j_{2}})$ for some $j_{1}<j_{2}$ it holds that $u_{1}$ precedes
$u_{2}$ on $Q$.

######  Definition 25 (Plain path).

A path $Q$ is _plain_ , if whenever $Q$ contains some $x_{i}\in V(X)$, then
the vertices of $Q$ in $T_{i}$ induce a path in $T_{i}$. In other words, if
vertices $x_{j}\in V(X)$ and $u\in V(T_{j})$ both appear on $Q$, then
$T[u,x_{j}]\subseteq Q$.

######  Lemma 26.

Let $Q_{1}$ and $Q_{2}$ be two permissively disjoint
$(\\{a_{1},a_{2}\\},\\{b_{1},b_{2}\\})$-paths in $G$ with minimum total
weight. Then both $Q_{1}$ and $Q_{2}$ are $X$-monotone and plain.

###### Proof.

W.l.o.g. we suppose $a_{i},b_{i}\in V(Q_{i})$ for $i\in[2]$. First we prove
that $Q_{1}$ and $Q_{2}$ are $X$-monotone, and then prove their plainness.

######  Claim 27.

Both $Q_{1}$ and $Q_{2}$ are $X$-monotone.

Proof: For vertices $u_{1}\in V(T_{j_{1}})$ and $u_{2}\in V(T_{j_{2}})$ for
some indices $j_{1}<j_{2}$, we say that $(u_{1},u_{2})$ is a _reversed pair_ ,
if $u_{1}$ and $u_{2}$ both appear on $Q_{i}$ for some $i\in[2]$, but $u_{2}$
precedes $u_{1}$ on $Q_{i}$. The statement of the lemma is that no reversed
pair exists for $Q_{1}$ or $Q_{2}$. Assume the contrary, and choose $u_{1}$
and $u_{2}$ so that $u_{1}$ is as close to $x_{1}$ as possible (i.e., it
minimizes $|T[u_{1},x_{1}]|$), and subject to that, $u_{2}$ is as close to
$x_{r}$ as possible. By symmetry, we may assume that $u_{1}$ and $u_{2}$ are
both on $Q_{1}$. See Figure 3 for an illustration.

First note that $T[a_{1},u_{1}]\not\subseteq Q_{1}$ (because $u_{2}$ precedes
$u_{1}$), and therefore $T[a_{1},u_{1}]$ must contain a vertex of $Q_{2}$,
since $Q_{1}$ and $Q_{2}$ are locally cheapest. Let $v$ be a vertex on
$T[a_{1},u_{1}]$ closest to $u_{1}$ among those contained in $V(Q_{2})$.
Similarly, note that $T[u_{2},b_{1}]\not\subseteq Q_{2}$, and therefore
$T[u_{2},b_{1}]$ must contain a vertex of $Q_{2}$, since $Q_{1}$ and $Q_{2}$
are locally cheapest. Let $v^{\prime}$ be a vertex on $T[u_{2},b_{1}]$ closest
to $u_{2}$ among those contained in $V(Q_{1})$.

$a_{1}$$a_{2}$$b_{1}$$b_{2}$$u_{1}$$u_{2}$$v$$v^{\prime}$$x_{j_{1}}$$x_{j_{2}}$$x_{1}$$x_{r}$$Q_{1}$$Q_{2}$$W$
Figure 3: Illustration for the proof of Lemma 23. Edges within $T$ are
depicted using solid lines, edges not in $T$ using dashed lines. Paths $Q_{1}$
and $Q_{2}$ are shown in blue and in green, respectively. We highlighted paths
$T[a_{1},z]$ and $T[a_{2},y]$ in coral red.

By Lemma 23 we know that $v$ lies on $T[x_{1},u_{1}]$, and $v^{\prime}$ lies
on $T[u_{2},x_{r}]$. Note that no inner vertex of $T[v,u_{1}]$ is contained in
$V(Q_{2})$ by the definition of $v$. Let $e_{1}$ denote the edge
$T[x_{1},u_{1}]$ incident to $u_{1}$, and let $u^{\prime}_{1}$ be the other
endpoint of $e_{1}$. Observe that $e_{1}\in Q_{1}$ is not possible, because
then $(u^{\prime}_{1},u_{2})$ would also be a reversed pair, which would
contradict our choice of $(u_{1},u_{2})$ (since $u^{\prime}_{1}$ is closer to
$x_{1}$ than $u_{1}$). Using that $Q_{1}$ and $Q_{2}$ are locally cheapest, we
have that no inner vertex of $T[v,u_{1}]$ is contained in $V(Q_{1}\cup
Q_{2})$. Reasoning analogously, it also follows that no inner vertex of
$T[u_{2},v^{\prime}]$ is contained in $V(Q_{1}\cup Q_{2})$.

Note that $v\in V(T_{j})$ for some $j\leq j_{1}$, and $v^{\prime}\in
V(T_{j^{\prime}})$ for some $j^{\prime}\geq j_{2}$, implying $j<j^{\prime}$.
Moreover, $v$ is closer to $x_{1}$ than $u_{1}$. Hence, by our choice of
$(u_{1},u_{2})$, the pair $(v,v^{\prime})$ is not a reversed pair. This
implies that $v$ is on $Q_{2}[a_{2},v^{\prime}]$. In particular,
$Q_{2}[a_{2},v]$ and $Q_{2}[v^{\prime},b_{2}]$ are disjoint (because $v\neq
v^{\prime}$). Define paths

$\displaystyle S_{1}$ $\displaystyle=Q_{1}[a_{1},u_{2}]\cup
T[u_{2},v^{\prime}]\cup Q_{2}[v^{\prime},b_{2}],$ $\displaystyle S_{2}$
$\displaystyle=Q_{2}[a_{2},v]\cup T[v,u_{1}]\cup Q_{1}[u_{1},b_{1}].$

Observe that $S_{1}$ and $S_{2}$ are permissively disjoint
$(\\{a_{1},a_{2}\\},\\{b_{1},b_{2}\\})$-paths due to the permissive
disjointness of $Q_{1}$ and $Q_{2}$ and our observations on $T[v,u_{1}]$ and
$T[u_{2},v^{\prime}]$. Moreover, the walk

$W=T[v,u_{1}]\cup Q_{1}[u_{1},u_{2}]\cup T[u_{2},v^{\prime}]\cup
Q_{2}[v^{\prime},v]$

is closed and does not contain any edge of $E^{-}$ more than once, since
$Q_{1}$ and $Q_{2}$ share no edges, and no edge of $T[v,u_{1}]\cup
T[u_{2},v^{\prime}]$ is contained in $Q_{1}\cup Q_{2}$. Thus, $w(W)\geq 0$ by
Lemma 2. This implies

$\displaystyle\\!\\!w(S_{1})+w(S_{2})$
$\displaystyle=w(Q_{1})+w(Q_{2})-w(W\setminus(T[v,u_{1}]\cup
T[u_{2},v^{\prime}]))+w(T[v,u_{1}]\cup T[u_{2},v^{\prime}])$
$\displaystyle<w(Q_{1})+w(Q_{2}),$

because $w(T[v,u_{1}]\cup T[u_{2},v^{\prime}])<0$. This contradicts our
definition of $Q_{1}$ and $Q_{2}$. Hence, we have proved that no reversed pair
exists, and thus both $Q_{1}$ and $Q_{2}$ are $X$-monotone. $\lhd$

######  Claim 28.

Both $Q_{1}$ and $Q_{2}$ are plain.

Proof: Suppose for contradiction that $x_{j}\in V(Q_{1})$ and $u\in
V(Q_{1})\cap V(T_{j})$, but $T[u,x_{j}]\not\subseteq Q_{1}$; the case when $u$
and $x_{j}$ are on $Q_{2}$ is symmetric. Clearly, $u\neq x_{j}$. Since $Q_{1}$
and $Q_{2}$ are locally cheapest, by $T[u,x_{j}]\not\subseteq Q_{1}$ we know
that $T[u,x_{j}]$ must contain a vertex of $Q_{2}$.

Let $z$ be the closest vertex on $T[u,x_{j}]$ to $u$ that appears on $Q_{2}$,
and let $z^{\prime}$ be the closest vertex on $T[u,z]$ to $z$ that appears on
$Q_{1}$. Then no inner vertex of $T[z,z^{\prime}]$ contained in $V(Q_{1}\cup
Q_{2})$. Since $Q_{1}$ and $Q_{2}$ are locally cheapest, it follows from the
definition of $z$ and $z^{\prime}$ that $T[u,z^{\prime}]\subseteq Q_{1}$.

We now distinguish between two cases; see Figure 4 for an illustration.

Case
A:$a_{1}$$a_{2}$$b_{1}$$b_{2}$$u$$z$$z^{\prime}$$x_{h}$$x_{j}$$x_{1}$$x_{r}$$Q_{1}$$Q_{2}$$W$

Case
B:$a_{1}$$a_{2}$$b_{1}$$b_{2}$$u$$z$$z^{\prime}$$x_{h}$$x_{j}$$x_{1}$$x_{r}$$Q_{1}$$Q_{2}$$W$

Figure 4: Illustration for the proof of Claim 28. Edges within $T$ are
depicted using solid lines, edges not in $T$ using dashed lines. Paths $Q_{1}$
and $Q_{2}$ are shown in blue and in green, respectively. We highlighted the
closed walk $W$ in coral red.

Case A. First assume that $u$ precedes $x_{j}$ on $Q_{1}$. By
$T[u,z^{\prime}]\subseteq Q_{1}$ this implies that $z^{\prime}$ also precedes
$x_{j}$ on $Q_{1}$.

Using again that $Q_{1}$ and $Q_{2}$ are locally cheapest, by
$T[a_{1},x_{j}]\notin Q_{1}$ we know that $[Tx_{1},x_{j}]$ must contain a
vertex of $Q_{2}$. Let $x_{h}$ be the vertex on $T[x_{1},x_{j}]$ closest to
$x_{j}$. We show that neither $Q_{1}$ nor $Q_{2}$ contains an inner vertex of
$T[x_{h},x_{j}]$. For $Q_{2}$, this follows from the definition of $x_{h}$.
For $Q_{1}$, this follows from Claim 27 since $u$ precedes $x_{j}$ on $Q_{1}$,
the $X$-monotonicity of $Q_{1}$ implies that $Q_{1}$ enters $x_{j}$ through an
edge with both endpoints in $T_{j}$, so in particular, $x_{j}x_{j-1}\notin
Q_{1}$; using that $Q_{1}$ and $Q_{2}$ are locally cheapest, it follows that
$Q_{1}$ contains no inner vertices of $T[x_{h},x_{j}]$. By the
$X$-monotonicity of $Q_{2}$, we also know that $z$ follows $x_{h}$ on $Q_{2}$.

Define the paths

$\displaystyle S_{1}$ $\displaystyle=Q_{1}[a_{1},z^{\prime}]\cup
T[z^{\prime},z]\cup Q_{2}[z,b_{2}],$ $\displaystyle S_{2}$
$\displaystyle=Q_{2}[a_{2},x_{h}]\cup T[x_{h},x_{j}]\cup Q_{1}[x_{j},b_{1}].$

Observe that $S_{1}$ and $S_{2}$ are permissively disjoint
$(\\{a_{1},a_{2}\\},\\{b_{1},b_{2}\\})$-paths due to the permissive
disjointness of $Q_{1}$ and $Q_{2}$, and our observations on $T[z,z^{\prime}]$
and $T[x_{h},x_{j}]$. Moreover, the walk

$W=Q_{1}[z^{\prime},x_{j}]\cup T[x_{j},x_{h}]\cup Q_{2}[x_{h},z]\cup
T[z,z^{\prime}]$

is closed and does not contain any edge of $E^{-}$ more than once, since
$Q_{1}$ and $Q_{2}$ share no edges, and no edge of $T[z,z^{\prime}]\cup
T[x_{j},x_{h}]$ is contained in $Q_{1}\cup Q_{2}$. Thus, $w(W)\geq 0$ by Lemma
2. This implies

$\displaystyle\\!\\!w(S_{1})+w(S_{2})$
$\displaystyle=w(Q_{1})+w(Q_{2})-w(W\setminus(T[z,z^{\prime}]\cup
T[x_{j},x_{h}]))+w(T[z,z^{\prime}]\cup T[x_{j},x_{h}])$
$\displaystyle<w(Q_{1})+w(Q_{2}),$

because $w(T[z,z^{\prime}]\cup T[x_{j},x_{h}])<0$. This contradicts our
definition of $Q_{1}$ and $Q_{2}$.

Case B. Assume now that $u$ follows $x_{j}$ on $Q_{1}$; our reasoning is very
similar to the previous case. By $T[u,z^{\prime}]\subseteq Q_{1}$ this implies
that $z^{\prime}$ also follows $x_{j}$ on $Q_{1}$.

Using again that $Q_{1}$ and $Q_{2}$ are locally cheapest, by
$T[x_{j},b_{1}]\notin Q_{1}$ we know that $T[x_{j},x_{r}]$ must contain a
vertex of $Q_{2}$. Let $x_{h}$ be the vertex on $T[x_{j},x_{r}]$ closest to
$x_{j}$. We show that neither $Q_{1}$ nor $Q_{2}$ contains an inner vertex of
$T[x_{j},x_{h}]$. For $Q_{2}$, this follows from the definition of $x_{h}$.
For $Q_{1}$, this follows from Lemma 26 (implying $x_{j}x_{j+1}\notin Q_{1}$)
and the fact that $Q_{1}$ and $Q_{2}$ are locally cheapest. Note also that by
the $X$-monotonicity of $Q_{2}$, we know that $z$ precedes $x_{h}$ on $Q_{2}$.

Define the paths

$\displaystyle S_{1}$ $\displaystyle=Q_{1}[a_{1},x_{j}]\cup T[x_{j},x_{h}]\cup
Q_{2}[x_{h},b_{2}],$ $\displaystyle S_{2}$ $\displaystyle=Q_{2}[a_{2},z]\cup
T[z,z^{\prime}]\cup Q_{1}[z,b_{1}].$

Observe that $S_{1}$ and $S_{2}$ are permissively disjoint
$(\\{a_{1},a_{2}\\},\\{b_{1},b_{2}\\})$-paths due to the permissive
disjointness of $Q_{1}$ and $Q_{2}$, and our observations on $T[z^{\prime},z]$
and $T[x_{j},x_{h}]$. Moreover, the walk

$W=Q_{1}[x_{j},z^{\prime}]\cup T[z^{\prime},z]\cup Q_{2}[z,x_{h}]\cup
T[x_{h},x_{j}]$

is closed and does not contain any edge of $E^{-}$ more than once, since
$Q_{1}$ and $Q_{2}$ share no edges, and no edge of $T[z^{\prime},z]\cup
T[x_{h},x_{j}]$ is contained in $Q_{1}\cup Q_{2}$. Thus, $w(W)\geq 0$ by Lemma
2. This implies

$\displaystyle\\!\\!w(S_{1})+w(S_{2})$
$\displaystyle=w(Q_{1})+w(Q_{2})-w(W\setminus(T[z^{\prime},z]\cup
T[x_{h},x_{j}]))+w(T[z^{\prime},z]\cup T[x_{h},x_{j}])$
$\displaystyle<w(Q_{1})+w(Q_{2}),$

because $w(T[z,z^{\prime}]\cup T[x_{j},x_{h}])<0$. This contradicts our
definition of $Q_{1}$ and $Q_{2}$. $\lhd$ Having proved Claims 27 and 28,
Lemma 26 follows. ∎

The following observation summarizes our understanding on how an optimal
solution uses paths $A_{1}$, $A_{2}$, $B_{1}$, and $B_{2}$.

######  Lemma 29.

If $Q_{1}$ and $Q_{2}$ are two permissively disjoint
$(\\{a_{1},a_{2}\\},\\{b_{1},b_{2}\\})$-paths that are locally cheapest and
also plain, then one of them contains $A_{1}$ or $A_{2}$, and one of them
contains $B_{1}$ or $B_{2}$.

###### Proof.

W.l.o.g. we suppose $a_{i},b_{i}\in V(Q_{i})$ for $i\in[2]$. First, we show
that both $x_{1}$ and $x_{r}$ are contained in $Q_{1}\cup Q_{2}$. For each
$i\in[2]$, let $u_{i}$ denote the vertex closest to $x_{1}$ on $A_{i}$ that is
contained in $Q_{1}\cup Q_{2}$. Similarly, let $v_{i}$ denote the vertex
closest to $x_{r}$ on $B_{i}$ that is contained in $Q_{1}\cup Q_{2}$. If
$V(X)\cap V(Q_{1}\cup Q_{2})=\emptyset$, then $u_{1},u_{2},v_{1}$ and $v_{2}$
are four distinct vertices, with at least two of them belonging to the same
path $Q_{1}$ or $Q_{2}$, contradicting our assumption that $Q_{1}$ and $Q_{2}$
are locally cheapest. Consider the vertex $z$ of $V(X)\cap V(Q_{1}\cup Q_{2})$
closest to $x_{1}$ on $X$. If $x_{1}\notin V(Q_{1}\cup Q_{2})$, then
$u_{1},u_{2}$ and $z$ are three distinct vertices, so at least two of them
belong to the same path, $Q_{1}$ or $Q_{2}$ which contradicts our assumption
that $Q_{1}$ and $Q_{2}$ are locally cheapest. Hence, $x_{1}\in V(Q_{1}\cup
Q_{2})$, and an analogous argument shows $x_{r}\in V(Q_{1}\cup Q_{2})$.

Now, let $Q_{i}$ contain $x_{1}$. As $Q_{i}$ is plain and $a_{i}\in V(Q_{i})$
we get that $V(A_{i})\subseteq V(Q_{i})$. As $Q_{1}$ and $Q_{2}$ are locally
cheapest, we get that $A_{i}\subseteq Q_{i}$. The analogous argument shows
that $B_{i}$ is contained in $Q_{1}$ or $Q_{2}$. ∎

###  4.3 Computing Partial Solutions

In this section we design a dynamic programming algorithm that computes two
permissively disjoint $(\\{a_{1},a_{2}\\},\\{b_{1},b_{2}\\})$-paths of minimum
total weight (we keep all definitions introduced in Section 4.2, including our
assumptions on vertices $a_{1},b_{1},a_{2},$ and $b_{2}$). In Section 4.2 we
have established that two permissively disjoint
$(\\{a_{1},a_{2}\\},\\{b_{1},b_{2}\\})$-paths of minimum total weight are
necessarily $X$-monotone, plain, and they form a locally cheapest pair. A
natural approach would be to require these same properties from a partial
solution that we aim to compute. However, it turns out that the property of
$X$-monotonicity is quite hard to ensure when building subpaths of a solution.
The following relaxed version of monotonicity can be satisfied much easier,
and still suffices for our purposes:

######  Definition 30 (Quasi-monotone path).

A path $P$ starting at $a_{1}$ or $a_{2}$ is _quasi-monotone_ , if the
following holds: if $x_{i}\in V(P)$ for some $i\in[r]$, then all vertices in
$\bigcup_{h\in[i-1]}V(T_{h})\cap V(P)$ precede $x_{i}$ on $P$, and all
vertices in $\bigcup_{h\in[r]\setminus[i]}V(T_{h})\cap V(P)$ follow $x_{i}$ on
$P$.

######  Definition 31 (Well-formed path pair).

Two paths $P_{1}$ and $P_{2}$ form a _well-formed pair_ , if they are locally
cheapest, and both are plain and quasi-monotone.

We are now ready to define partial solutions, the central notion that our
dynamic programming algorithm relies on.

######  Definition 32 (Partial solution).

Given vertices $u\in V(T_{i})$ and $v\in V(T_{j})$ for some $i\leq j$ and a
set $\tau\subseteq\mathcal{T}\setminus\\{T\\}$, two paths $Q_{1}$ and $Q_{2}$
form a _partial solution $(Q_{1},Q_{2})$ for_ $(u,v,\tau)$, if

(a)

$Q_{1}$ and $Q_{2}$ are permissively disjoint
$(\\{a_{1},a_{2}\\},\\{u,v\\})$-paths;

(b)

$Q_{1}$ and $Q_{2}$ are a well-formed pair;

(c)

$Q_{1}$ ends with the subpath $T[x_{i},u]$;

(d)

$V(T_{(i+1,r)})\cap V(Q_{2})\subseteq\\{v\\}$;

(e)

if $Q_{1}\cup Q_{2}$ contains a vertex of some
$T^{\prime}\in\mathcal{T}\setminus\\{T\\}$, then $T^{\prime}\in\tau$;

(f)

there exists no tree $T^{\prime}\in\mathcal{T}\setminus\\{T\\}$ such that
$Q_{1}$ and $Q_{2}$ are in contact at $T^{\prime}$.

We will say that the vertices of $V(\mathcal{T}\setminus(\tau\cup\\{T\\}))$
are _forbidden_ for $(\tau,T)$; then condition (e) asks for $Q_{1}\cup Q_{2}$
not to contain vertices forbidden for $(\tau,T)$.

Before turning our attention to the problem of computing partial solutions,
let us first show how partial solutions enable us to find two permissively
disjoint $(\\{a_{1},a_{2}\\},\\{b_{1},b_{2}\\})$-paths.

######  Lemma 33.

Paths $P_{1}$ and $P_{2}$ are permissively disjoint
$(\\{a_{1},a_{2}\\},\\{b_{1},b_{2}\\})$-paths of minimum weight in $G$ if and
only if they form a partial solution for
$(b_{h},b_{3-h},\mathcal{T}\setminus\\{T\\})$ of minimum weight for some
$h\in[2]$.

###### Proof.

First assume that $P_{1}$ and $P_{2}$ are permissively disjoint
$(\\{a_{1},a_{2}\\},\\{b_{1},b_{2}\\})$-paths in $G$. By Lemma 29 we know that
one of them contains $B_{1}$ or $B_{2}$, so define $h$ such that
$B_{h}\subseteq P_{1}\cup P_{2}$. By Observation 5 and Lemmas26 we know that
$P_{1}$ and $P_{2}$ are a well-formed pair. Note also that condition (d) holds
vacuously, since $b_{1},b_{2}\in V(T_{r})$. Condition (e) holds trivially,
since there are no vertices forbidden for $(\mathcal{T}\setminus\\{T\\},T)$.
Therefore, if $P_{1}$ ends with $B_{h}$, then $(P_{1},P_{2})$ is a partial
solution for $(b_{h},b_{3-h},\mathcal{T})$, and if $P_{2}$ ends with $B_{h}$,
then $(P_{2},P_{1})$ is a partial solution for $(b_{h},b_{3-h},\mathcal{T})$.

Since a partial solution for $(b_{h},b_{3-h},\mathcal{T}\setminus\\{T\\})$ for
some $h\in[2]$ is by definition a pair of two permissively disjoint
$(\\{a_{1},a_{2}\\},\\{b_{1},b_{2}\\})$-paths, the lemma follows. ∎

We now present our approach for computing partial solutions using dynamic
programming.

##### Computing partial solutions: high-level view.

For each $u\in V(T_{i})$ and $v\in V(T_{j})$ for some $i\leq j$, and each
$\tau\subseteq\mathcal{T}\setminus\\{T\\}$, we are going to compute a partial
solution for $(u,v,\tau)$ of minimum weight, denoted by $F(u,v,\tau)$, using
dynamic programming; if there exists no partial solution for $(u,v,\tau)$, we
set $F(u,v,\tau)=\varnothing$.

To apply dynamic programming, we fix an ordering $\prec$ over $V(T)$
fulfilling the condition that for each $i^{\prime}<i$, $u\in V(T_{i})$ and
$u^{\prime}\in V(T_{i^{\prime}})$ we have $u^{\prime}\prec u$. We compute the
values $F(u,v,\tau)$ based on the ordering $\prec$ in the sense that
$F(u^{\prime},v^{\prime},\tau^{\prime})$ is computed before $F(u,v,\tau)$
whenever $u^{\prime}\prec u$. This computation is performed by Algorithm
PartSol which determines a partial solution $F(u,v,\tau)$ based on partial
solutions already computed.

To compute $F(u,v,\tau)$ in a recursive manner, we use an observation that
either the partial solution has a fairly simple structure, or it strictly
contains a partial solution for $(u^{\prime},v^{\prime},\tau^{\prime})$ for
some vertices $u^{\prime}$ and $v^{\prime}$ with $u^{\prime}\in
V(T_{i^{\prime}})$ and $i^{\prime}<i$, and some set
$\tau^{\prime}\subseteq\tau$. We can thus try all possible values for
$u^{\prime},v^{\prime}$ and $\tau^{\prime}$, and use the partial solution
$(Q^{\prime}_{1},Q^{\prime}_{2})$ we have already computed and stored in
$F(u^{\prime},v^{\prime},\tau^{\prime})$. To obtain a partial solution for
$(u,v,\tau)$ based on $Q^{\prime}_{1}$ and $Q^{\prime}_{2}$, we append paths
to $Q^{\prime}_{1}$ and to $Q^{\prime}_{2}$ so that they fulfill the
requirements of Definition 32 – most importantly, that $Q_{1}$ ends with
$T[x_{i},u]$, that $Q_{2}$ ends at $v$, and that $Q_{1}\cup Q_{2}$ contains no
vertex of $V(\mathcal{T}\setminus(\tau\cup\\{T\\}))$. To this end, we create a
path $P_{1}=Q^{\prime}_{2}\cup T[v^{\prime},u]$ and a path
$P_{2}=Q^{\prime}_{1}\cup R$ where $R$ is a shortest $(u^{\prime},v)$-path in
a certain auxiliary graph. Essentially, we use the tree $T$ for getting from
$v^{\prime}$ to $u$, and we use the “remainder” of the graph for getting from
$u^{\prime}$ to $v$; note that we need to avoid the forbidden vertices and
ensure condition (f) as well. The precise definition of the auxiliary subgraph
of $G$ that we use for this purpose is provided in Definition 34. If the
obtained path pair $(P_{1},P_{2})$ is indeed a partial solution for
$(u,v,\tau)$, then we store it. After trying all possible values for
$u^{\prime},v^{\prime},$ and $\tau^{\prime}$, we select a partial solution
that has minimum weight among those we computed.

######  Definition 34 (Auxiliary graph).

For some $T\in\mathcal{T}$, let $P\subseteq T$ be a path within $T$, let $u$
and $v$ be two vertices on $T$, and let
$\tau\subseteq\mathcal{T}\setminus\\{T\\}$. Then the _auxiliary graph_
$G\langle P,u,v,\tau\rangle$ denotes the graph defined as

$G\langle P,u,v,\tau\rangle=G-\left(\bigcup\\{V(T_{h}):V(T_{h})\cap
V(P)=\emptyset\\}\cup V(P)\setminus\\{u,v\\}\cup
V(\mathcal{T}\setminus(\tau\cup\\{T\\}))\right).$

In other words, we obtain $G\langle P,u,v,\tau\rangle$ from $G$ by deleting
all trees $T_{h}$ that do not intersect $P$, and deleting $P$ itself as well,
while taking care not to delete $u$ or $v$, and additionally deleting all
vertices forbidden for $(\tau,T)$.

Working towards a proof for the correctness of Algorithm PartSol, we start
with two simple observations. The first one, stated by Lemma 35 below,
essentially says that a path in a partial solution that uses a subtree $T_{h}$
of $T$ for some $h\in[r]$ should also go through the vertex $x_{h}$ whenever
possible, that is, unless the other path uses $x_{h}$.

######  Lemma 35.

Let $Q_{1}$ and $Q_{2}$ be two permissively disjoint, locally cheapest
$(\\{a_{1},a_{2}\\},\\{x_{i},v\\})$-paths for some $v\in V(T_{j})$ where
$1\leq i\leq j\leq r$. Let $z\in V(T_{h})$ for some $h\leq j$ such that $h<j$
or $x_{h}\in V(T[z,v])$. If $z\in V(Q_{1}\cup Q_{2})$, then $x_{h}\in
V(Q_{1}\cup Q_{2})$.

###### Proof.

W.l.o.g. we may assume $z\in V(Q_{1})$; let $a$ denote the starting vertex
($a_{1}$ or $a_{2}$) of $Q_{1}$. Suppose for contradiction that $x_{h}\notin
V(Q_{1}\cup Q_{2})$; then either $1\leq h<i$ or $i<h\leq j$. In the former
case, define $P_{1}$, $P_{2}$, and $P_{3}$ as the three openly disjoint paths
leading within $T$ from $x_{h}$ to $a$, to $x_{i}$, and to $z$, respectively.
In the latter case, define $P_{1}$, $P_{2}$, and $P_{3}$ as the three openly
disjoint paths leading within $T$ from $x_{h}$ to $x_{i}$, to $v$, and to $z$,
respectively; observe that such paths exist due to the condition that either
$h<j$ or $x_{h}\in V(T[z,v])$. Let $z_{1}$, $z_{2}$, and $z_{3}$ denote the
vertex closest to $x_{h}$ on $T_{1}$, $T_{2}$, and $T_{3}$, respectively, that
is contained in $V(Q_{1}\cup Q_{2})$; note that $z_{1}$, $z_{2}$ and $z_{3}$
are three distinct vertices, with no vertex of $V(Q_{1}\cup Q_{2})$ lying
between any two of them on $T$. Since at least two vertices from
$\\{z_{1},z_{2},z_{3}\\}$ belong to the same path $Q_{1}$ or $Q_{2}$, this
contradicts the assumption that $Q_{1}$ and $Q_{2}$ are locally cheapest. ∎

As a consequence of Lemma 35, applied with $a_{1}$ taking the role of $z$ and
$x_{1}$ taking the role of $x_{h}$, we get that every partial solution for
some $(u,v,\tau)$ must contain $x_{1}$; using that both paths in a partial
solution must be plain, we get the following fact.

######  Observation 36.

Let $(Q_{1},Q_{2})$ be a partial solution for $(u,v,\tau)$ for vertices $u\in
V(T_{i})$ and $v\in V(T_{j})$ for some $i\leq j$ and for
$\tau\subseteq\mathcal{T}\setminus\\{T\\}$. Then either $Q_{1}$ or $Q_{2}$
contains $A_{1}$ or $A_{2}$.

Let us now give some insight on Algorithm PartSol that computes a minimum-
weight partial solution $(Q_{1},Q_{2})$ for $(u,v,\tau)$, if it exists, for
vertices $u\in V(T_{i})$ and $v\in V(T_{j})$ with $i\leq j$ and trees
$\tau\subseteq\mathcal{T}\setminus\\{T\\}$. It distinguishes between two cases
based on whether $Q_{2}$ contains a vertex of $T[x_{1},x_{i}]$ or not. In both
cases it constructs candidates for a partial solution, and then chooses the
one among these with minimum weight.

Case A:

$Q_{2}$ does not contain any vertices from $T[x_{1},x_{i}]$. See Figure 5 for
an illustration. In this case, due to Observation 36, we know that $Q_{1}$
contains $A_{h}$ for some $h\in[2]$; let us fix this value of $h$. Since
$Q_{1}$ and $Q_{2}$ are locally cheapest and $Q_{1}$ ends with $T[x_{i},u]$,
we also know that $Q_{1}$ must contain $T[x_{1},x_{i}]$. Therefore, we obtain
$Q_{1}=A_{h}\cup T[x_{1},u]$. In this case, we can also prove that $Q_{2}$ is
a shortest $(a_{3-h},v)$-path in the auxiliary graph $G\langle A_{h}\cup
T[x_{1},u],a_{3-h},v,\tau\rangle$. Hence, Algorithm PartSol computes such a
path $R$ and constructs the pair $(A_{h}\cup T[x_{1},u],R)$ as a candidate for
a partial solution for $(u,v,\tau)$.

Case B:

$Q_{2}$ contains a vertex from $T[x_{1},x_{i}]$. See Figure 6 for an
illustration. In this case, let $x_{i^{\prime}}$ be the vertex on
$T[x_{1},x_{i-1}]$ closest to $x_{i}$ that appears on $Q_{2}$, and let
$u^{\prime}$ be the last vertex of $Q_{2}$ in $T_{i^{\prime}}$; since $Q_{2}$
is plain, we know $T[x_{i^{\prime}},u^{\prime}]\subseteq Q_{2}$. Let
$x_{j^{\prime}}$ denote the vertex on $T[x_{i^{\prime}},x_{i}]$ closest to
$x_{i^{\prime}}$ that appears on $Q_{1}$; then $i^{\prime}<j^{\prime}\leq i$.
As $Q_{1}$ and $Q_{2}$ are locally cheapest, $T[x_{j^{\prime}},x_{i}]\subseteq
Q_{1}$ follows. Let $v^{\prime}$ denote the first vertex of $Q_{1}$ in
$T_{j^{\prime}}$. Since $Q_{1}$ is plain, we know
$T[v^{\prime},x_{j^{\prime}}]\subseteq Q_{1}$.

Define $\widetilde{Q}_{1}=Q_{2}\setminus Q_{2}[u^{\prime},v]$ and
$\widetilde{Q}_{2}=Q_{1}\setminus Q_{1}[v^{\prime},u]$. Let also
$\tau^{\prime}$ denote those trees in $\mathcal{T}\setminus\\{T\\}$ that share
a vertex with $\widetilde{Q}_{1}\cup\widetilde{Q}_{2}$. We can then prove that
$(\widetilde{Q}_{1},\widetilde{Q}_{2})$ is a partial solution for
$(u^{\prime},v^{\prime},\tau^{\prime})$; moreover, $Q_{2}[u^{\prime},v]$ is a
path in the auxiliary graph $G\langle
T[v^{\prime},u],u^{\prime},v,\tau\setminus\tau^{\prime}\rangle$. Thus,
Algorithm PartSol takes a partial solution $(Q^{\prime}_{1},Q^{\prime}_{2})$
for $(u^{\prime},v^{\prime},\tau^{\prime})$, already computed, and computes a
shortest $(u^{\prime},v)$-path $R$ in $G\langle
T[v^{\prime},u],u^{\prime},v,\tau\setminus\tau^{\prime}\rangle$. It then
creates the path pair $(Q^{\prime}_{2}\cup T[v^{\prime},u],Q^{\prime}_{1}\cup
R)$ as a candidate for a partial solution for $(u,v,\tau)$.

Algorithm PartSol Computes a partial solution $F(u,v,\tau)$ of minimum weight
for $(u,v,\tau)$ where $u\in V(T_{i})$ and $v\in V(T_{j})$ with $i\leq j$, and
$\tau\subseteq\mathcal{T}\setminus\\{T\\}$.

1:Vertices $u$ and $v$ where $u\in V(T_{i})$ and $v\in V(T_{j})$ for some
$i\leq j$, and a set $\tau\subseteq\mathcal{T}\setminus\\{T\\}$.

2:A partial solution $F(u,v,\tau)$ for $(u,v,\tau)$ of minimum weight, or
$\varnothing$ if not existent.

3:Let $\mathcal{S}=\emptyset$.

4:for all $h\in[2]$ do

5: if $A_{h}\cup T[x_{1},u]$ is a path then

6: if $v$ is reachable from $a_{3-h}$ in $G\langle A_{h}\cup
T[x_{1},u],a_{3-h},v,\tau\rangle$ then

7: Compute a shortest $(a_{3-h},v)$-path $R$ in $G\langle A_{h}\cup
T[x_{1},u],u,a_{3-h},v,\tau\rangle$.

8: if $(A_{h}\cup T[x_{1},u],R)$ is a partial solution for $(u,v,\tau)$ then

9: $\mathcal{S}\leftarrow(A_{h}\cup T[x_{1},u],R)$.

10:for all $i^{\prime}\in[i-1]$ and $u^{\prime}\in V(T_{i^{\prime}})$ do

11: for all $j^{\prime}\in[i]\setminus[i^{\prime}]$ and $v^{\prime}\in
V(T_{j^{\prime}})$ such that $T[x_{j^{\prime}},v^{\prime}]\cap
T[x_{i},u]=\emptyset$ do

12: for all $\tau^{\prime}\subseteq\tau$ do

13: if $F(u^{\prime},v^{\prime},\tau^{\prime})=\varnothing$ then continue;

14: Let
$(Q^{\prime}_{1},Q^{\prime}_{2})=F(u^{\prime},v^{\prime},\tau^{\prime})$.

15: if $v$ is not reachable from $u^{\prime}$ in $G\langle
T[v^{\prime},u],u^{\prime},v,\tau\setminus\tau^{\prime}\rangle$ then continue;

16: Compute a shortest $(u^{\prime},v)$-path $R$ in $G\langle
T[v^{\prime},u],u^{\prime},v,\tau\setminus\tau^{\prime}\rangle$.

17: Let $P_{1}=Q^{\prime}_{2}\cup T[v^{\prime},u]$ and
$P_{2}=Q^{\prime}_{1}\cup R$.

18: if $(P_{1},P_{2})$ is a partial solution for $(u,v,\tau)$ then

19: $\mathcal{S}\leftarrow(P_{1},P_{2})$.

20:if $\mathcal{S}=\emptyset$ then return $\varnothing$.

21:else Let $S^{\star}$ be the cheapest pair among those in $\mathcal{S}$, and
return $F(u,v,\tau):=S^{\star}$.

The following lemma guarantees the correctness of Algorithm PartSol. Formally,
we say that $F(u,v,\tau)$ is _correctly computed_ if either it contains a
minimum-weight partial solution for $(u,v,\tau)$, or no partial solution for
$(u,v,\tau)$ exists and $F(u,v,\tau)=\varnothing$.

######  Lemma 37.

Let $i,j\in[r]$ with $i\leq j$, $u\in V(T_{i})$, $v\in V(T_{j})$ and
$\tau\subseteq\mathcal{T}\setminus\\{T\\}$. Assuming that the values
$F(u^{\prime},v^{\prime},\tau^{\prime})$ are correctly computed for each
$u^{\prime}\in V(T_{i^{\prime}})$ with $i^{\prime}<i$, Algorithm PartSol
correctly computes $F(u,v,\tau)$.

###### Proof.

Let $(Q_{1},Q_{2})$ be a partial solution for $(u,v,\tau)$ with minimum
weight. We distinguish between two cases.

$a_{1}$$a_{2}$$b_{1}$$b_{2}$$u$$v$$x_{i}$$x_{j}$$x_{1}$$x_{r}$$Q_{1}$$Q_{2}$
Figure 5: Illustration for Case A in Lemma 37. Edges within $T$ are depicted
using solid lines, edges not in $T$ using dashed lines. The figure assumes
$Q_{1}=A_{1}\cup T[x_{1},u]$ (so $h=1$). Paths $Q_{1}$ and $Q_{2}$ are shown
in blue and in green, respectively.

Case A: $Q_{2}$ contains no vertex of $T[x_{1},x_{i}]$. See Figure 5 for an
illustration. Due to Observation 36, we know that $Q_{1}$ contains $A_{h}$ for
some $h\in[2]$; let us fix this value of $h$. Since $Q_{1}$ and $Q_{2}$ are
locally cheapest and $Q_{1}$ ends with $T[x_{i},u]$, we also know that $Q_{1}$
must contain $T[x_{1},x_{i}]$. Therefore, we obtain $Q_{1}=A_{h}\cup
T[x_{1},u]$.

First, $Q_{1}$ and $Q_{2}$ may share a vertex only if $x_{1}=a_{1}=a_{2}$. We
also know that $Q_{2}$ may only contain vertices of $T_{(1,i)}$ that are not
on the path $A_{h}\cup T[x_{1},u]$, except possibly for the starting vertex
$a_{3-h}$ (in case $a_{1}=a_{2}$). Second, by condition (d) in the definition
of a partial solution, we also have that $Q_{2}$ contains no vertices from
$T_{h}$ for any $i<h\leq r$ other than its endpoint $v$. Third, by condition
(e) in the definition of a partial solution, we know that $Q_{1}\cup Q_{2}$
contains no vertex that is forbidden for $(\tau,T)$. This means that $Q_{2}$
is a path in the auxiliary graph $G\langle A_{h}\cup
T[x_{1},u],a_{3-h},v,\tau\rangle$.

Conversely, we claim that $(A_{h}\cup T[x_{1},u],R)$ is a partial solution for
$(u,v,\tau)$ for any shortest $(a_{3-h},v)$-path $R$ in $G\langle A_{h}\cup
T[x_{1},u],a_{3-h},v,\tau\rangle$, supposing that $A_{h}\cup T[x_{1},u]$ is an
$(a_{h},u)$-path; note that this condition is explicitly checked by the
algorithm (and trivial whenever $i>1$). By the definition of $G\langle
A_{h}\cup T[x_{1},u],a_{3-h},v,\tau\rangle$, we know that $A_{h}\cup
T[x_{1},u]$ and $R$ are two permissively disjoint
$(\\{a_{1},a_{2}\\},\\{u,v\\})$-paths.

Let us show that $A_{h}\cup T[x_{1},u]$ and $R$ are also locally cheapest:
assuming that there exists a shortcut $T[q,q^{\prime}]$ witnessing the
opposite, we get that both $q$ and $q^{\prime}$ must be vertices of $R$ on
$T_{(1,i)}$, and the path $T[q,q^{\prime}]$ must share no vertices with
$A_{h}\cup T[x_{1},u]$. Hence, replacing $R[q,q^{\prime}]$ with
$T[q,q^{\prime}]$ would yield a path in $G\langle A_{h}\cup
T[x_{1},u],a_{3-h},v\rangle$ whose weight is less than $w(R)$ by Lemma 3,
contradicting the fact that $R$ is a shortest path. Thus, $A_{h}\cup
T[x_{1},u]$ and $R$ are locally cheapest. They also form a well-formed pair,
since their quasi-monotonicity and plainness is obvious. It is straightforward
to see that they also satisfy conditions (c)–(f) in Definition 32, and thus
form a partial solution for $(u,v,\tau)$.

Therefore, for the right choice of $h$, Algorithm PartSol will put $(A_{h}\cup
T[x_{1},u],R)$ into $\mathcal{S}$ on line 9 where $R$ is a shortest
$(a_{3-h},v)$-path in $G\langle A_{h}\cup T[x_{1},u],a_{3-h},v,\tau\rangle$.
Observe that

$\displaystyle w(A_{h}\cup T[x_{1},u])+w(R)$ $\displaystyle=w(Q_{1})+w(R)\leq
w(Q_{1})+w(Q_{2}),$

implying that $(A_{h}\cup T[x_{1},u],R)$ is indeed a partial solution for
$(u,v,\tau)$ with minimum total weight. This proves the lemma for Case A.

Case B: $Q_{2}$ contains a vertex of $T[x_{1},x_{i}]$. Consider the vertex
$x_{i^{\prime}}$ on $T[x_{1},x_{i-1}]$ closest to $x_{i}$ that appears on
$Q_{2}$, and let $u^{\prime}$ be the last vertex of $Q_{2}$ in
$T_{i^{\prime}}$; since $Q_{2}$ is plain, we know
$T[x_{i^{\prime}},u^{\prime}]\subseteq Q_{2}$. Let $x_{j^{\prime}}$ denote the
vertex on $T[x_{i^{\prime}},x_{i}]$ closest to $x_{i^{\prime}}$ that is
contained in $Q_{1}$; then $i^{\prime}<j^{\prime}\leq i$. As $Q_{1}$ and
$Q_{2}$ are locally cheapest, we have $T[x_{j^{\prime}},x_{i}]\subseteq
Q_{1}$. Let $v^{\prime}$ denote the first vertex of $Q_{1}$ in
$T_{j^{\prime}}$. Since $Q_{1}$ is plain, we know
$T[v^{\prime},x_{j^{\prime}}]\subseteq Q_{1}$. Note also that
$T[x_{j^{\prime}},v^{\prime}]\cap T[x_{i},u]=\emptyset$: this is trivial if
$x_{j^{\prime}}\neq x_{i}$, and it follows from the plainness of $Q_{1}$ if
$x_{j^{\prime}}=x_{i}$, because then $T[v^{\prime},x_{j^{\prime}}]$ and
$T[x_{j^{\prime}},u]$ are both subpaths of $Q_{1}$ and therefore can share no
edge.

Let $\widetilde{Q}_{1}=Q_{2}\setminus Q_{2}[u^{\prime},v]$ and
$\widetilde{Q}_{2}=Q_{1}\setminus Q_{1}[v^{\prime},u]$. Let also
$\tau^{\prime}$ denote those trees in $\mathcal{T}\setminus\\{T\\}$ that share
a vertex with $\widetilde{Q}_{1}\cup\widetilde{Q}_{2}$.

$a_{1}$$a_{2}$$b_{1}$$b_{2}$$u$$v$$u^{\prime}$$v^{\prime}$$x_{i}$$x_{i^{\prime}}$$x_{j}$$x_{j^{\prime}}$$x_{1}$$\widetilde{Q}_{1}$$\widetilde{R}\subseteq
Q_{2}$$\widetilde{Q}_{2}$$Q_{1}$ Figure 6: Illustration for Case B in Lemma
37. Edges within $T$ are depicted using solid lines, edges not in $T$ using
dashed lines. Paths $Q_{1}$ and $Q_{2}$ are shown in blue and in green,
respectively. Their subpaths $\widetilde{Q}_{2}$ and $\widetilde{Q}_{1}$,
forming a partial solution for $(u^{\prime},v^{\prime},\tau^{\prime})$, are
depicted in bold, with their endings marked by a parenthesis-shaped delimiter.

######  Claim 38.

$(\widetilde{Q}_{1},\widetilde{Q}_{2})$ is a partial solution for
$(u^{\prime},v^{\prime},\tau^{\prime})$.

Proof: Observe that $\widetilde{Q}_{1}$ and $\widetilde{Q}_{2}$ are
permissively disjoint $(\\{a_{1},a_{2}\\},\\{u^{\prime},v^{\prime}\\})$-paths.
It is straightforward to verify that they form a well-formed pair and satisfy
condition (c) in the definition of partial solutions. Observe that neither
$Q_{1}$ nor $Q_{2}$ passes through an inner vertex of
$T[x_{i^{\prime}},x_{j^{\prime}}]$, by the definition of $x_{i^{\prime}}$ and
$x_{j^{\prime}}$. By Lemma 35 this implies that $V(\widetilde{Q}_{2})\cap
V(T_{h})=\emptyset$ for any $i^{\prime}<h<j^{\prime}$. Recall also that
$V(\widetilde{Q}_{2})\cap V(T_{j^{\prime}})=\\{v^{\prime}\\}$ by the
definition of $v^{\prime}$. Furthermore, since $Q_{1}$ is quasi-monotone, we
also have that $\widetilde{Q}_{2}$ contains no vertices from
$T_{(j^{\prime}+1,r)}$, so $\widetilde{Q}_{2}$ satisfies condition (d) as
well. By our definition of $\tau^{\prime}$, we also know that
$\widetilde{Q}_{1}\cup\widetilde{Q}_{2}$ contains no vertex of
$V(\mathcal{T}\setminus(\tau^{\prime}\cup\\{T\\})$, that is, no vertex that is
forbidden for $(\tau^{\prime},T)$. Since condition (f) holds for $Q_{1}$ and
$Q_{2}$, it also holds for their subpaths, $\widetilde{Q}_{1}$ and
$\widetilde{Q}_{2}$. Thus $(\widetilde{Q}_{1},\widetilde{Q}_{2})$ is a partial
solution for $(u^{\prime},v^{\prime},\tau^{\prime})$. $\lhd$

######  Claim 39.

$\widetilde{R}=Q_{2}[u^{\prime},v]$ is a $(u^{\prime},v)$-path in $G\langle
T[v^{\prime},u],u^{\prime},v,\tau\setminus\tau^{\prime}\rangle$.

Proof: First we show that $\widetilde{R}$ cannot contain any vertex that is
forbidden for $(\tau\setminus\tau^{\prime},T)$. For the sake of contradiction
assume that $\widetilde{R}$ contains some vertex $v_{f}$ forbidden for
$(\tau\setminus\tau^{\prime},T)$. By condition (e) in the definition of a
partial solution for $(u,v,\tau)$, we know that $Q_{1}\cup Q_{2}$ does not
contain vertices forbidden for $(\tau,T)$, and by $\widetilde{R}\subseteq
Q_{2}$, neither does $\widetilde{R}$. Note that the vertices that are
forbidden for $(\tau\setminus\tau^{\prime},T)$ but not for $(\tau^{\prime},T)$
are exactly the vertices

$\underbrace{V(\mathcal{T}\setminus(\tau\setminus\tau^{\prime}\cup\\{T\\}))}_{\textrm{forbidden
for
}(\tau\setminus\tau^{\prime},T)}\,\,\setminus\,\,\underbrace{V(\mathcal{T}\setminus(\tau\cup\\{T\\}))}_{\textrm{forbidden
for }(\tau,T)}=V(\tau^{\prime})$

Consequently, $v_{f}$ must be contained in $\tau^{\prime}$. Let $T^{\prime}$
be the negative tree in $\tau^{\prime}$ that contains $v_{f}$.

Recall that by the definition of $\tau^{\prime}$,
$\widetilde{Q}_{1}\cup\widetilde{Q}_{2}$ must contain a vertex of
$T^{\prime}$. In this case we can show that $Q_{1}$ contains a vertex of
$T^{\prime}$: if $V(\widetilde{Q}_{2})\cap V(T^{\prime})\neq\emptyset$, then
this follows from by $\widetilde{Q}_{2}\subseteq Q_{1}$; if
$V(\widetilde{Q}_{1})\cap V(T^{\prime})\neq\emptyset$, then by
$\widetilde{Q}_{1}=Q_{2}\setminus Q_{2}[u^{\prime},v]$ we get that $Q_{2}$
visits $T^{\prime}$ both before and after the vertex $u^{\prime}\in V(T)$, and
since $Q_{1}$ and $Q_{2}$ are locally cheapest, this implies that $Q_{1}$ must
contain a vertex of $T^{\prime}$. Hence, in either case we get that $Q_{1}$
and $Q_{2}$ are in contact at $T^{\prime}$, a contradiction to our assumption
that $(Q_{1},Q_{2})$ is a partial solution for $(u,v,\tau)$ and thus satisfies
condition (f). This proves that $\widetilde{R}$ contains no vertex forbidden
for $(\tau\setminus\tau^{\prime},T)$.

It is clear that $\widetilde{R}\subseteq Q_{2}$ has no common vertices with
$T[v^{\prime},u]\subseteq Q_{1}$ by the (permissive) disjointness of $Q_{1}$
and $Q_{2}$. Hence it suffices to prove the following: if $\widetilde{R}$
contains a vertex in $T_{\ell}$ other than $u^{\prime}$ or $v$, then
$j^{\prime}\leq\ell\leq i$. First, $\ell<i^{\prime}$ is not possible by the
quasi-monotonicity of $Q_{2}$ (using that $x_{i^{\prime}}$ is on $Q_{2}$).
Second, $\ell>i$ is also not possible, due to condition (d) for $Q_{2}$ in the
definition of a partial solution. Third, since $Q_{2}$ is plain, we get
$\ell\neq i^{\prime}$ from the definition of $u^{\prime}$. Fourth, recall that
neither $Q_{1}$ nor $Q_{2}$ passes through an inner vertex of
$T[x_{i^{\prime}},x_{j^{\prime}}]$, by the definition of $x_{i^{\prime}}$ and
$x_{j^{\prime}}$. Hence, by Lemma 35, no vertex of $Q_{1}$ or $Q_{2}$ can be
contained in $\bigcup_{i^{\prime}<h<j^{\prime}}V(T_{h})$, so $\ell$ is not
between $i^{\prime}$ and $j^{\prime}$. Thus, $j^{\prime}\leq\ell\leq i$ as
claimed, and so $\widetilde{R}$ is a path in $G\langle
T[v^{\prime},u],u^{\prime},v,\tau\setminus\tau^{\prime}\rangle$. $\lhd$

Consider the iteration when Algorithm PartSol picks the values for
$i^{\prime}$, $j^{\prime}$, $u^{\prime}$, $v^{\prime}$, and $\tau^{\prime}$ as
defined above (note that the condition on line 11 holds for these values); we
call this the _lucky_ iteration. In this iteration, the algorithm will find on
line 13 that $F(u^{\prime},v^{\prime},\tau^{\prime})\neq\varnothing$: by Claim
38 and our assumption that $F(u^{\prime},v^{\prime},\tau^{\prime})$ is already
correctly computed due to $i^{\prime}<i$, we know that
$F(u^{\prime},v^{\prime},\tau^{\prime})=(Q^{\prime}_{1},Q^{\prime}_{2})$ is a
partial solution for $(u^{\prime},v^{\prime},\tau^{\prime})$ with minimum
total weight. Moreover, by Claim 39 Algorithm PartSol will find on line 15
that $v$ is reachable from $u^{\prime}$ in $G\langle
T[v^{\prime},u],u^{\prime},v,\tau\setminus\tau^{\prime}\rangle$, and so the
algorithm will not continue with the next iteration but will proceed with
computing a pair $(P_{1},P_{2})$ where $P_{1}=Q^{\prime}_{2}\cup
T[v^{\prime},u]$ and $P_{2}=Q^{\prime}_{1}\cup R$ for some shortest
$(u^{\prime},v)$-path $R$ in $G\langle
T[v^{\prime},u],u^{\prime},v,\tau\setminus\tau^{\prime}\rangle$.

In the remainder of the proof we show that $(P_{1},P_{2})$ is a partial
solution for $(u,v,\tau)$, and moreover, its weight is at most
$w(Q_{1})+w(Q_{2})$. Clearly, this finishes the proof of the lemma for Case B.
We start with the following claim.

######  Claim 40.

$(P_{1},P_{2})$ satisfies conditions (b)–(f) of being a partial solution for
$(u,v,\tau)$.

Proof: Recall that $P_{1}=Q^{\prime}_{2}\cup T[v^{\prime},u]$ and
$P_{2}=Q^{\prime}_{1}\cup R$.

Observe that both $P_{1}$ and $P_{2}$ are plain and quasi-monotone by the
definitions. Let us show now that $(P_{1},P_{2})$ is a locally cheapest and,
hence, a well-formed pair. Suppose for contradiction that there is a shortcut
for $P_{1}$ and $P_{2}$, with endpoints $q$ and $q^{\prime}$. Since
$Q^{\prime}_{1}$ and $Q^{\prime}_{2}$ are locally cheapest, it follows that
$q$ and $q^{\prime}$ must lie on $R$. Note first that the auxiliary graph
$G\langle T[v^{\prime},u],u^{\prime},v,\tau\setminus\tau^{\prime}\rangle$ has
the property that for each $T^{\prime}\in\mathcal{T}\setminus\\{T\\}$ it
either contains $T^{\prime}$ as a subgraph, or contains no vertex of
$T^{\prime}$. Since $R$ is a shortest path in this graph, it follows that $R$
intersects each tree in $\mathcal{T}\setminus\\{T\\}$ in a path (if at all),
and hence any shortcut on $R$ must be within $T$, i.e., it has the form
$T[q,q^{\prime}]$. On the one hand, if $T[q,q^{\prime}]$ is contained in the
auxiliary graph $G\langle
T[v^{\prime},u],u^{\prime},v,\tau\setminus\tau^{\prime}\rangle$, then this
contradicts the optimality of $R$. On the other hand, if the auxiliary graph
does not contain $T[q,q^{\prime}]$ even though it contains both $q$ and
$q^{\prime}$, then $q$ and $q^{\prime}$ must be contained in different
components of $T_{(j^{\prime},i)}-V(T[v^{\prime},u])$: in this case, however,
by $T[v^{\prime},u]\subseteq P_{1}$ we obtain that there is a vertex of
$P_{1}$ on $T[q,q^{\prime}]$, contradicting our assumption that
$T[q,q^{\prime}]$ is a shortcut for $(P_{1},P_{2})$. This proves that
$(P_{1},P_{2})$ is a well-formed pair.

Note that condition (c) for being a partial solution for $(u,v,\tau)$ holds,
because $T[v^{\prime},x_{j^{\prime}}]\cap T[x_{i},u]=\emptyset$ is guaranteed
by the algorithm’s choice for $v^{\prime}$, and so we have
$T[x_{i},u]\subseteq T[v^{\prime},u]$. Condition (d) holds by the definition
of $G\langle T[v^{\prime},u],u^{\prime},v,\tau\setminus\tau^{\prime}\rangle$
and of $R$.

To see that $(P_{1},P_{2})$ satisfies condition (e), note that
$Q^{\prime}_{1}\cup Q^{\prime}_{2}$ contains no vertex that is forbidden for
$(\tau^{\prime},T)$, and $R$ contains no vertex that is forbidden for
$(\tau\setminus\tau^{\prime},T)$. Hence, neither of them contains a vertex
forbidden for $(\tau,T)$. Consequently, $P_{1}\cup P_{2}=Q^{\prime}_{2}\cup
T[v^{\prime},u]\cup Q^{\prime}_{1}\cup R$ does not contain vertices forbidden
for $(\tau,T)$, i.e., condition (e) holds for $(P_{1},P_{2})$.

Finally, let us show that condition (f) also holds for $(P_{1},P_{2})$.
Consider some $T^{\prime}\in\mathcal{T}\setminus\\{T\\}$. First, if
$T^{\prime}\notin\tau^{\prime}$, then the vertices of $T^{\prime}$ are
forbidden for $(\tau^{\prime},T)$ and hence cannot appear on
$Q^{\prime}_{1}\cup Q^{\prime}_{2}$. This implies $V(P_{1})\cap
V(T^{\prime})=\emptyset$, so $P_{1}$ and $P_{2}$ are certainly not in contact
at $T^{\prime}$. Second, if $T^{\prime}\in\tau^{\prime}$, then the vertices of
$T^{\prime}$ are forbidden for $(\tau\setminus\tau^{\prime},T)$ and hence
cannot appear on $R$, by the definition of $G\langle
T[v^{\prime},u],u^{\prime},v,\tau\setminus\tau^{\prime},\rangle$. Moreover,
since $(Q^{\prime}_{1},Q^{\prime}_{2})$ is a partial solution for
$(u^{\prime},v^{\prime},\tau^{\prime})$, we know that $Q^{\prime}_{1}$ and
$Q^{\prime}_{2}$ are not in contact at $T^{\prime}$, due to condition (f). By
$V(T^{\prime})\cap V(R)=\emptyset$, this implies that $P_{1}$ and $P_{2}$
cannot be in contact at $T^{\prime}$ either. This proves that $(P_{1},P_{2})$
satisfies condition (f). $\lhd$

By Claim 40, to show that $(P_{1},P_{2})$ is a partial solution for
$(u,v,\tau)$, it remains to prove that $P_{1}$ and $P_{2}$ are permissively
disjoint $(\\{a_{1},a_{2}\\},\\{u,v\\})$-paths. We show that this holds
whenever $R$ is vertex-disjoint from $Q^{\prime}_{1}\cup Q^{\prime}_{2}$, as
stated in Claim 41. Then we will prove in Claims 42 and 43, that this is
always the case.

######  Claim 41.

If $V(R)\cap V(Q^{\prime}_{1}\cup Q^{\prime}_{2})=\emptyset$, then
$(P_{1},P_{2})$ is a partial solution for $(u,v,\tau)$.

Proof: As a consequence of Claim 40, it remains to prove that $P_{1}$ and
$P_{2}$ are permissively disjoint $(\\{a_{1},a_{2}\\},\\{u,v\\})$-paths.

By definition, $Q^{\prime}_{1}$ and $Q^{\prime}_{2}$ are permissively disjoint
$(\\{a_{1},a_{2}\\},\\{u^{\prime},v^{\prime}\\})$-paths. Moreover, they do not
share any vertex with $T[v^{\prime},u]$ except for $v^{\prime}$: for
$Q^{\prime}_{1}$ this follows from its quasi-monotonicity and
$i^{\prime}<j^{\prime}$; for $Q^{\prime}_{2}$ this follows from condition (d)
on $Q^{\prime}_{2}$ for being a partial solution for
$(u^{\prime},v^{\prime}).$ Note that $R$ cannot share a vertex with
$T[v^{\prime},u]$ either, by the definition of $G\langle
T[v^{\prime},u],u^{\prime},v,\tau\setminus\tau^{\prime}\rangle$. Hence, our
assumption $V(R)\cap V(Q^{\prime}_{1}\cup Q^{\prime}_{2})=\emptyset$ implies
that $P_{1}$ and $P_{2}$ are permissively disjoint
$(\\{a_{1},a_{2}\\},\\{u,v\\})$-paths, as claimed. $\lhd$

Using Claims 38 and 39, the optimality of $(Q^{\prime}_{1},Q^{\prime}_{2})$
and that of $R$, we get

$\displaystyle\begin{split}w(Q_{1})+w(Q_{2})&=w(\widetilde{Q}_{2})+w(T[v^{\prime},u])+w(\widetilde{Q}_{1})+w(\widetilde{R})\\\
&\geq w(Q^{\prime}_{1})+w(Q^{\prime}_{2})+w(T[v^{\prime},u])+w(R)\geq
w(P_{1})+w(P_{2})\end{split}$ (6)