where the last inequality follows from the fact that $Q^{\prime}_{1}$,
$Q^{\prime}_{2}$, and $T[v^{\prime},u]$ are pairwise edge-disjoint, as we have
proved in Claim 41, and moreover, $R$ cannot share a negative-weight edge with
any of these four paths. This latter fact follows from our definition of the
auxiliary graph $G\langle
T[v^{\prime},u],u^{\prime},v,\tau\setminus\tau^{\prime}\rangle$, the quasi-
monotonicity of $Q^{\prime}_{1}$ and $Q^{\prime}_{2}$, and the fact that they
avoid vertices forbidden for $(\tau^{\prime},T)$; note that each vertex in
$V(\mathcal{T}\setminus\\{T\\})$ is either forbidden for $(\tau^{\prime},T)$,
or forbidden for $(\tau\setminus\tau^{\prime},T)$ (or both), so no edge of
$E(\mathcal{T}\setminus\\{T\\})$ can be shared by $R$ and $Q^{\prime}_{1}\cup
Q^{\prime}_{2}$.

It remains to show that $(P_{1},P_{2})$ is indeed a partial solution for
$(u,v,\tau)$; Inequality 6 then implies its optimality. By Claim 41, it
suffices to show that $R$ is vertex-disjoint from $Q^{\prime}_{1}\cup
Q^{\prime}_{2}$. To this end, we show in Claims 42 and 43 that assuming
otherwise contradicts the optimality of $(Q_{1},Q_{2})$.

Let $y$ be the vertex on $R$ closest to $v$ that is contained in
$Q^{\prime}_{1}\cup Q^{\prime}_{2}$, assuming that such a vertex exists.

######  Claim 42.

If $y\in V(Q^{\prime}_{1})$, then $(u,v,\tau)$ admits a partial solution of
weight less than $w(Q_{1})+w(Q_{2})$.

Proof: Define $P^{\prime}_{2}=P_{2}\setminus W$ for the closed walk
$W=Q^{\prime}_{1}[y,u^{\prime}]\cup R[u^{\prime},y]$; see Figure 7 for an
illustration. Note that $Q^{\prime}_{1}$ and $R$ cannot share vertices of $T$
other than $u^{\prime}$, because $Q^{\prime}_{1}$ contains no vertex of $T$
outside $T_{(1,i^{\prime})}$ due to its plainness and quasi-monotonicity, and
$R$ contains no vertex of $T$ outside $T_{(j^{\prime},i)}$ except for
$u^{\prime}$ and $v$, because $R$ is in $G\langle
T[v^{\prime},u],u^{\prime},v,\tau\setminus\tau^{\prime}\rangle$; from
$i^{\prime}<j^{\prime}$ thus follows $V(Q^{\prime}_{1})\cap V(R)\cap
V(T)=\\{u^{\prime}\\}$. Therefore, $W$ does not contain any edge of $T$ more
than once.

It is also clear that $W$ does not contain any edge of
$E(\mathcal{T}\setminus\\{T\\})$ more than once: if some
$T^{\prime}\in\mathcal{T}\setminus\\{T\\}$ shares an edge with
$Q^{\prime}_{1}$, then $T^{\prime}\in\tau^{\prime}$ holds by condition (e) for
$(Q^{\prime}_{1},Q^{\prime}_{2})$ being a partial solution for
$(u^{\prime},v^{\prime},\tau^{\prime})$; however, then the vertices of
$T^{\prime}$ are forbidden for $(\tau\setminus\tau^{\prime},T)$ and hence
cannot be contained in $R$. This implies that $W$ has non-negative weight by
Lemma 2. Using Inequality 6 this implies

$\displaystyle w(P_{1})+w(P^{\prime}_{2})$
$\displaystyle=w(P_{1})+w(P_{2})-w(W)\leq w(P_{1})+w(P_{2})\leq
w(Q_{1})+w(Q_{2}).$ (7)

$a_{1}$$a_{2}$$b_{1}$$b_{2}$$u$$v$$u^{\prime}$$v^{\prime}$$x_{\ell}$$x_{\ell^{\prime}}$$x_{i}$$x_{i^{\prime}}$$x_{j}$$x_{j^{\prime}}$$x_{1}$$Q^{\prime}_{1}$$y$$W$$R[u^{\prime},y]$$R[y,v]$$Q^{\prime}_{2}$$P_{1}$$P^{\prime}_{2}$
Figure 7: Illustration for Claim 42. Paths $P_{1}$ and $P_{2}$ are shown in
blue and in green, respectively. Their subpaths $Q^{\prime}_{2}$ and
$Q^{\prime}_{1}$ are depicted in bold, with their endings marked by a
parenthesis-shaped delimiter. We highlighted the closed walk $W$ in coral red,
and path $P^{\prime}_{2}$ in purple.

It is clear by our choice of $y$ that $R[y,v]$ shares no vertices with
$Q^{\prime}_{1}$ or $Q^{\prime}_{2}$. Using the same arguments as in the proof
of Claim 41, we obtain that $P^{\prime}_{1}$ and $P_{2}$ are permissively
disjoint $(\\{a_{1},a_{2}\\},\\{u,v\\})$-paths. It is also clear that they
satisfy conditions (c)–(f) of being a partial solution for $(u,v,\tau)$, and
that $P_{1}$ is plain and quasi-monotone. To see that $P^{\prime}_{2}$ is also
plain and quasi-monotone, recall that $y$ cannot be on $T$. Since
$P^{\prime}_{2}$ is obtained by deleting the subpath of $Q^{\prime}_{1}$
starting at $y$, and then appending a subpath of $R$ (not containing any
vertex of $X$) it follows that $P^{\prime}_{2}$ is quasi-monotone and plain.

Therefore, $(P_{1},P^{\prime}_{2})$ satisfies all conditions for being a
partial solution for $(u,v,\tau)$, except the condition of being locally
cheapest.

We are going to show that $(P_{1},P^{\prime}_{2})$ is _not_ locally cheapest,
but $\texttt{Amend}(P_{1},P^{\prime}_{2})$ is a partial solution for
$(u,v,\tau)$. Observe that this suffices to prove the claim: if
$(P_{1},P^{\prime}_{2})$ is _not_ locally cheapest, then by Observation 5 and
Inequality 7 we get that $\texttt{Amend}(P_{1},P^{\prime}_{2})$ has weight
less than $w(P_{1})+w(P^{\prime}_{2})\leq w(Q_{1})+w(Q_{2})$.

By Claim 40, we know that $P_{1}$ and $P_{2}$ are not in contact at any tree
of $\mathcal{T}$ other than $T$, so any shortcut for $(P_{1},P^{\prime}_{2})$
must be on $T$. Recall also that $P_{1}$ and $P_{2}$ are locally cheapest,
again by Claim 40. Hence, any shortcut for $(P_{1},P^{\prime}_{2})$ must be
the result of deleting the closed walk $W=Q^{\prime}_{1}[y,u^{\prime}]\cup
R[u^{\prime},y]\subseteq P_{2}$. This means that if $T[q,q^{\prime}]$ is a
shortcut for $(P_{1},P^{\prime}_{2})$, then $T[q,q^{\prime}]$ contains an
inner vertex $\hat{q}\in V(W)$. In addition, note that $\hat{q}$ cannot be on
$R$ unless $\hat{q}=u^{\prime}$: since $V(P_{1})\cap
V(T_{(j^{\prime},i)})=V(T[v^{\prime},u])$, we know that $P_{1}$ contains no
two vertices that may be separated on $T$ by any vertex of
$T_{(j^{\prime},i)}$. Hence, any shortcut for $(P_{1},P^{\prime}_{2})$ is of
the form $T[q,q^{\prime}]$ where $q$ and $q^{\prime}$ are on $P_{1}$, and
$T[q,q^{\prime}]$ contains a vertex $\hat{q}\in
V(Q^{\prime}_{1}[y,u^{\prime}])$.

Let
$(\widetilde{P}_{1},\widetilde{P}_{2})=\texttt{Amend}(P_{1},P^{\prime}_{2})$.
By the above arguments we have
$\widetilde{P}_{2}=P^{\prime}_{2}=Q^{\prime}_{1}\cup R\setminus W$. Observe
that by amending shortcuts we cannot violate permissive disjointness, and it
is easy to see that conditions (c)–(f) remain true as well. Moreover, after
amending all shortcuts, the resulting pair of paths must be locally cheapest.
Recall that we already proved that $\widetilde{P}_{2}=P^{\prime}_{2}$ is plain
and quasi-monotone. Hence, to prove that
$(\widetilde{P}_{1},\widetilde{P}_{2})$ is a partial solution for $(u,v,\tau)$
it suffices to check the plainness and quasi-monotonicity of
$\widetilde{P}_{1}$.

Let $x_{\ell}$ be the first vertex on $Q^{\prime}_{1}$ after $y$ that is on
$X$. By $y\notin V(T)$ we know that $Q^{\prime}_{1}$ does not contain
$T[x_{1},x_{\ell}]$, and since $Q^{\prime}_{1}$ and $Q^{\prime}_{2}$ are
locally cheapest, $T[x_{1},x_{\ell}]$ must contain a vertex of
$Q^{\prime}_{2}$. Let $x_{\ell^{\prime}}$ denote the vertex on
$T[x_{1},x_{\ell}]$ closest to $x_{\ell}$ that belongs to $Q^{\prime}_{2}$. We
claim that $\widetilde{P}_{1}=Q^{\prime}_{2}\setminus
Q^{\prime}_{2}[x_{\ell^{\prime}},x_{j^{\prime}}]\cup
T[x_{\ell^{\prime}},x_{j^{\prime}}]$. To see this, note that the deletion of
the vertices of $Q^{\prime}_{1}[x_{\ell},u^{\prime}]$ removes all vertices of
$Q^{\prime}_{1}$ from $T[x_{\ell^{\prime}},x_{j^{\prime}}]$; these vertices
(weakly) follow $x_{\ell}$ on $Q^{\prime}_{1}$ by its quasi-monotonicity.
Hence, as $x_{\ell^{\prime}}$ and $x_{j^{\prime}}$ are both on
$Q^{\prime}_{2}$, we obtain
$T[x_{\ell^{\prime}},x_{j^{\prime}}]\subseteq\widetilde{P}_{1}$. Observe also
that if a vertex $z$ of $Q^{\prime}_{1}[y,x_{\ell}]$ is contained in some
$T_{h}$ with $h<\ell$, then $x_{h}\in V(Q^{\prime}_{1}\cup Q^{\prime}_{2})$ by
Lemma 35, which implies $x_{h}\in V(Q^{\prime}_{2})$ by the definition of
$x_{\ell}$, and thus we get $h\leq\ell^{\prime}$ from the definition of
$x_{\ell^{\prime}}$. However, then the removal of $z$ from $Q^{\prime}_{1}$
cannot result in a shortcut, since $Q^{\prime}_{2}$ is plain and thus its
intersection with $T_{h}$ is a path. Therefore,
$\widetilde{P}_{1}=Q^{\prime}_{2}\setminus
Q^{\prime}_{2}[x_{\ell^{\prime}},x_{j^{\prime}}]\cup
T[x_{\ell^{\prime}},x_{j^{\prime}}]$ indeed holds. As a consequence, the
plainness and quasi-monotonicity of $P_{1}$ immediately implies that
$\widetilde{P}_{1}$ is plain and quasi-monotone as well. Hence,
$(\widetilde{P}_{1},\widetilde{P}_{2})$ is a partial solution for
$(u,v,\tau)$.

To see that $(P_{1},P^{\prime}_{2})$ is not locally cheapest, observe that at
least one shortcut is created when deleting $W$: we know that
$T[x_{\ell^{\prime}},x_{j^{\prime}}]\subseteq\widetilde{P}_{1}$, but
$x_{i^{\prime}}$ lies on the path $T[x_{\ell^{\prime}},x_{j^{\prime}}]$ and is
a vertex of $W$. Hence
$w(\widetilde{P}_{1})+w(\widetilde{P}_{2})<w(P_{1})+w(P_{2})\leq
w(Q_{1})+w(Q_{2})$. $\lhd$

The proof of Claim 43 is similar to the proof of Claim 42, but it is not
entirely symmetric.

######  Claim 43.

If $y\in V(Q^{\prime}_{2})$, then $(u,v,\tau)$ admits a partial solution of
weight less than $w(Q_{1})+w(Q_{2})$.

Proof: Define $P^{\prime}_{1}=Q^{\prime}_{1}\setminus
T[x_{i^{\prime}},u^{\prime}]\cup T[x_{i^{\prime}},u]$ and
$P^{\prime}_{2}=Q^{\prime}_{2}\setminus Q^{\prime}_{2}[y,v^{\prime}]\cup
R[y,v]$, and consider the closed walk

$W=R[u^{\prime},y]\cup Q^{\prime}_{2}[y,v^{\prime}]\cup
T[u^{\prime},v^{\prime}].$

See Figure 8 for an illustration. We argue that $W$ does not contain any edge
of $T$ more than once. First, by the definition of $G\langle
T[v^{\prime},u],u^{\prime},v,\tau\setminus\tau^{\prime}\rangle$ we know that
any vertex of $T$ contained in the path $R$ belongs to $T_{(j^{\prime},i)}$,
but not to $T[v^{\prime},u]$. Hence, $R$ shares no edges with
$T[u^{\prime},v^{\prime}]$. Condition (d) for $Q^{\prime}_{2}$ being a partial
solution for $(u^{\prime},v^{\prime},\tau^{\prime})$ requires
$V(T_{(i^{\prime}+1,r)})\cap V(Q^{\prime}_{2})\subseteq\\{v^{\prime}\\}$. This
shows that $Q^{\prime}_{2}$ cannot share an edge of $T$ with $R$ or with
$T[x_{i^{\prime}},v^{\prime}]$; note that $y\notin V(T)$ also follows. Lastly,
$Q^{\prime}_{2}[y,v^{\prime}]$ shares no edge of $T$ with
$T[u^{\prime},x_{i^{\prime}}]$ by the (permissive) disjointness of
$Q^{\prime}_{1}$ and $Q^{\prime}_{2}$.

It is also clear that $W$ does not contain any edge of
$E(\mathcal{T}\setminus\\{T\\})$ more than once: if some
$T^{\prime}\in\mathcal{T}\setminus\\{T\\}$ shares an edge with
$Q^{\prime}_{2}$, then $T^{\prime}\in\tau^{\prime}$ holds by condition (e) for
$(Q^{\prime}_{1},Q^{\prime}_{2})$ being a partial solution for
$(u^{\prime},v^{\prime},\tau^{\prime})$; however, then the vertices of
$T^{\prime}$ are forbidden for $(\tau\setminus\tau^{\prime},T)$ and hence
cannot be contained in $R$. Therefore, by Lemma 2 we know $w(W)\geq 0$. By
Inequality 6 this implies

$\displaystyle w(P^{\prime}_{1})+w(P^{\prime}_{2})$
$\displaystyle=w(P_{1})+w(P_{2})-w(T[x_{i^{\prime}},u^{\prime}]\cup
R[u^{\prime},y]\cup Q^{\prime}_{2}[y,v^{\prime}]\cup
T[v^{\prime},x_{j^{\prime}}])$
$\displaystyle\phantom{=,}+w(T[x_{i^{\prime}},v^{\prime}])$
$\displaystyle=w(P_{1})+w(P_{2})-w(W\setminus
T[x_{i^{\prime}},x_{j^{\prime}}])+w(T[x_{i^{\prime}},x_{j^{\prime}}])$
$\displaystyle<w(P_{1})+w(P_{2})\leq w(Q_{1})+w(Q_{2}).$ (8)

$a_{1}$$a_{2}$$b_{1}$$b_{2}$$u$$v$$u^{\prime}$$v^{\prime}$$x_{\ell}$$x_{\ell^{\prime}}$$x_{i}$$x_{i^{\prime}}$$x_{j}$$x_{j^{\prime}}$$x_{1}$$y$$Q^{\prime}_{1}$$R$$P^{\prime}_{1}$$P^{\prime}_{2}$$W$$Q^{\prime}_{2}$$P_{1}$
Figure 8: Illustration for Claim 43. Paths $P_{1}$ and $P_{2}$ are shown in
blue and in green, respectively, and their subpaths $Q^{\prime}_{2}$ and
$Q^{\prime}_{1}$ are depicted in bold, with their endings marked by a
parenthesis-shaped delimiter. Paths $P^{\prime}_{1}$ and $P^{\prime}_{2}$ are
shown both in purple, and we highlighted the closed walk $W$ in coral red.

It is clear by our choice of $y$ that $R[y,v]$ shares no vertices with
$Q^{\prime}_{1}$ or $Q^{\prime}_{2}$. Using the same arguments as in the proof
of Claim 41, we obtain that $P^{\prime}_{1}$ and $P^{\prime}_{2}$ are
permissively disjoint $(\\{a_{1},a_{2}\\},\\{u,v\\})$-paths. It is also clear
that they satisfy conditions (c)–(f), and that both $P^{\prime}_{1}$ and
$P^{\prime}_{2}$ are plain and quasi-monotone. Therefore,
$(P^{\prime}_{1},P^{\prime}_{2})$ satisfies all conditions for being a partial
solution for $(u,v,\tau)$, except for the condition of being locally cheapest.

We are going to show that $\texttt{Amend}(P^{\prime}_{1},P^{\prime}_{2})$ is a
partial solution for $(u,v,\tau)$. Observe that this suffices to prove the
claim, as by Observation 5 and Inequality 8,
$\texttt{Amend}(P^{\prime}_{1},P^{\prime}_{2})$ has weight at most
$w(P^{\prime}_{1})+w(P^{\prime}_{2})<w(Q_{1})+w(Q_{2})$.

By Claim 40, we know that $P_{1}$ and $P_{2}$ are not in contact at any tree
of $\mathcal{T}$ other than $T$, so any shortcut for
$(P^{\prime}_{1},P^{\prime}_{2})$ must be on $T$. Let
$(\widetilde{P}_{1},\widetilde{P}_{2})=\texttt{Amend}(P^{\prime}_{1},P^{\prime}_{2})$.
Observe that by amending shortcuts we cannot violate permissive disjointness,
and it is obvious that conditions (c)–(f) remain true as well. Moreover, after
amending all shortcuts, the resulting pair of paths must be locally cheapest.
Hence, to prove that $(\widetilde{P}_{1},\widetilde{P}_{2})$ is a partial
solution for $(u,v,\tau)$ it suffices to check the plainness and quasi-
monotonicity of $\widetilde{P}_{1}$ and $\widetilde{P}_{2}$.

Suppose for contradiction that the condition of plainness or quasi-
monotonicity is violated for $\widetilde{P}_{h}$ for some $h\in[2]$ at some
vertex $x_{k}$; by the definition of these properties (see Definitions 25 and
30) we have $x_{k}\in V(\widetilde{P}_{h})$. If $x_{k}$ is also contained in
$P^{\prime}_{h}$, then exactly by the plainness and quasi-monotonicity of
$P^{\prime}_{1}$ and $P^{\prime}_{2}$, these properties will not get violated
at $x_{k}$ when amending shortcuts. Hence, $x_{k}\notin V(P^{\prime}_{h})$ and
thus must be contained in a shortcut for $(P^{\prime}_{1},P^{\prime}_{2})$.
Since $P^{\prime}_{1}$ ends with $T[x_{i^{\prime}},u]$, we have that
$\widetilde{P}_{1}$ must also end with $T[x_{i^{\prime}},u]$; therefore,
$x_{k}\notin V(T[x_{i^{\prime}},x_{i}])$. Note that $k>i$ is not possible
either, since $R$ and thus $P^{\prime}_{2}$ contains no vertex of
$T_{(i+1,r)}$ other than $v$. Thus, we get $k<i^{\prime}$.

Note that $x_{k}$ cannot be contained in a shortcut that results from the
deletion of $R[y,u^{\prime}]\cup T[u^{\prime},x_{i^{\prime}}]$, since such
shortcuts cannot contain a vertex of $T_{(1,i^{\prime}-1)}$. Consequently,
$x_{k}$ is contained in a shortcut resulting from the deletion of
$Q^{\prime}_{2}[y,v^{\prime}]$; it also follows that the two endpoints of such
a shortcut must lie on $Q^{\prime}_{1}$. In particular, $x_{k}$ is a vertex of
$\widetilde{P}_{1}$ not contained in $P^{\prime}_{1}$. Since $Q^{\prime}_{1}$
and $Q^{\prime}_{2}$ are locally cheapest and plain, we get that
$Q^{\prime}_{2}[y,v^{\prime}]$ must contain a vertex of
$T[x_{1},x_{i^{\prime}-1}]$.

Let $x_{\ell}$ be the first vertex on $Q^{\prime}_{2}$ after $y$ that is on
$X$ (by our previous sentence, such a vertex exists). By $y\notin V(T)$ we
know that $Q^{\prime}_{2}$ does not contain $T[x_{1},x_{\ell}]$, and since
$Q^{\prime}_{1}$ and $Q^{\prime}_{2}$ are locally cheapest, it must contain a
vertex of $Q^{\prime}_{1}$. Let $x_{\ell^{\prime}}$ denote the vertex on
$T[x_{1},x_{\ell}]$ closest to $x_{\ell}$ that belongs to $Q^{\prime}_{1}$. We
claim that $\widetilde{P}_{1}=Q^{\prime}_{1}\setminus
Q^{\prime}_{1}[x_{\ell^{\prime}},x_{i^{\prime}}]\cup T[x_{\ell^{\prime}},u]$.
To see this, note that the deletion of the vertices of
$Q^{\prime}_{2}[x_{\ell},v^{\prime}]$ removes all vertices of $Q^{\prime}_{2}$
from $T[x_{\ell^{\prime}},x_{i^{\prime}}]$; these vertices (weakly) follow
$x_{\ell}$ on $Q^{\prime}_{2}$ by its quasi-monotonicity. Hence, as
$x_{\ell^{\prime}}$ and $x_{i^{\prime}}$ are both on $Q^{\prime}_{2}$, we
obtain $T[x_{\ell^{\prime}},x_{i^{\prime}}]\subseteq\widetilde{P}_{1}$.
Observe also that if a vertex $z$ of $Q^{\prime}_{2}[y,x_{\ell}]$ is contained
in some $T_{h}$ with $h<\ell$, then $x_{h}\in V(Q^{\prime}_{1}\cup
Q^{\prime}_{2})$ by Lemma 35, which implies $x_{h}\in V(Q^{\prime}_{1})$ by
the definition of $x_{\ell}$, and thus we get $h\leq\ell^{\prime}$ from the
definition of $x_{\ell^{\prime}}$. However, then the removal of $z$ from
$Q^{\prime}_{2}$ cannot result in a shortcut, since $Q^{\prime}_{1}$ is plain
and thus its intersection with $T_{h}$ is a path. Therefore,
$\widetilde{P}_{1}=Q^{\prime}_{1}\setminus
Q^{\prime}_{1}[x_{\ell^{\prime}},x_{i^{\prime}}]\cup T[x_{i^{\prime}},u]$
indeed holds. As a consequence, the plainness and quasi-monotonicity of
$P_{1}$ immediately implies that $\widetilde{P}_{1}$ is plain and quasi-
monotone as well, a contradiction to our assumption $x_{k}$ is a vertex on
$\widetilde{P}_{1}$ where one of these properties is violated. Hence,
$(\widetilde{P}_{1},\widetilde{P}_{2})$ is a partial solution for
$(u,v,\tau)$. $\lhd$

A direct consequence of Claims 42 and 43 is that neither $y\in
V(Q^{\prime}_{1})$ nor $y\in V(Q_{2})$ is possible, as that would contradict
the optimality of $(Q_{1},Q_{2})$. Hence, $V(Q^{\prime}_{1}\cup
Q^{\prime}_{2})\cap V(R)=\emptyset$, so by Claim 41 and Inequality 6 we know
that $(P_{1},P_{2})$ is a partial solution for $(u,v,\tau)$ of minimum weight,
as required. ∎

###  4.4 Assembling the Parts

Using Algorithm PartSol as a subroutine, it is now straightforward to
construct an algorithm that computes two permissively disjoint
$(\\{a_{1},a_{2}\\},\\{b_{1},b_{2}\\})$-paths of minimum total weight; see
Algorithm PermDisjoint.

Algorithm PermDisjoint Computing two permissively disjoint
$(\\{a_{1},a_{2}\\},\\{b_{1},b_{2}\\})$-paths of minimum total weight in $G$.

1:Vertices $a_{1},a_{2},b_{1},$ and $b_{2}$ in $T$ for which
$T[a_{1},b_{1}]\cap T[a_{2},b_{2}]\neq\emptyset$.

2:Two permissively disjoint $(\\{a_{1},a_{2}\\},\\{b_{1},b_{2}\\})$-paths of
minimum total weight, or $\varnothing$ if no such paths exist.

3:for all $u,v\in V(T)\textrm{ and }\tau\subseteq\mathcal{T}\setminus\\{T\\}$
do $F(u,v,\tau)\leftarrow\varnothing$.

4:for $i=1$ to $r$ do

5: for all $j$ where $j>i$ or $j=r$ do

6: for all $u\in V(T_{i})$, $v\in V(T_{j})$ and
$\tau\subseteq\mathcal{T}\setminus\\{T\\}$ do

7: $F(u,v,\tau)\leftarrow$ PartSol$(u,v,\tau)$.

8:if $F(b_{1},b_{2},\mathcal{T}\setminus\\{T\\})=\varnothing$ and
$F(b_{2},b_{1},\mathcal{T}\setminus\\{T\\})=\varnothing$ then return
$\varnothing$.

9:else return a path pair in
$\\{F(b_{1},b_{2},\mathcal{T}\setminus\\{T\\}),F(b_{2},b_{1},\mathcal{T}\setminus\\{T\\})\\}$
with minimum weight.

Using the correctness of Algorithm PartSol, as established by Lemma 37, and
the observation in Lemma 33 on how partial solutions can be used to find two
permissively disjoint $(\\{a_{1},a_{2}\\},\\{b_{1},b_{2}\\})$-paths of minimum
total weight, we immediately obtain the following.

######  Corollary 44.

For each constant $c\in\mathbb{N}$, there is a polynomial-time algorithm that
finds two permissively disjoint $(\\{a_{1},a_{2}\\},\\{b_{1},b_{2}\\})$-paths
of minimum total weight in $G$ (if such paths exist), where the set of
negative edges in $G$ spans $c$ trees.

Using Corollary 44, we can now give the proof of Theorem 1. Algorithm STDP
contains a pseudo-code description of our algorithm solving Shortest Two
Disjoint Paths.

Algorithm STDP Solving Shortest Two Disjoint Paths with conservative weights.

1:An instance $(G,w,s,t)$ where $w$ is conservative on $G$.

2:A solution for $(G,w,s,t)$ with minimum weight, or $\varnothing$ if no
solution exist.

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

4:for all $E^{\prime}\subseteq E$ such that $E\setminus E^{\prime}\subseteq
E^{-}$ and $|E\setminus E^{\prime}|\leq 1$ do $\triangleright$ Separable
solutions.

5: Create the instance $(G[E^{\prime}],w_{|E^{\prime}},s,t)$.

6: Let $\mathcal{T}^{\not\ni s,t}=\\{T:T$ is a maximal tree in
$G[E^{\prime}\cap E^{-}]$ with $s,t\notin V(T)\\}$.

7: for all $Z\subseteq V$ such that $|Z\cap V(T)|=1$ for each
$T\in\mathcal{T}^{\not\ni s,t}$ do

8: Create the network $N_{Z}$ from instance
$(G[E^{\prime}],w_{|E^{\prime}},s,t)$. $\triangleright$ Use Def. 14.

9: if $\exists$ a flow $f$ of value $2$ in $N_{Z}$ then

10: Compute a minimum-cost flow $f$ of value 2 in $N_{Z}$.

11: Construct a solution $(S_{1},S_{2})$ from $f$ using Lemma 15.

12: $\mathcal{S}\leftarrow(S_{1},S_{2})$.

13:for all $T\in\mathcal{T}$ do $\triangleright$ Non-separable solutions.

14: for all partitions $(\mathcal{T}_{s},\mathcal{T}_{0},\mathcal{T}_{t})$ of
$\mathcal{T}\setminus\\{T\\}$ do

15: if $\mathcal{T}_{s}\neq\emptyset$ then

16: for all $a_{1},a_{2}\in V(T)$ with $a_{1}\neq a_{2}$ do

17: Create sub-instances $I_{s}^{1}$ and $I_{s}^{2}$. $\triangleright$ Use
Def. 17.

18: Compute
$(Q^{\scalebox{0.5}{$\nearrow$}}_{1},Q^{\scalebox{0.5}{$\nearrow$}}_{2})=\textup{STDP}(I_{s}^{1})$.

19: Compute
$(Q^{\scalebox{0.5}{$\searrow$}}_{1},Q^{\scalebox{0.5}{$\searrow$}}_{2})=\textup{STDP}(I_{s}^{2})$.

20: if
$(Q^{\scalebox{0.5}{$\nearrow$}}_{1},Q^{\scalebox{0.5}{$\nearrow$}}_{2})\neq\varnothing$
and
$(Q^{\scalebox{0.5}{$\searrow$}}_{1},Q^{\scalebox{0.5}{$\searrow$}}_{2})\neq\varnothing$
then

21: Create a solution $(S_{1},S_{2})$ from
$(Q^{\scalebox{0.5}{$\nearrow$}}_{1},Q^{\scalebox{0.5}{$\nearrow$}}_{2})$ and
$(Q^{\scalebox{0.5}{$\searrow$}}_{1},Q^{\scalebox{0.5}{$\searrow$}}_{2})$
using Lemma 19.

22: $\mathcal{S}\leftarrow(S_{1},S_{2})$.

23: else if $\mathcal{T}_{t}\neq\emptyset$ then

24: for all $b_{1},b_{2}\in V(T)$ with $b_{1}\neq b_{2}$ do

25: Create sub-instances $I_{t}^{1}$ and $I_{t}^{2}$. $\triangleright$ Use
Def. 18.

26: Compute
$(Q^{\scalebox{0.5}{$\nearrow$}}_{1},Q^{\scalebox{0.5}{$\nearrow$}}_{2})=\textup{STDP}(I_{t}^{1})$.

27: Compute
$(Q^{\scalebox{0.5}{$\searrow$}}_{1},Q^{\scalebox{0.5}{$\searrow$}}_{2})=\textup{STDP}(I_{t}^{2})$.

28: if
$(Q^{\scalebox{0.5}{$\nearrow$}}_{1},Q^{\scalebox{0.5}{$\nearrow$}}_{2})\neq\varnothing$
and
$(Q^{\scalebox{0.5}{$\searrow$}}_{1},Q^{\scalebox{0.5}{$\searrow$}}_{2})\neq\varnothing$
then

29: Create a solution $(S_{1},S_{2})$ from
$(Q^{\scalebox{0.5}{$\nearrow$}}_{1},Q^{\scalebox{0.5}{$\nearrow$}}_{2})$ and
$(Q^{\scalebox{0.5}{$\searrow$}}_{1},Q^{\scalebox{0.5}{$\searrow$}}_{2})$
using Lemma 19.

30: $\mathcal{S}\leftarrow(S_{1},S_{2})$.

31: else$\triangleright$ $\mathcal{T}_{s}=\mathcal{T}_{t}=\emptyset$.

32: for all $a_{1},a_{2},b_{1},b_{2}\in V(T)$ that constitute a reasonable
guess do

33: if $\exists$ a flow $f$ of value $4$ in $N_{(a_{1},b_{1},a_{2},b_{2})}$
then $\triangleright$ Use Def. 20.

34: if $\exists$ two permissively disjoint
$(\\{a_{1},a_{2}\\},\\{b_{1},b_{2}\\})$-paths in $G$ then

35: Compute a minimum-cost flow $f$ of value 4 in
$N_{(a_{1},b_{1},a_{2},b_{2})}$.

36: Compute permissively disjoint
$(\\{a_{1},a_{2}\\},\\{b_{1},b_{2}\\})$-paths $Q_{1}$ and $Q_{2}$.

37:$\triangleright$ Use Algorithm PermDisjoint in Section 4.3

38: Construct a solution $(S_{1},S_{2})$ from $f$, $Q_{1}$, and $Q_{2}$ using
Lemma 21.

39: $\mathcal{S}\leftarrow(S_{1},S_{2})$.

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

41:else Let $S^{\star}$ be the cheapest pair among those in $\mathcal{S}$, and
return $S^{\star}$.

Proof of Theorem 1. We show that given an instance $(G,w,s,t)$ of Shortest Two
Disjoint Paths where $w$ is conservative on $G$, Algorithm STDP computes a
solution for $(G,w,s,t)$ of minimum weight whenever a solution exists. We
apply induction based on the number of negative trees in $\mathcal{T}$.
Suppose that $(P_{1},P_{2})$ is an optimal solution for $(G,w,s,t)$ with total
weight $w^{\star}$.

First, if $(P_{1},P_{2})$ is separable, then there exists some
$E^{\prime}\subseteq E$ with $|E\setminus E^{\prime}|\leq 1$ such that the
instance $(G[E^{\prime}],w_{|E^{\prime}},s,t)$ has a strongly separable
solution with weight at most $w^{\star}$: if $(P_{1},P_{2})$ itself is
strongly separable, then this holds for $E^{\prime}=E$, and if $(P_{1},P_{2})$
is separable but not strongly separable, then by Lemma 16, it holds for some
$E^{\prime}=E\setminus\\{e\\}$, $e\in E^{-}$. In either case, Algorithm STDP
will create at least one instance $(G[E^{\prime}],w_{|E^{\prime}},s,t)$ on
Line 5 that admits a strongly separable solution of weight $w^{\star}$. For
this particular instance, Lemma 15 guarantees that for some choice of $Z$,
Algorithm STDP will find on Line 10 a flow of value 2 and cost at most
$w^{\star}$ in $N_{Z}$, from which it obtains a solution $(S_{1},S_{2})$ of
weight at most $w^{\star}$ for $(G[E^{\prime}],w_{|E^{\prime}},s,t)$ using
again Lemma 15. Note that since $G[E^{\prime}]$ is a subgraph of $G$, the
obtained path pair $(S_{1},S_{2})$, of weight at most $w^{\star}$, is also a
solution for $(G,w,s,t)$.

Second, if $(P_{1},P_{2})$ is not separable, then by Definition 12 there
exists a tree $T\in\mathcal{T}$ at which $P_{1}$ and $P_{2}$ are in contact.
By Lemma 9, there exists a $T$-valid partition of
$\mathcal{T}\setminus\\{T\\}$. Let us consider the iteration of Algorithm STDP
when it chooses $T$ on Line 13 and a valid $T$-partition
$(\mathcal{T}_{s},\mathcal{T}_{0},\mathcal{T}_{t})$ on Line 14. If
$\mathcal{T}_{s}$ is not empty, then Algorithm STDP guesses the first vertices
on the solution paths, $a_{1}$ and $a_{2}$, that are contained in $T$.
Algorithm STDP then uses recursion to solve the sub-instances $I_{s}^{1}$ and
$I_{s}^{2}$, and applies Lemma 19 to create a solution for $(G,w,s,t)$ using
the obtained solutions for $I_{s}^{1}$ and $I_{s}^{2}$. To see that the
weighted graphs underlying $I_{s}^{1}$ and $I_{s}^{2}$ are conservative, note
that the addition of vertex $a^{\star}$ does not create a negative-weight
cycle: any cycle $C$ through $a^{\star}$ necessarily includes the edges
$a_{1}a^{\star}$ and $a_{2}a^{\star}$, plus a path between $a_{1}$ and $a_{2}$
whose weight is at least $w(T[a_{1},a_{2}])$ by statement (1) of Lemma 3; thus
we have $w(C)\geq 2w_{a^{\star}}+w(T[a_{1},a_{2}])=0$. Observe that the number
of negative trees in $I_{s}^{1}$ is $|\mathcal{T}_{s}|<|\mathcal{T}|$ because
$T\notin\mathcal{T}_{s}$, and the number of negative trees in $I_{s}^{2}$ is
$|\mathcal{T}\setminus\mathcal{T}_{s}|<|\mathcal{T}|$ because
$\mathcal{T}_{s}\neq\emptyset$. Hence, due to our inductive hypothesis we know
that these recursive calls for $I_{s}^{1}$ and for $I_{s}^{2}$ return minimum-
weight solutions for them. By Lemma 19, this implies that the solution
$(S_{1},S_{2})$ for $(G,w,s,t)$ obtained on Line 21 has weight at most
$w(P_{1})+w(P_{2})$.

Similarly, if $\mathcal{T}_{t}$ is not empty, then Algorithm STDP guesses the
last vertices on the solution paths, $b_{1}$ and $b_{2}$, that are contained
in $T$. Algorithm STDP then uses recursion to solve the sub-instances
$I_{t}^{1}$ and $I_{t}^{2}$, and applies Lemma 19 to create a solution for
$(G,w,s,t)$ using the obtained solutions for $I_{t}^{1}$ and $I_{t}^{2}$.
Again, the weighted graphs in $I_{t}^{1}$ and $I_{t}^{2}$ are conservative due
to the value of $w_{b^{\star}}$ and statement (1) of Lemma 3. Observe that the
number of negative trees in $I_{t}^{1}$ is
$|\mathcal{T}\setminus\mathcal{T}_{t}|<|\mathcal{T}|$ because
$\mathcal{T}_{t}\neq\emptyset$, and the number of negative trees in
$I_{t}^{2}$ is $|\mathcal{T}_{t}|<|\mathcal{T}|$ because
$T\notin\mathcal{T}_{t}$. Hence, due to our inductive hypothesis we know that
these recursive calls for $I_{t}^{1}$ and for $I_{t}^{2}$ return minimum-
weight solutions for them. By Lemma 19, this implies that the solution
$(S_{1},S_{2})$ for $(G,w,s,t)$ obtained on Line 29 has weight at most
$w(P_{1})+w(P_{2})$.

If $\mathcal{T}_{s}=\mathcal{T}_{t}=\emptyset$, then Algorithm STDP guesses
the first and the last vertices on the solution paths contained in $T$;
consider the iteration when the guessed vertices, $a_{i}$ and $b_{i}$, are the
first and last vertices of $P_{i}$ contained in $T$, for both $i\in[2]$. Note
that since $(\emptyset,\mathcal{T}\setminus\\{T\\},\emptyset)$ is a valid
$T$-partition, we know that the paths $P[s,a_{i}]$ and $P[b_{i},t]$ for
$i\in[2]$ contain no edges of $E^{-}$. Hence, these four paths directly yield
a flow of value 4 in the network $N_{(a_{1},b_{1},a_{2},b_{2})}$. Also, the
paths $P_{1}[a_{1},b_{1}]$ and $P_{2}[a_{2},b_{2}]$ are two permissively
disjoint $(\\{a_{1},a_{2}\\},\\{b_{1},b_{2}\\})$-paths in $G$. Thus Algorithm
STDP satisfies the conditions on Lines 33 and 34, and proceeds with computing
a minimum-cost flow of value 4 in $N_{(a_{1},b_{1},a_{2},b_{2})}$, as well as
two permissively disjoint $(\\{a_{1},a_{2}\\},\\{b_{1},b_{2}\\})$-paths of
minimum weight in $G$ using Algorithm PermDisjoint. Note that by Lemma 21 the
returned flow $f$ will have cost at most
$\sum_{i=1}^{2}w(P_{i}[s,a_{i}])+w(P_{i}[b_{i},t])$, and by Corollary 44,
Algorithm PermDisjoint returns two permissively disjoint
$(\\{a_{1},a_{2}\\},\\{b_{1},b_{2}\\})$-paths of weight at most
$\sum_{i=1}^{2}w(P_{i}[a_{i},b_{i}])$. Finally, the algorithm applies Lemma 21
to construct a solution of weight at most

$\sum_{i=1}^{2}w(P_{i}[s,a_{i}])+w(P_{i}[b_{i},t])+w(P_{i}[a_{i},b_{i}])=\sum_{i=1}^{2}w(P_{i}),$

as required.

It remains to analyze the running time of Algorithm STDP. Let $n=|V|$ and
recall that the number of trees spanned by all negative edges in $G$ is
$c=|\mathcal{T}|$. We denote by $T(n,c)$ the running time of Algorithm STDP as
a function of these two integers.

There are $|E^{-}|+1\leq n$ possibilities for choosing $E^{-}$ on Line 4, and
at most $\binom{n}{c+1}$ possibilities for choosing $Z$ on Line 7, because
removing an edge of $E^{-}$ from $G$ may increase parameter $c$, that is, the
number of connected components of the subgraph spanned by all negative-weight
edges. Creating the network $N_{Z}$ and computing a minimum-cost flow of value
$2$ in it takes $O(n^{3})$ time by using the Successive Shortest Path
algorithm [9, 8, 4], and from that it takes linear time to construct a
solution for $(G,w,s,t)$. Thus, the computations performed on Lines 4–12 take
$O(n^{c+5})$ time.

There are $c$ possibilities to choose $T$ on Line 13, and there are $3^{c-1}$
possibilities to choose the partition
$(\mathcal{T}_{s},\mathcal{T}_{0},\mathcal{T}_{t})$ of
$\mathcal{T}\setminus\\{T\\}$ on Line 14. The iteration on Line 16 yields a
factor of less than $n^{2}$. Both recursive calls take time at most
$T(n,c-1)$, since the the number of negative trees decreases in both
$I_{s}^{1}$ and $I_{s}^{2}$ (as we have already shown in this proof). Applying
Lemma 19 (which in turn relies on Lemma 10) takes linear time. Hence, the
computations on Lines 16–22 take time $O(n^{2})T(n,c-1)$. Similarly, Lines
24–30 also take time $O(n^{2})T(n,c-1)$.

There are $O(n^{4})$ possibilities to choose the vertices $a_{1},b_{1},a_{2}$,
and $b_{2}$ on Line 32. The minimum-cost flow computation on Line 35 takes
$O(n^{3})$ time, but the bottleneck here is the running time of Algorithm
PermDisjoint, called on Line 37. Algorithm PermDisjoint performs a call to
Algorithm PartSol for at most $2^{c-1}\binom{n}{2}$ triples $(u,v,\tau)$.
Algorithm PartSol in turn iterates over all possible values for vertices
$u^{\prime}$ and $v^{\prime}$ as well as over all values of
$\tau^{\prime}\subseteq\tau$, and for each triple
$(u^{\prime},v^{\prime},\tau^{\prime})$ computes a shortest
$(u^{\prime},v)$-path in the auxiliary graph $G\langle
T[v^{\prime},u],u^{\prime},v,\tau\setminus\tau^{\prime}\rangle$.777 In fact,
there are two more shortest-path computations performed by the algorithm
during Lines 4–9 of Algorithm PartSol, but the running time of Algorithm
PartSol is dominated by the computations on Lines 10–19. Note that $G\langle
T[v^{\prime},u],u^{\prime},v\rangle$ implicitly depends also on the path $X$
(via the definition of the trees $T_{i}$, $i\in[r]$). Since there are
$O(n^{2})$ possibilities for choosing $X$, then $n^{4}$ possibilities to
choose $u,v,u^{\prime}$ and $v^{\prime}$, and then $2^{c-1}$ possibilities to
choose the subset of negative trees (other than $T$) contained in the given
auxiliary graph, we obtain that the number of shortest-path computations we
need to perform during Lines 32–39 of Algorithm STDP is $O(2^{c-1}n^{6})$ in
total.

Let us now consider an implementation of Lines 32–39 of Algorithm STDP where
we compute all necessary shortest paths in all possible auxiliary graphs as a
preprocessing step: since we can compute a shortest path between two given
vertices in an undirected conservative graph in $O(n^{3})$ time (see e.g.,
[17, Section 29.2]), this takes $O(2^{c-1}n^{9})$ time in total. Assuming that
we already have the results of this preprocessing step, a single call to
Algorithm PartSol (assuming that all partial solutions called for on line 13
are available) takes $O(2^{c-1}n^{3})$ time, because there are
$O(2^{c-1}n^{2})$ possibilities for choosing $u^{\prime},v^{\prime}$ and
$\tau^{\prime}$ (recall that $T\notin\tau^{\prime}$), and an iteration for
fixed values of $u^{\prime},v^{\prime}$ and $\tau^{\prime}$ takes linear time.
Therefore, running Algorithm PermDisjoint for fixed values of
$a_{1},b_{1},a_{2}$ and $b_{2}$ takes
$2^{c-1}n^{2}O(2^{c-1}n^{3})=O(2^{2c-2}n^{5})$ time (as it calls Algorithm
PartSol at most $2^{c-1}n^{2}$ times), which yields a running time of
$O(2^{2c-2}n^{9})$ in total after the preprocessing phase. Hence, the overall
running time of Lines 32–39 (including all necessary preprocessing steps) is
$O(2^{2c-2}n^{9})$.

This yields the following recursive formula for the total running time of
Algorithm STDP:

$T(n,c)=O(n^{c+5})+c\dot{3}^{c-1}\big{(}O(n^{2})T(n,c-1)+O(2^{2c-2}n^{9})\big{)}$

from which we can conclude $T(n,c)=O(n^{2c+7})$. In particular, for $c=1$ we
obtain a running time of $O(n^{9})$. ∎

##  5 Conclusion

We have presented a polynomial-time algorithm for solving the Shortest Two
Disjoint Paths problem on undirected graphs $G$ with conservative edge
weights, assuming that the number of connected components in the subgraph
$G[E^{-}]$ spanned by all negative-weight edges is a fixed constant $c$. The
running time of our algorithm is $O(n^{2c+9})$ on an $n$-vertex graph. Is it
possible to give a substantially faster algorithm for this problem? In
particular, is it possible to give a fixed-parameter tractable algorithm for
Shortest Two Disjoint Paths on undirected conservative graphs when
parameterized by $c$?

More generally, is it possible to find in polynomial time $k$ openly disjoint
$(s,t)$-paths with minimum total weight for some fixed $k\geq 3$ in undirected
conservative graphs with constant values of $c$?

### Funding

Ildikó Schlotter acknowledges the support of the Hungarian Academy of Sciences
under its Momentum Programme (LP2021-2) and its János Bolyai Research
Scholarship.

## References

  * [1] Isolde Adler, Stavros G. Kolliopoulos, Philipp Klaus Krause, Daniel Lokshtanov, Saket Saurabh, and Dimitrios M. Thilikos.  Irrelevant vertices for the Planar Disjoint Paths problem.  Journal of Combinatorial Theory, Series B, 122:815–843, 2017.  doi:10.1016/j.jctb.2016.10.001.
  * [2] Aaron Bernstein, Danupon Nanongkai, and Christian Wulff-Nilsen.  Negative-weight single-source shortest paths in near-linear time.  In FOCS 2022: Proceedings of the 63rd Annual IEEE Symposium on Foundations of Computer Science, pages 600–611. IEEE Computer Society, 2022\.  doi:10.1109/FOCS54457.2022.00063.
  * [3] Andreas Björklund and Thore Husfeldt.  Shortest two disjoint paths in polynomial time.  SIAM Journal on Computing, 48(6):1698–1710, 2019.  doi:10.1137/18M1223034.
  * [4] Robert G. Busacker and Paul J. Gowen.  A procedure for determining a family of miminum-cost network flow patterns.  Technical Report ORO-TP-15, Operations Research Office, Johns Hopkins University, 1960.
  * [5] Marek Cygan, Dániel Marx, Marcin Pilipczuk, and Michal Pilipczuk.  The planar directed $k$-vertex-disjoint paths problem is fixed-parameter tractable.  In FOCS 2013: Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, pages 197–206. IEEE Computer Society, 2013\.  doi:10.1109/FOCS.2013.29.
  * [6] Éric Colin de Verdière and Alexander Schrijver.  Shortest vertex-disjoint two-face paths in planar graphs.  ACM Trans. Algorithms, 7(2):19:1–19:12, 2011.  doi:10.1145/1921659.1921665.
  * [7] Guoli Ding, A. Schrijver, and P. D. Seymour.  Disjoint paths in a planar graph – a general theorem.  SIAM Journal on Discrete Mathematics, 5(1):112–116, 1992.  doi:10.1137/0405009.
  * [8] Masao Iri.  A new method for solving transportation-network problems.  Journal of the Operations Research Society of Japan, 3:27–87, 1960\.
  * [9] William S. Jewell.  Optimal flow through networks.  Operations Research, 10(4):476–499, 1962.
  * [10] Richard M. Karp.  On the computational complexity of combinatorial problems.  Networks, 5(1):45–68, 1975.
  * [11] Yusuke Kobayashi and Christian Sommer.  On shortest disjoint paths in planar graphs.  Discrete Optimization, 7(4):234–245, 2010.  doi:10.1016/j.disopt.2010.05.002.
  * [12] Daniel Lokshtanov, Pranabendu Misra, Michał Pilipczuk, Saket Saurabh, and Meirav Zehavi.  An exponential time parameterized algorithm for planar disjoint paths.  In STOC 2020: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, page 1307–1316. Association for Computing Machinery, 2020.  doi:10.1145/3357713.3384250.
  * [13] James F. Lynch.  The equivalence of theorem proving and the interconnection problem.  ACM SIGDA Newsletter, 5:31–36, 1975.  doi:10.1145/1061425.1061430.
  * [14] Neil Robertson and P.D. Seymour.  Graph minors. XIII. The disjoint paths problem.  Journal of Combinatorial Theory, Series B, 63(1):65–110, 1995.  doi:10.1006/jctb.1995.1006.
  * [15] Ildikó Schlotter and András Sebő.  Odd paths, cycles and $T$-joins: Connections and algorithms, 2022.  arXiv:2211.12862.
  * [16] Alexander Schrijver.  Finding $k$ disjoint paths in a directed planar graph.  SIAM Journal on Computing, 23(4):780–788, 1994.  doi:10.1137/S0097539792224061.
  * [17] Alexander Schrijver.  Combinatorial Optimization: Polyhedra and Efficiency.  Springer, Berlin, 2003.