$$\text{dist}\_{G\_k}(s, t) = D\_{G\_k}(t) \ge D\_{G\_{k-1}}(t) \ge \dots \ge D\_{G\_1}(t) = D\_{G'}(t) \ge \text{dist}\_{G'}(s, t) \ge d.$$

Finally, (3) states that for all *v, w* ∈ *V* \ {*s, t*} with *bv < bw* that

$$\text{dist}\_{G^{\prime\prime}}(s,v) = D\_{G^{\prime\prime}}(v) \le D\_{G^{\prime\prime}}(w) = \text{dist}\_{G^{\prime\prime}}(s,w). \tag{8}$$

We now describe how to obtain the sequence (*G*′ = *G*1*, G*2*, . . . , Gk*) of graphs. To this end, we need a rather technical order over the graphs in G. We say that (*V, Eα*) = *Gα <*∆ *Gγ* = (*V, Eγ*) for *Gα, Gγ* ∈ G if and only if

$$\bullet \quad |E\_{\alpha}| = |E\_{\gamma}|, \; D\_{G\_{\alpha}}(v) = D\_{G\_{\gamma}}(v) \text{ for all } v \in V \; \backslash \; \{t\}, \; \text{and } D\_{G\_{\alpha}}(t) < D\_{G\_{\gamma}}(t).$$

Notice that *<*∆ defnes a total preorder on G, that is, the order *<*∆ is transitive, refexive, and for each two graphs *Gα, Gβ* ∈ G with *Gα* ̸= *Gβ* it holds that *Gα <*∆ *Gβ* or *Gβ <*∆ *Gα*.

Let *Gℓ* be a graph in the sequence. We will guarantee that each graph in the sequence fulflls (1) and (2). Consequently, if *Gℓ* satisfes (3), then we have found the last graph in the sequence. Otherwise, we describe how to obtain another graph *Gℓ*+1 ∈ G such that (2) holds for *Gℓ* and *Gℓ*+1 and *Gℓ*+1 *<*∆ *Gℓ*. Since *<*∆ is a total preorder, we can only build a fnite sequence and hence at some point a graph has to satisfy (3).

Since *Gℓ* = (*V, Eℓ*) does not satisfy (3), there is some minimum *j* such that *DGℓ* (*vj* ) *> DGℓ* (*vj*+1). Let

$$X := \{ x \in N\_G(v\_{j+1}) \mid (b\_x  b\_{v\_{j+1}} \lor y = t) \land \{v\_{j+1}, y\} \in E \mid E\_\ell \land \{v\_j, y\} \in E\_\ell\}.$$

See Figure 4.2 for an example of *X* and *Y* . We distinguish between the two cases |*X*| ≥ |*Y* | and |*X*| *<* |*Y* |.

**Figure 4.2:** An example for *X* and *Y* . Red (vertical) edges are contained in *E* \ *Eℓ*. For the sake of readability we do not depict edges in *Eℓ*. Note that *X* = {*vj*−2} and *Y* = {*vj*+3}.

**Case 1 (**|*X*| ≥ |*Y* |**):** Let

$$E\_{\ell+1} := (E\_{\ell} \backslash \{ \{ v\_j, y \} \mid y \in Y \}) \cup \{ \{ v\_j, x \} \mid x \in X \},$$

and *Gℓ*+1 . .= (*V, Eℓ*+1). Since |*X*| ≥ |*Y* |, *X* ∩ *Y* = ∅, and *Gℓ* ∈ G, it holds that |*Eℓ*+1| ≥ |*Eℓ*| ≥ |*E* \ *F*| and thus *Gℓ*+1 ∈ G. Clearly, for all *v* ∈ *V* \ {*t*} with *bv < bvj* , we have *DGℓ*+1 (*v*) = *DGℓ* (*v*) as *Eℓ*+1 and *Eℓ* only difer in edges incident to *vj* . Let *w* be the predecessor of *vj*+1 in a shortest monotone *s*-*vj*+1-path in *Gℓ*. Since *DGℓ* (*vj* ) *> DGℓ* (*vj*+1) it holds that *w* ≠ *vj* and hence *bw < bvj < bvj*+1 ≤ *fw*. Moreover, vertex *w* is contained in *X* as otherwise *DGℓ* (*vj* ) ≤ *DGℓ* (*w*) + 1 = *DGℓ* (*vj*+1). Thus,

$$D\_{G\_{\ell+1}}(v\_j) = D\_{G\_{\ell}+1}(w) + 1 = D\_{G\_{\ell}}(w) + 1 = D\_{G\_{\ell}}(v\_{j+1}) < D\_{G\_{\ell}}(v\_j)$$

and combined with |*Eℓ*+1| ≥ |*Eℓ*| this yields *Gℓ*+1 *<*∆ *Gℓ*.

It remains to show that *DGℓ* (*t*) ≤ *DGℓ*+1 (*t*). Consider a shortest monotone *s*-*t*-path *P* in *Gℓ*+1. If *P* does not pass through *vj* , then it is also a monotone *s*-*t*-path in *Gℓ* and hence *DGℓ* (*t*) ≤ *DGℓ*+1 (*t*). If *P* passes through *vj* , then let *z* be the successor of *vj* in *P*. Note that if *z* ∈ *Y* , then {*vj*+1*, z*} ∈ *Eℓ*, and if *z /*∈ *Y* , then *z* = *vj*+1 or {*vj*+1*, z*} ∈ *Eℓ* as *bvj* ≤ *bz*. Hence it holds that

$$D\_{G\_\ell}(z) \le D\_{G\_\ell}(v\_{j+1}) + 1 = D\_{G\_{\ell+1}}(v\_j) + 1 = D\_{G\_\ell+1}(z).$$

Finally, let *P* ′ be a shortest monotone *s*-*z*-path in *Gℓ* and let *P* ′′ = *P* ′ • *P*[*z, t*]. Note that *P* ′′ is a monotone *s*-*t*-path of length at most *DGℓ*+1 (*t*) in *Gℓ* and thus *DGℓ* (*t*) ≤ *DGℓ*+1 (*t*).

**Case 2 (**|*X*| *<* |*Y* |**):** We set

$$E\_{\ell+1} := \left( E\_{\ell} \mid \{ \{ v\_{j+1}, x \} \mid x \in X \} \right) \cup \{ \{ v\_{j+1}, y \} \mid y \in Y \}.$$

Since |*X*| *<* |*Y* |, *X* ∩ *Y* = ∅, and *Gℓ* ∈ G, it holds that |*Eℓ*+1| *>* |*Eℓ*| and therefore *Gℓ*+1 ∈ G and *Gℓ*+1 *<*∆ *Gℓ*. It remains to show *DGℓ* (*t*) ≤ *DGℓ*+1 (*t*).

Since *Eℓ* and *Eℓ*+1 only difer in edges incident to *vj*+1, for all *v* with *bv < bvj* it holds that *DGℓ*+1 (*v*) = *DGℓ* (*v*). Let *P* be a shortest monotone *s*-*vj*+1-path in *Gℓ*+1 and let *w* be the predecessor of *vj*+1 in *P*. By defnition of *Eℓ*+1 it holds that *w* = *vj* or {*w, vj*} ∈ *Eℓ* and hence *DGℓ* (*vj* ) ≤ *DGℓ*+1 (*vj*+1). Let *P* ′ be a shortest monotone *s*-*t*-path in *Gℓ*+1. If *P* ′ does not pass through *vj*+1, then it is also a monotone *s*-*t*-path in *Gℓ* as *Eℓ* and *Eℓ*+1 only difer in edges incident to *vj*+1 and hence *DGℓ* (*t*) ≤ *DGℓ*+1 (*t*). If *P* ′ passes through *vj*+1, then let *z* be the successor of *vj*+1 in *P* ′ . Since only edges between *vj*+1 and the vertices in *Y* are contained in *Eℓ*+1 but not in *Eℓ*, it holds that *z* ∈ *Y* . Hence, it holds that {*vj , z*} ∈ *Eℓ* and thus

$$D\_{G\_\ell}(z) \le D\_{G\_\ell}(v\_j) + 1 \le D\_{G\_{\ell+1}}(v\_{j+1}) + 1 = D\_{G\_{\ell+1}}(z).$$

Finally, let *P* ′′ be a shortest monotone *s*-*vj* -path in *Gℓ* and let *P* ′′′ = *P* ′′ • *P*[*z, t*]. Since *P* ′′′ is a monotone *s*-*t*-path of length at most *DGℓ*+1 (*t*) in *Gℓ*, we obtain *DGℓ*+1 (*t*) ≥ *DGℓ* (*t*).

This concludes the proof as we have shown that the sought sequence of graphs is fnite and how to obtain each graph in it from the previous.

Using Lemma 4.2, we now provide the main result of this chapter, that is, a dynamic program that solves Length-Bounded Cut on proper interval graphs in polynomial time. The dynamic program stores for each vertex *v* ∈ *V* \ {*t*} and each possible distance *d* the minimum size of a cut that makes each vertex *u* with *bu* ≥ *bv* or *u* = *t* have distance at least *d* from *s*.

**Theorem 4.4.** Length-Bounded Cut *can be solved in O*(*n* 2 · *m*) *time if the input graph is a proper interval graph.*

*Proof.* We prove the statement by developing a dynamic program. We frst state some general observations and derive from them the main idea behind the dynamic program. We then show how the entries of the table of the dynamic program are computed and how to compute the solution for Length-Bounded Cut from the flled table. We continue with proving the correctness of our algorithm and conclude with analyzing its running time.

We assume that, in the input graph *G* . .= (*V, E*), there is no *s*-*t*-cut of size at most *β* as this cut can be detected in *O*(*n* · *m*) time [FF56] and the answer for Length-Bounded Cut is then always yes. Thus, deg*G*(*s*) *> β* and deg*G*(*t*) *> β* as otherwise the set of edges incident to *s* or *t* are an *s*-*t*cut of size at most *β*. Furthermore, by Lemma 4.1, we can assume that there is no vertex *v* with *fv < bs* or *bv > ft*. By Lemma 4.2, we can assume that we search for a solution in which for all *vi , vj* ∈ *V* \ {*s, t*} with *i < j* it holds that dist(*s, vi*) ≤ dist(*s, vj* ). Hence, we construct a table *T* : *V* × N → N which stores for each vertex *vi* ∈ *V* \ {*s, t*} and each possible distance 2 ≤ *d* ≤ *λ* the minimum number of edges that have to be deleted from *G*′ . .= (*V* ′ *, E*′ ) . .= *G* − {*t*} to ensure the following. First, dist(*s, vk*) ≤ dist(*s, vℓ*) for all *k* ≤ *ℓ* ≤ *i*. Second, each vertex *vj* ∈ *V* \ {*s, t*} with *j* ≥ *i* has distance at least *d* from *s*.

We start with showing how to initialize the table *T*.  Hence, to increase the distance of each *vj* with *j* ≥ *i* for some given *i* to at least two, one has to delete all edges between *s* and the vertices in {*vj* | *i* ≤ *j* ≤ deg(*s*)}. Thus, the table is initialized with *T*[*vi ,* 2] = 0 for all *i >* deg(*s*) and *T*[*vi ,* 2] = deg(*s*)−*i*+ 1 for all *i* ≤ deg(*s*). We further initialize *T*[*v*1*, d*] = deg(*s*) for all *d* ≥ 3.

We next show how to compute the solution to Length-Bounded Cut once the table *T* is completely flled. Since we seek a solution *F* such that in *H* . .= (*V, E* \ *F*) it holds that dist*H*(*s, t*) *> λ*, each vertex *u* ∈ *NH*(*t*) has to satisfy dist*H*(*s, u*) ≥ *λ*. Note that deg*G*(*t*) *> β* and hence there is at least one vertex *v* ∈ *NH*(*t*). Thus, to compute the solution for Length-Bounded Cut, we iterate over *v* ∈ *NG*(*t*) \ {*s*} and compute *T*[*v, λ*] + |{*u* ∈ *N*(*t*) | *u* = *s* ∨ *bu < bv*}|. Note that this corresponds to the statement that each neighbor *u* of *t* in *G* has distance at least *λ* from *s* or the edge {*u, t*} was removed. Hence, the distance between *s* and *t* in the resulting graph is at least *λ* + 1. Further, if we take the minimum value over all iterations and compare it to *β*, then this solves Length-Bounded Cut.

It remains to present the recursive formula for *T*, to prove the correctness of our dynamic program, and to analyze its running time. We start with showing how to compute *T*. For the sake of simplicity, we also store, for each table entry *T*[*vi , d*] with *d* ≥ 2, in a second table *S*[*vi , d*] the vertex *vj* ∈ *V* \ {*s, t*} with minimum *j* such that *vj* has distance *d*−1 from *s* in some solution corresponding to *T*[*vi , d*]. We initialize *S*[*vi ,* 2] = *v*1 for all *vi* and *S*[*v*1*, d*] = *v*1 for all *d* ≥ 3. Note that *S*[*vi , d*] = *v*1 might not represent what we claimed if we seek to remove the edge {*s, v*1}. However, in this case there is no solution as we assume

that deg(*s*) *> β*. For increasing values of *d* ≥ 3, we iterate over 2 ≤ *i* ≤ *n* − 2 and compute

$$\begin{aligned} T[v\_i, d] &= \min\_{j$$

where *C*[*vh, vj , vi* ] is a function that represents for each triple (*vh, vj , vi*) of vertices with *h < j < i* the set of edges between a vertex *vℓ* with *h* ≤ *ℓ < j* and a vertex *vr* with *r* ≥ *i*. For technical reasons we exclude *s* and *t* here and hence the formal defnition is

$$C[v\_h, v\_j, v\_i] := \{ \{v\_\ell, v\_r\} \in E \mid h \le \ell < j < i \le r \}.$$

The vertex *vh* is used to avoid double counting.

We continue by proving that *S* and *T* store exactly what they are supposed to. Assume towards a contradiction that there is a vertex *vi* and a distance *d* ≥ 2 such that *S*[*vi , d*] or *T*[*vi , d*] were computed incorrectly. Then there is also a smallest *d* such that there is a vertex *vi* for which *S*[*vi , d*] or *T*[*vi , d*] are computed incorrectly and we assume that *vi* is the vertex with the smallest index *i* such that *S*[*vi , d*] or *T*[*vi , d*] is computed incorrectly. Since we have already shown that the initialization for *d* = 2 is correct, we focus on the case *d >* 2 and distinguish between the three cases that *S*[*vi , d*] was computed incorrectly, that *T*[*vi , d*] *> c*, or that *T*[*vi , d*] *< c*, where *c* is the correct value of *T*[*vi , d*].

If *T*[*vi , d*] *< c*, then let *vj* be a vertex with *j < i* that minimizes the sum *T*[*vj , d* − 1] + |*C*[*S*[*vj , d* − 1]*, vj , vi* ]|. Since we assume that *T*[*vj , d* − 1] is computed correctly (recall that *d* was chosen to be the minimum value for which *S* or *T* was computed incorrectly), there is a set *F*1 of *T*[*vj , d* − 1] edges such that in the graph *H*′ . .= (*V* ′ *, E*′ \ *F*1) it holds that dist*H*′ (*s, vr*) ≥ *d* − 1 for all *r* ≥ *j* and dist*H*′ (*s, vℓ*) ≤ dist*H*′ (*s, vk*) for all *ℓ* ≤ *k* ≤ *j*. Let *vh* = *S*[*vj , d* − 1]. Since *S*[*vj , d* − 1] is by assumption computed correctly, it holds for all *vℓ* with *ℓ < h* that dist*H*′ (*s, vℓ*) ≤ *d* − 3. Thus, *F*1 contains all edges between vertices in {*vℓ* | *ℓ < h*} and {*vr* | *r* ≥ *i*}. Since *C*[*vh, vj , vi* ] is the set of all edges between vertices *vℓ* ′ with *h* ≤ *ℓ* ′ *< j* to vertices *vr* with *r* ≥ *i*, it holds that there is no edge between a vertex of distance at most *d* − 2 from *s* to a vertex *vr* with *r* ≥ *i* in *H* . .= (*V* ′ *, E*′ \ (*F*1 ∪ *C*[*vh, vj , vi* ])). Hence each such vertex *vr* is of distance at least *d* from *s* in *H*. It remains to show that dist*H*(*s, vℓ*) ≤ dist*H*(*s, vk*) for all *ℓ* ≤ *k* ≤ *i*. Note that *H* and *H*′ only

difer in edges in *C*[*vh, vj , vi* ], that is, in edges between vertices *vℓ* and *vr* with *h* ≤ *ℓ* ≤ *j* and *r* ≥ *i*. Since those *vℓ* have distance *d* − 2 and those *vr* have distance at least *d* − 1 from *s* in *H*, it holds that dist*H*(*s, vℓ*) = dist*H*(*s, vℓ*) for all *ℓ* ≤ *i* and thus also *H* fulflls dist*H*(*s, vℓ*) ≤ dist*H*(*s, vk*) for all *ℓ* ≤ *k* ≤ *i*. Since *T*[*vi , d*] = |*F*1 ∪ *C*[*vh, vj , vi* ]| and *F*1 ∩ *C*[*vh, vj , vi* ] = ∅, it holds that

$$T[v\_i, d] = |F\_1| + |C[v\_h, v\_j, v\_i]| = T[v\_j, d-1] + |C[S[v\_j, d-1], v\_j, v\_i]|,$$

and thus *T*[*vi , d*] ≥ *c*, a contradiction.

If *T*[*vi , d*] *> c*, then there is a cut *F* ′ that contains less than *T*[*vi , d*] edges such that in the respective graph *H*′ . .= (*V* ′ *, E*′ \ *F* ′ ) all vertices *vr* with *r* ≥ *i* have distance at least *d* from *s* and dist*H*′ (*s, vk*) ≤ dist*H*′ (*s, vℓ*) for all *k* ≤ *ℓ* ≤ *i*. Then, there is a vertex *vj* such that *vj* and all vertices *vr* with *r* ≥ *j* have distance at least *d* − 1 from *s* in *H*′ and all vertices *vℓ* with *ℓ < j* have distance at most *d* − 2 from *s* in *H*′ . Hence, *F* ′ has to contain all edges in *F* ′′ . .= {{*vℓ, vr*} ∈ *E* | *ℓ < j < i* ≤ *r*} as otherwise a vertex *vr* with *r* ≥ *i* would have distance at most *d* − 1 from *s* in *H*′ . Let *vh* . .= *S*[*vj , d* − 1]. We partition the set *F* ′′ into two disjoint sets *F* ′′ *L* . .= {{*vℓ, vr*} ∈ *E* | *ℓ < h < i* ≤ *r*} and *F* ′′ *R* . .= {{*vℓ, vr*} ∈ *E* | *h* ≤ *ℓ < j < i* ≤ *r*}. Let *H* . .= (*V* ′ *, E*′ \ (*F* ′ \ *F* ′′ *R*)). Notice that *H* and *H*′ only difer in edges in *F* ′′ *R*, that is, in edges incident to vertices *vℓ* and *vr* with *h* ≤ *ℓ < j* and *r* ≥ *i*. Since those *vℓ* have distance *d* − 2 and those *vr* have distance at least *d*−1 from *s* in *H*, the distance between *s* and vertices *vℓ* with *ℓ < j* is the same in *H*′ and *H*. Hence, dist*H*(*s, vk*) ≤ dist*H*(*s, vℓ*) for all *k* ≤ *ℓ* ≤ *j*. Thus, it holds that *T*[*vj , d* − 1] ≤ |*F* ′ \ *F* ′′ *R*| as *T*[*vj , d* − 1] was computed correctly by assumption. Note further that *F* ′′ *R* is by defnition equal to *C*[*S*[*vj , d* − 1]*, vi , vj* ] and

$$|T[v\_j, d-1] + |C[v\_h, v\_j, v\_i]| \geq \min\_{j' \leq i} \{ T[v\_j', d-1] + |C[S[v\_j', d-1], v\_j', v\_i]| \}.$$

Thus, *c* = |*F* ′ | = |*F* ′ \ *F* ′′ *R*| + |*F* ′′ *R*| ≥ *T*[*vj , d* − 1] + |*C*[*vh, vj , vi* ]| ≥ *T*[*vi , d*], a contradiction.

Finally, assume towards a contradiction that *S*[*vi , d*] is computed incorrectly but *T*[*vi , d*] is computed correctly. Since *T*[*vi , d*] is computed correctly, there is a set *F* ′ of *T*[*vi , d*] edges such that in *H* = (*V* ′ *, E*′ \ *F* ′ ) it holds for all *k* ≤ *ℓ* ≤ *i* that dist*H*(*s, vk*) ≤ dist*H*(*s, vℓ*) and for all *j* ≥ *i* that dist*H*(*s, vj* ) ≥ *d*. Then, there is a vertex *vj* such that dist(*s, vℓ*) ≤ *d*−2 for all *ℓ < j* and dist(*s, vr*) ≥ *d*−1 for all *r* ≥ *j*. Let, without loss of generality, *F* ′ be a set of edges such that there is no edge set *F* ′′ with the same property as described above

where the respective vertex *vj* ′ satisfes *j* ′ *< j*. Let *S*[*vi , d*] = *vh*. We show that *h* = *j*. If *j < h*, then *T*[*vh, d* − 1] + |*C*[*S*[*vh, d* − 1]*, vh, vi* ]| *< T*[*vi , d*] as otherwise *h* would have been chosen smaller. This, however, contradicts the assumption that *T*[*vi , d*] is computed correctly. If *j > h*, then by defnition, *T*[*vi , d*] = *T*[*vh, d* − 1] + |*C*[*S*[*vh, d* − 1]*, vh, vi* ]|. Thus, there is a set *F* ′′ such that |*F* ′′| = *T*[*vi , d*] = |*F* ′ | and in *H*′ . .= (*V* ′ *, E*′ \ *F* ′′) it holds for all *k* ≤ *ℓ* ≤ *i* that dist*H*′ (*s, vk*) ≤ dist*H*′ (*s, vℓ*). Moreover, it holds for all *j* ≥ *i* that dist*H*′ (*s, vj* ) ≥ *d*, for all *ℓ < h* that dist*H*′ (*s, vℓ*) ≤ *d* − 2, and for all *r* ≥ *h* that dist(*s, vr*) ≥ *d* − 1. This contradicts the defnition of *F* ′ .

We conclude this prove with analyzing the running time of our algorithm. We frst show how to compute *C*[*vh, vi , vj* ] for all triples (*vh, vj , vi*) of vertices in *O*(*n* 2 · *m*) time. To this end, we frst compute a tables *A*[*vj , vi* ], where

$$A[v\_j, v\_i] := |\{ \{v\_\ell, v\_r\} \in E \mid \ell < j < i \le r\}|.$$

Note that *A* can be computed in *O*(*n* 2 ·*m*) time by iterating over all edges {*vℓ, vr*} (we assume *ℓ < r*) and all entries in *A*[*vj , vi* ] and if *ℓ < j < i* ≤ *r*, then increment the entry. Once *A* is computed, we compute *C*[*vh, vj , vi* ] . .= *A*[*vj , vi* ] − *A*[*vh, vi* ] in constant time per table entry. Since there are *O*(*n* 3 ) table entries, the overall running time for this preprocessing is *O*(*n* 2 · *m*) (note that the input graph is a connected interval graph and hence *O*(*n*) ⊆ *O*(*m*)).

Each table entry *S*[*vi , d*] and *T*[*vi , d*] can be computed in *O*(*n*) time by iterating over at most *n* vertices and computing the sum of a table entry in *T* and the size of a table entry in *C*, thereby keeping track of the minimum value and which iteration led to this minimum. Since there are *O*(*n* · *λ*) table entries, the overall running time is *O*(*n* 2 · *λ*). As we may assume that *λ < n* (each path has length at most *n*), the running time is bounded by *O*(*n* 3 ). Lastly, computing the solution takes *O*(*n*) time as we have to iterate over up to *n* neighbors *vi* of *t* and for each we have to compute |{*vℓ* | *ℓ < i* ∧ {*vℓ, t*} ∈ *E*}|. This computation takes constant time as we can compute the smallest index *j* of a vertex that is adjacent to *t* in *G* and then compute *i* − *j* + 1. Thus, the overall running time for our algorithm is *O*(*n* 2 · *m*).

The main point in the proof of Theorem 4.4 where we need to assume that the input graph is a proper interval graph and not an interval graph is the application of Lemma 4.2. In the following section, we will investigate problems arising when trying to adapt Lemma 4.2 for interval graphs. Concluding this section, we want to emphasis the way the solution is computed in the proof of Theorem 4.4 once the tables *T* and *S* are completely flled. Rather than looking

at a single entry or taking the maximum or minimum entry in a given column, we iterate over all entries with *d* = *λ* in *T*[*vi , d*] and add to it the number of neighbors *vj* with *j < i* of *t*. The solution is then corresponding to the minimum such sum. This way of fnding a solution goes to show that each of the four guiding questions (even the one that looks the simplest) can have a surprising or non-trivial answer.

## **4.3 Falsifying Assumptions for Interval Graphs**

In this section, we discuss some problems that arise when trying to adapt the algorithm behind Theorem 4.4 for interval graphs. The only diference between interval graphs and proper interval graphs is that in interval graphs there can be pairs (*v, w*) of vertices such that *N*[*v*] ⊂ *N*[*w*]. Intuitively, it does not seem to make sense to remove an edge {*u, v*} while leaving an edge {*u, w*} in the solution graph as each shortest *s*-*t*-path containing *v* and using the edge {*u, v*} can then be replaced by a path containing *w* and {*u, w*}. This leads to the following conjecture.

**Conjecture 4.5.** *Let G* = (*V, E*) *be an interval graph and let F be a set of edges. Let d be the distance from s to t in G*′ = (*V, E* \ *F*)*. Then, there is a set F* ′ *of edges with* |*F* ′ | ≤ |*F*| *such that for G*′′ *. .*= (*V, E* \ *F* ′ ) *it holds that* dist*G*′′ (*s, t*) ≥ *d and for each v, w* ∈ *V* \ {*s, t*} *with N*[*v*] ⊂ *N*[*w*] *it holds that if* {*u, v*} ∈ *F* ′ *for some u* ∈ *V , then also* {*u, w*} ∈ *F* ′ *.*

Conjecture 4.5 would be helpful to show that Lemma 4.2 also holds for interval graphs. Unfortunately, Conjecture 4.5 is false as shown in the example in Figure 4.3. Therein, the only solution for removing three edges deletes some edges incident to *w* and one edge incident to *v* such that the only remaining path between *s* and *t* passes through both *v* and *w*. A next natural conjecture could be that a similar approach to the dynamic program behind Theorem 4.4 could still work, where we order the vertices by their *b*- or their *f*-values.

**Conjecture 4.6.** *Let G* = (*V, E*) *be an interval graph and let F be a set of edges. Let d be the distance from s to t in G*′ *. .*= (*V, E* \ *F*)*. Let Fb and Ff be sets of minimum size such that Gb . .*= (*V, E* \ *Fb* ) *and Gf . .*= (*V, E* \ *Ff* ) *fulfll* dist*Gb* (*s, t*) ≥ *d,* dist*Gf* (*s, t*) ≥ *d, and the following. For each v, w* ∈ *V* \ {*s, t*} *it holds that if bv < bw, then* dist*Gb* (*s, v*) ≤ dist*Gb* (*s, w*)*. Moreover, if fv < fw, then* dist*Gf* (*s, v*) ≤ dist*Gf* (*s, w*)*. Then,* |*Fb* | ≤ |*F*| *or* |*Ff* | ≤ |*F*|*.*

**Figure 4.3:** An interval graph and its interval representation. The dashed edges show the unique solution for Length-Bounded Cut with *β* = 3 and *λ* = 5. Note that *N*[*v*] ⊂ *N*[*w*], that the edge {*u, v*} is dashed, and that the edge {*u, w*} is not. Since the dashed edges are the only solution, Conjecture 4.5 is false.

**Figure 4.4:** An interval graph and its interval representation. The dashed edge is the unique solution for Length-Bounded Cut with *β* = 1 and *λ* = 5. Let *G* ′ denote the graph without the dashed edge. Note that it holds in *G* ′ that dist*G*′ (*s, u*) *<* dist*G*′ (*s, x*) = dist*G*′ (*s, y*) *<* dist*G*′ (*s, v*) but *bv < by* and *fu < fx*. Note further that the dashed edge is the only edge whose removal increases the distance between *s* and *t* and hence Conjecture 4.6 is false.

Again, Conjecture 4.6 is false as shown in Figure 4.4. The idea behind this counterexample is to include short intervals with only two neighbors that prevent any reordering of their neighbors after the removal of some edges. This shows that the basic idea of our algorithm for proper interval graphs cannot work for interval graphs as we cannot order the vertices by their *b*- or their *f*-values for the dynamic program. Moreover, note that the dashed edge in Figure 4.4 is the only solution and that after removing this edge, the resulting graph contains a *C*4 induced by the vertices *u, x, v* and *y*. Thus, we cannot even assume that removing a solution from the input interval graph yields an interval graph. This is in contrast to Theorem 4.4 where the graph resulting from removing a solution from the input proper interval graph is again a proper interval graph.

# **4.4 Concluding Remarks**

In this chapter, we studied Length-Bounded Cut in the special case where the input graph is a proper interval graph and showed polynomial-time solvability. This confrms a conjecture by Bazgan et al. [Baz+19]. A natural next step is to investigate interval graphs. We showed some limitations for adapting our approach from proper interval graphs to interval graphs. We still conjecture that Length-Bounded Cut on interval graphs should allow for a polynomial-time algorithm.

Bazgan et al. [Baz+19] provide a hierarchy of parameters with known results and open problems for Length-Bounded Cut. In the paper on which this chapter is based, we solved some of their open problems [BHK20]. Tackling the remaining ones is left as a challenge for future research.

# **Chapter 5**

### **Disjoint Shortest Paths**

This is the fnal chapter in the dynamic-programming part of the thesis. With regards to content, our main contribution in this chapter is an *XP*-algorithm for the *NP*-hard *k*-Disjoint Shortest Paths problem. This is a variant of the fundamental and well-studied combinatorial problem *k*-Disjoint Path. On a conceptual level, we will complete our journey through the intricacies of dynamic programming. For the dynamic program we develop in this chapter, there is a very simple way of computing each table entry. However, when we consider a natural generalization of our problem, then this way is not feasible any more. Further investigating the generalization yields another way of computing each table entry that will turn out to be much more efcient even for the special case we are mainly interested in.

*k*-Disjoint Path describes the question of whether there are *k* pairwise disjoint1 paths between vertex terminal pairs (*si , ti*)*i*∈[*k*] in a given undirected graph *G*. Karp [Kar75] showed that the problem is *NP*-hard when *k* is part of the input. On the positive side, Robertson and Seymour [RS95] provided an algorithm running in *O*(*n* 3 ) time for any constant *k*. Later, Kawarabayashi et al. [KKR12] improved the running time to *O*(*n* 2 )—again for fxed *k*. On directed graphs, in contrast, the problem is NP-hard even for *k* = 2 [FHW80]. However, on directed acyclic graphs (DAGs), the problem becomes again polynomial-time solvable for constant *k* [FHW80].

We study a variant called *k*-Disjoint Shortest Paths. Therein, all paths in a sought solution have to be shortest paths between the respective terminal pairs. This problem has applications in transportation networks, circuit layout, and circuit routing (see e. g. the work by Kawarabayashi et al. [KKR12] and

1Here and in the following this means vertex-disjoint.

references therein) and its complexity for constant *k* has been a long-standing open problem [Eil98, Fom+19]. Very recently, Lochet [Loc21] settled this question by showing that *k*-Disjoint Shortest Paths can be solved in *n O* ( *k* 5 *k* ) time, that is, polynomial time for every constant *k*. We provide a new approach with a novel geometric perspective that simplifes many arguments and leads to an overall streamlined algorithm with a running time of *O*(*k* · *n* 16*k*·*k*!+*k*+1). Notably, *k*-Disjoint Shortest Paths is *W[1]*-hard with respect to *k* and, assuming the ETH, there is no *f*(*k*) · *n o*(*k*) -time algorithm for *k*-Disjoint Shortest Paths [Ben+21]. The asymptotic gap between the lower bound of *n o*(*k*) and our upper bound of *n O*((*k*+1)!) is, however, still quite large.

We formalize our novel geometric view for *k*-Disjoint Shortest Paths and provide some structural observations regarding solutions to *k*-Disjoint Shortest Paths in Section 5.2. In Section 5.3, we present a dynamic-programmingbased approach to solve a special case of *k*-Disjoint Shortest Paths. Afterwards, we provide our algorithm for the general problem that uses the dynamic program as a subprocedure and prove our main theorem.

### **5.1 Problem Defnition and Related Work**

*k*-Disjoint Shortest Paths is defned as follows.

*k*-Disjoint Shortest Paths

**Input:** An undirected graph *G* = (*V, E*) and *k* pairs (*si , ti*)*i*∈[*k*] of vertices.

**Question:** Are there *k* disjoint paths *Pi* such that, for each *i* ∈ [*k*], *Pi* is a shortest *si*-*ti*-path?

Eilam-Tzoref [Eil98] introduced this variant of *k*-Disjoint Path, showed that it is *NP*-hard when *k* is part of the input, and provided a dynamic-programmingbased *O*(*n* 8 )-time algorithm for 2-Disjoint Shortest Paths. This was later improved to an *O*(*n* 2*m*)-time algorithm [Ben+21]. The *O*(*n* 8 )-time algorithm for 2-Disjoint Shortest Paths works for positive edge lengths and, recently, Gottschau et al. [GKW19] and Kobayashi and Sako [KS19] independently extended this result by providing polynomial-time algorithms for the case where the edge lengths are non-negative. Concerning directed graphs, Bérczi and Kobayashi [BK17] provided a polynomial-time algorithm for positive edge lengths for 2-Disjoint Shortest Paths. Note that setting all edge length to zero results in 2-Disjoint Path on directed graphs, which is *NP*-hard [FHW80]. Extending the problem to fnding two disjoint *si*-*ti*-paths of minimal total length

(in undirected graphs), Björklund and Husfeldt [BH19] provided an *O*(*n* 11)-time randomized algorithm. Finally, Tragoudas and Varol [TV96] showed that it is *NP*-hard to decide whether the number of solutions of an instance of 2-Disjoint Paths is at least some given threshold.

### **5.2 A Geometric View on Shortest Paths**

In this section, we delineate our geometric perspective on *k*-Disjoint Shortest Paths, make some structural observations, and give a characterization of solutions with regard to their geometry. In the following sections, we will then use these observations to design a dynamic-programming-based algorithm for *k*-Disjoint Shortest Paths. We start with some basic intuition and a small example. In Subsection 5.2.1 we then formalize the geometry-based ideas and provide a characterization of solutions for 2-Disjoint Shortest Paths. In Subsection 5.2.2 we then generalize this characterization to solutions of *k*-Disjoint Shortest Paths.

For the geometric representation, we defne a *k*-dimensional vector2 #»*v* for each vertex *v*. The *i* th coordinate of this vector is the distance between *si* and *v*. An example of this vector representation is given in Figure 5.1. Note that there can be multiple vertices with the same vector. The geometric perspective is based on the following two observations. First, since each path *Pi* = (*v i* 0 *, vi* 1 *, . . . , vi di* ) in the sought solution is a shortest *si*-*ti*-path, it holds for each *j* ∈ [*di* ] that dist(*si , vi j* ) = dist(*si , vi j*−1 ) + 1, that is, the path *Pi* is strictly monotone in the *i* th coordinate. We say that paths which are strictly monotone in the *i* th coordinate have *color i*. Second, for each vertex *v i j* in *Pi* , it holds that dist(*si , ti*) = dist(*si , vi j* ) + dist(*v i j , ti*). Thus, any vertex *w* with dist(*si , ti*) ̸= dist(*si , w*) + dist(*w, ti*) cannot be part of a shortest *si*-*ti*-path. We can formulate this into a necessary (but not sufcient) condition in terms of our geometric perspective as follows. Consider the *k*-dimensional hyperrectangle that has the vectors of *si* and *ti* as two corners and whose sides form an angle of 45◦ with the coordinate axes. We say that this hyperrectangle is *spanned* by *si* and *ti* . The (hyper)rectangle spanned by *s*1 and *t*1 in the right-hand side of Figure 5.1 is highlighted in gray. We will prove that any vertex whose vector is not within the area of this hyperrectangle cannot be part of a shortest *si*-*ti*path. Moreover, if we consider any vertex *v i j* in *Pi* and the two hyperrectangles

2We use the term vector interchangeably with the point the vector is pointing to.

**Figure 5.1:** *Left side:* A simple, undirected graph with four distinguished vertices *s*1, *s*2, *t*1, and *t*2. The vectors with the distances to each *si* are written next to the vertices. Two disjoint shortest paths are highlighted.

*Right side:* A two-dimensional coordinate system. Each vertex is represented at its vector and edges are drawn as lines between their respective end points. When multiple vertices share the same vector, then vertices are depicted close to their actual vector. The rectangle spanned by *s*1 and *t*1 is drawn in gray. The two disjoint shortest paths are again depicted. Note that the *s*1-*t*1-path is going strictly monotone to the right and the *s*2-*t*2-path is strictly monotone going down.

spanned by *vi j* and either *si* or *ti*, then it holds that the vector of each vertex in *Pi* is contained in the area of these two hyperrectangles.

We use these two observations as follows. Assume that there is a solution (a set of pairwise disjoint shortest *si*-*ti*-paths (*Pi*)*i*∈[*k*]). We will show that each path *Pi* can be split into *ℓi* subpaths *P*1 *i , P*2 *i , . . . , Pℓi i* such that

	- subpaths in the same part of the partition share a common color and
	- for two subpaths *Pj i* and *Pq p* in diferent parts of the partition, it holds that the areas of the hyperrectangles spanned by the end vertices of *Pj i* and *Pq p* , respectively, are disjoint.

Our algorithm works in two phases. In the frst phase, we *guess*3 the end vertices of each of the described subpaths (we call the end vertices *marbles*). In the second phase, we compute the described partition and solve *k*-Disjoint Shortest Paths independently for each part of the partition. For each part of the partition, there is a color *c* that all subpaths in this part have. We assume that each subpath in this part is strictly increasing in its *c*-coordinates as we can otherwise swap the two endpoints. We then ignore all edges that are not monotone in *c* (the two endpoints of the edge have the same *c*-coordinate) and direct the edges so that they are pointing towards the higher *c*-coordinate. Note that the resulting graph is a DAG and since each subpath is strictly increasing in its *c*-coordinates, the directed version of each subpath is still contained in the constructed DAG. Hence, we can use the algorithm of Fortune et al. [FHW80] for *k*-Disjoint Shortest Paths on DAGs to fnd pairwise disjoint shortest subpaths. We then also present our own dynamic program for *k*-Disjoint Shortest Paths on DAGs and, as Fortune et al. [FHW80] only state *n O*(*k*) time, provide a precise running-time analysis.

We remark that Lochet [Loc21] used the same two-step approach but how these steps are achieved is diferent. In particular, he does not use a geometric view on shortest paths (as we do). As a result, even for *k* = 2 he can only upper-bound the number of vertices his algorithm has to guess to ensure that no two parts can intersect by 9 91 ([Loc21, Lemma 13]) while our approach produces at most fve parts. Moreover, our geometric view allows us to use a more efcient way of splitting the paths for general *k* (in *O*((*k* + 1)!) parts instead of *O*(*k* 5 *k* ) as done by Lochet).

We continue with some intuition for the described subpaths and the partition of them. We start with the two-dimensional case and distinguish between four cases. Figure 5.2 gives an overview over these cases and the vertices (the marbles) we guess in each case. It is easy to see that only in the case in the top right-hand corner the areas of two subpaths intersect (the dashed line). However, in this area both paths are strictly monotone in both coordinates. Thus, the depicted marbles ensure in each case that a partition as described exists.

We continue with the case where *k >* 2. The basic idea is to recursively partition the paths by considering two-dimensional projections of the respective hyperrectangles. Note that if these projections are disjoint, then also the areas

3Whenever we pretend to guess something, we mean that we iterate over all possible choices and consider for the explanation or proof the respective correct iteration.

**Figure 5.2:** The four cases for the two-dimensional projection of two paths *P*1 and *P*2. The thick black lines represent *P*1 and *P*2 and the colored rectangles are the ones spanned by the respective terminals and marbles. For easier distinction, we colored everything related to the *s*1-*t*1-path red and related to the *s*2-*t*2-path blue (except for the respective paths themselves). A black square represents a vector on which we guessed a marble on both paths. The dashed line represents the subpaths of *P*1 and *P*2 that have a common color.

(top left-hand corner): The lines cross in one point with non-integer coordinates.

(top right-hand corner): The lines cross in at least one point with integer coordinates. (bottom left-hand corner): The rectangles defned by *si* and *ti* intersect (in the gray (darker) area), but the lines do not.

(bottom right-hand corner): The rectangles defned by *si* and *ti* do not intersect.

of the respective hyperrectangles are disjoint. For each pair (*Pi, Pj* ) of paths, we start with the orthogonal projection to the coordinates *i* and *j*. This yields a set of marbles for *Pi* and *Pj* such that the respective subpaths either have colors *i* and *j* or cannot interfere with the respective other path. Assume that we guessed for each two-dimensional (*i, j*)-projection the intersection of *Pi* and *Pj* in this projection. Unfortunately, we cannot partition the respective subpaths as

stated above. Instead, we store for each subpath *P* ′ *i* of *Pi* the set Φ of all colors that *P* ′ *i* has and recursively refne these subpaths until a partition as stated is possible. Roughly speaking, we check for each pair of subpaths whether the areas of their respective hyperrectangles intersect and if they do, then we fnd a two-dimensional projection and use this to fnd new marbles. The resulting subpaths are then either disjoint from the respective other path or have an additional color. We continue this procedure until the areas of any two subpaths with diferent colors are disjoint. These subpaths are then partitioned by their respective sets of colors. Note that by construction diferent subpaths in one part of the partition share a common color and the areas of the hyperrectangles spanned by the end vertices of two subpaths in diferent parts of the partition are disjoint.

In Subsection 5.2.1 we formalize the geometry-based ideas and provide a characterization of solutions for 2-Disjoint Shortest Paths. In Subsection 5.2.2 we generalize this characterization to solutions of *k*-Disjoint Shortest Paths.

### **5.2.1 Two Shortest Paths**

We now formalize and generalize the idea behind the geometric view (visualized in Figures 5.1 and 5.2). We start with some notation for projections. For any ∅ ⊂ *I* ⊆ [*k*] and any vector *x* ∈ R*k* , we denote with *x I* ∈ R|*I*| the orthogonal projection of *x* to the coordinates in *I*. That is, *x I* is the |*I*|-dimensional vector obtained by deleting all dimensions in *x* that are not in *I*. We usually drop the brackets in the exponent, thus writing e. g. (5*,* 6*,* 7*,* 8*,* 9)1*,*3*,*4 . .= (5*,* 7*,* 8) or (5*,* 6*,* 7)2 . .= (6). Similarly, for *R* ⊆ R*k* we defne *RI* . .= {*x I* | *x* ∈ *R*} ⊆ R|*I*| .

We associate with each vertex *v* ∈ *V* a vector in the *k*-dimensional Euclidean vector space. Formally, #»*v* . .= (#»*v i* )*i*∈[*k*] . .= (dist(*si , v*))*i*∈[*k*] ∈ N*k* and for *U* ⊆ *V* we use #»*U* . .= { #»*u* | *u* ∈ *U*} to denote the set of all vectors of vertices in *U*. For a given instance of *k*-Disjoint Shortest Paths, one can compute the vector of each vertex in *O*(*km*) time by performing a breadth-frst-search from each vertex *si* .

We use the following notations for any non-empty index set *I* ⊆ [*k*] in order to compare vectors of vertices *v, w* or sets *V, W* of vertices:

$$\begin{aligned} v \simeq^I w &\iff \forall c \in I. \ \overleftrightarrow{v}^c \simeq \overleftrightarrow{w}^c &\text{for } \simeq \in \{<, \le, =, \ge, >\}, \text{ and} \\ V \simeq^I W &\iff \{\overleftrightarrow{v}^I \mid v \in V\} \simeq \{\overleftrightarrow{w}^I \mid w \in W\} &\text{for } \simeq \in \{\subset, \le, =, \ge, \supset\}. \end{aligned}$$

We further write *x* ∈ *I X* if there is an *x* ′ ∈ *X* with *x* ′ =*I x* and *x /*∈ *I X* otherwise.

**Lemma 5.1.** *For any pair of vertices v, w* ∈ *V , we have* ∥ #»*v* − #»*w*∥∞ ≤ dist(*v, w*)*.*

*Proof.* Let *P* be a shortest *v*-*w*-path. Each edge {*p, q*} in *P* fulflls ∥ #»*p* − #»*q* ∥∞ ≤ 1 as | dist(*si , p*) − dist(*si , q*)| ≤ 1 for each vertex *si* . Thus, by the triangle inequality, ∥ #»*v* − #»*w*∥∞ ≤ ∑ *a*∈*A*(*P* ) 1 = dist(*v, w*).

For two vertices *u, w* ∈ *V* , let

$$u \diamond w := \{ v \in V \mid \text{dist}(u, v) + \text{dist}(v, w) = \text{dist}(u, w) \}$$

be the set of all vertices that lie on a shortest *u*-*w*-path. Similarly, for any *x, y* ∈ N*k* , let

$$x \diamond y := \{ z \in \mathbb{R}^k \mid ||x - z||\_{\infty} + ||z - y||\_{\infty} = ||x - y||\_{\infty} \}$$

be the hyperrectangle spanned by *x* and *y* (whose sides form an angle of 45◦ with the coordinate axes (see Figure 5.1)). We continue with a formal defnition of *colors*.

**Defnition 5.1.** Let *s, t* be two vertices and let *P* be a shortest *s*-*t*-path. The pair (*s, t*) and the path *P* are *colored* if dist(*s, t*) = ∥ #»*s* − #»*t* ∥∞. Let

$$C(P) := C(s, t) := \{ c \in [k] \mid |\overleftarrow{s}^{\succ c} - \overrightarrow{t}^{\succ c}| = ||\overrightarrow{s} - \overrightarrow{t}^{\succ}||\_{\infty} \}.$$

be the set of all colors of *P*. The pair (*s, t*) and the path *P* are *c-colored* for each *c* ∈ *C*(*s, t*).

Note that this defnition of a *c*-colored path is equivalent to saying that *P* is strictly monotonous in its *c*-coordinates. Note further that for arbitrary *u, w* ∈ *V* we do *not* always have # » *u* ⋄ *w* ⊆ #»*u* ⋄ #»*w*, that is, the vectors of all vertices on a shortest *u*-*w*-path are not necessarily contained in the set of vectors "spanned" by #»*u* and #»*w*. However, this inclusion holds for colored vertex pairs as shown next.

**Lemma 5.2.** *Let v, w* ∈ *V be a b-colored pair. Then,* # » *v* ⋄ *w* ⊆ #»*v* ⋄ #»*w.*

*Proof.* Without loss of generality *v* ≤*b w*. Let *u* be an arbitrary vertex in *v* ⋄ *w*. Then, dist(*v, w*) = dist(*v, u*) + dist(*u, w*). Defnition 5.1 and Lemma 5.1 yield

$$
\Box^b = \overline{v}^b + \text{dist}(v, w) = \overline{v}^b + \text{dist}(v, u) + \text{dist}(u, w) \ge \overline{u}^b + \text{dist}(u, w) \ge \overline{w}^b.
$$

Hence, #»*u b* = #»*v b* + dist(*v, u*) and #»*w b* = #»*u b* + dist(*u, w*). Lemma 5.1 then states that dist(*v, u*) = ∥ #»*v* − #»*u*∥∞ and dist(*u, w*) = ∥ #»*v* − #»*u*∥∞. Hence,

$$\|\|\vec{v} - \vec{w}\|\|\_{\infty} = \text{dist}(v, w) = \text{dist}(v, u) + \text{dist}(u, w) = \|\|\vec{v} - \vec{w}\|\|\_{\infty} + \|\|\vec{u} - \vec{w}\|\|\_{\infty}.$$

This leads to #»*u* ∈ #»*v* ⋄ #»*w* and thus # » *v* ⋄ *w* ⊆ #»*v* ⋄ #»*w*.

Throughout this chapter, we will be particularly interested in two-dimensional projections of areas #»*v* ⋄ #»*w* for some vertices *v* and *w*. Note in this context that ( #»*v* ⋄ #»*w*) *I* = #»*v I* ⋄ #»*w I* . Recall that the area defned by *x* ⋄ *y* for *x, y* ∈ N2 is a rectangle in the plane whose sides form an angle of 45◦ to the coordinate axes. The following lemma lists necessary and sufcient conditions for those rectangles to intersect.

**Lemma 5.3.** *Let x, y, x*ˆ*, y*ˆ ∈ N2 *. Then x* ⋄ *y* ∩ *x*ˆ ⋄ *y*ˆ ≠ ∅ *if and only if all of the following hold:*

$$\{ (iv) \; \min \{ \hat{x}^1 + \hat{x}^2, \hat{y}^1 + \hat{y}^2 \} \le \max \{ x^1 + x^2, y^1 + y^2 \} \dots \} $$

*Proof.* Let *R*1*, R*2 ⊆ R2 be two axis-parallel rectangles defned by the opposite corners *q, r* ∈ R2 and ˆ*q, r*ˆ ∈ R2 . It is easy to see that *R*1 and *R*2 intersect if and only if

Since the intersection of two rectangles is invariant under rotation and scaling, we simply rotate *x*⋄*y* and *x*ˆ ⋄*y*ˆ by 45◦ (and scale it by factor √ 2) by multiplying all vectors with the matrix

$$R = \begin{bmatrix} 1 & -1 \\ 1 & 1 \end{bmatrix}.$$

Now the above characterization for axis-parallel rectangles translates into the conditions stated in the lemma.

**Figure 5.3:** The rectangle *x* ⋄ *y* spanned by two points *x* and *z* in two dimensions and a point *z* ∈ *x* ⋄ *y*. Note that ∥*y* − *x*∥∞ is the vertical distance between *x* and *y*. Lemma 5.4 states that *d*1 ≥ *d*2 and *d*3 ≥ *d*4.

The next lemma states that the distance between *x* and any *z* ∈ *x* ⋄ *y* where *x* and *y* have distance |*y c* −*x c* | is at most |*z c* −*x c* |. Intuitively, this is clear as *x*⋄ *y* is a hyperrectangle whose sides form an angle of 45◦ with the coordinate axes and hence half of its borders exactly defne all points *z* whose distance to *x* is exactly |*z c* − *x c* |. See Figure 5.3 for an illustration.

**Lemma 5.4.** *Let b, c* ∈ [*k*] *and let x, y* ∈ N*k with* ∥*y* − *x*∥∞ = *y c* − *x c . Then, for all z* ∈ *x* ⋄ *y it holds that z c* − *x c* ≥ |*z b* − *x b* | ≥ 0 *and y c* − *z c* ≥ |*y b* − *z b* | ≥ 0*.*

*Proof.* By assumption and the defnition of *x* ⋄ *y*, it holds that

$$\begin{aligned} \|y^c - x^c = \|y - x\|\_\infty &= \|y - z\|\_\infty + \|z - x\|\_\infty \\ &\ge |y^c - z^c| + |z^c - x^c| \ge (y^c - z^c) + (z^c - x^c) \\ &= y^c - x^c. \end{aligned}$$

Thus, we have equality everywhere, in particular *y c* − *z c* = ∥*y* − *z*∥∞ ≥ |*z b* − *x b* | and *z c* − *x c* = ∥*z* − *x*∥∞ ≥ |*y b* − *z b* | (as shown by the equality between the last term in the frst row and the frst term in the second row).

We next formalize the lines we used in Figure 5.1 to connect the vectors of vertices in a path. To this end, for any path *P* = (*v*1*, v*2*, . . . , vi*) we defne *ζ*(*P*) ⊂ R*k* as the piecewise linear curve connecting the points of #»*P* in the

order given by *P*. Recall that *C*(*P*) denotes the set of all colors *a* such that *P* is *a*-colored. The next observation states that *ζ*(*P*) *C*(*P* ) is a straight line, which is equivalent to the statement that *P* is strictly monotone in each coordinate in *C*(*P*).

**Observation 5.5.** *Let P be a colored path. Then ζ*(*P*) *C*(*P* ) *is a straight line segment.*

*Proof.* Let *ℓ* . .= ∥ # »*sP* − # »*tP* ∥∞ and *k* ′ . .= |*C*(*P*)|. The path *P* contains exactly *ℓ* edges, each of which has an Euclidean length of at most √ *k* ′ in the projection *ζ*(*P*) *C*(*P* ) . Thus the length of *ζ*(*P*) *C*(*P* ) is at most *ℓ* · √ *k* ′ which is exactly the Euclidean distance between # »*sP C*(*P* ) and # »*tP C*(*P* ) .

As a consequence of Observation 5.5, the intersection of two paths *P, Q* in the (*C*(*P*) ∪ *C*(*Q*))-projection is also a straight line segment with an angle of 45◦ to the coordinate axes as shown in Figure 5.1 (right side) and Figure 5.2 (top right).

**Lemma 5.6.** *Let P and Q be two colored paths, and C* ⊆ *C*(*P*) ∪ *C*(*Q*)*. Then ζ*(*P*) *C* ∩ *ζ*(*Q*) *C is a (possibly empty) straight line segment.*

*Proof.* For the sake of notation, we assume that *C* = [|*C*|]. Note that *ζ*(*Pa*) and *ζ*(*Pb*) are piecewise linear curves. Moreover, according to Lemma 5.2 for any two points *x, y* ∈ *ζ*(*P*), it holds that ∥*x* − *y*∥∞ = |*x c* − *y c* | for all *c* ∈ *C*(*P*) and ∥*x* ′ − *y* ′∥∞ = |*x* ′*b* − *y* ′*b* | for any two points *x* ′ *, y*′ ∈ *ζ*(*Q*) and all *b* ∈ *C*(*Q*). So, for *x, y* ∈ R*k* with *x C , yC* ∈ *ζ*(*P*) *C* ∩ *ζ*(*Q*) *C* , it follows that

> |*x c* − *y c* | = ∥*x* − *y*∥∞ = |*x b* − *y b* |

for all *c* ∈ *C* ∩ *C*(*P*) and all *b* ∈ *C* ∩ *C*(*Q*). Thus, *C*(*x, y*) ⊇ *C* and the claim follows from Observation 5.5.

Note that even if *ζ*(*P*) *C*(*P* )∪*C*(*Q*) ∩ *ζ*(*Q*) *C*(*P* )∪*C*(*Q*) is non-empty, then it does not need to contain points from N|*C*(*P* )∪*C*(*Q*)| as can be seen in the top left example in Figure 5.2.

The following defnition starts to formalize the notion of marbles, that is, the special vertices in the diferent cases in Figure 5.2. We start with the two cases in which the lines of *P* and *Q* cross (the upper two).

**Defnition 5.2.** Let *P, Q* be two colored paths, let *b* ∈ *C*(*P*), and let *c* ∈ *C*(*Q*). The paths *P* and *Q* are *b, c-crossing* if the intersection

$$X := \zeta(P)^{b,c} \cap \zeta(Q)^{b,c}$$

is non-empty and they are *b, c-non-crossing* otherwise.

If #»*P b,c* ∩ *X* ≠ ∅, then we defne *α b,c P* (*Q*) and *ω b,c P* (*Q*) to be the frst and last vertex *v* of *P* with *v b,c* ∈ *X*. If #»*P b,c* ∩ *X* only contains non-integer coordinates, then *α b,c P* (*Q*) . .= *ω b,c P* (*Q*) . .= ⊥. We further defne *∂ b,c P* (*Q*) and *ϖ b,c P* (*Q*) to be the last vertex before and the frst vertex after that intersection. If #»*P b,c* ∩ *X* = ∅, then *α b,c P* (*Q*) . .= *ω b,c P* (*Q*) . .= *∂ b,c P* (*Q*) . .= *ϖ b,c P* (*Q*) . .= ⊥.

Regarding notation, we will use *αP* instead of *α b,c P* (*Q*) (and the same for *ω, ∂*, and *ϖ*) if *b*, *c*, and *Q* are clear from the context. Note that the subpaths between the respective *α*- and *ω*-vertices are by Lemma 5.6 straight lines and {*b, c*} colored.

**Observation 5.7.** *If P, Q are two paths with α b,c P* (*Q*) ̸= ⊥*, then*

$$P[\alpha\_P^{b,c}(Q), \omega\_P^{b,c}(Q)] = {}^{b,c}Q[\alpha\_Q^{b,c}(P), \omega\_Q^{b,c}(P)].$$

*In particular, both of these subpaths are b, c-colored.*

It remains to consider the subpaths between *s*- and *α*-vertices and between *ω*and *t*-vertices. By Lemma 5.2 these have to lie in the rectangle areas

$$\overleftrightarrow{s\_P} \diamond \overrightarrow{\partial\_P^{b,c}(Q)}, \overrightarrow{\varpi\_P^{b,c}(Q)} \diamond \overleftrightarrow{t\_P}, \overrightarrow{s\_Q} \diamond \overrightarrow{\partial\_Q^{b,c}(P)}, \text{ and } \overrightarrow{\varpi\_Q^{b,c}(P)} \diamond \overrightarrow{t\_Q}.\tag{5.1}$$

Figure 5.2 (top left-hand corner and top right-right hand corner) suggests that these areas are pairwise disjoint. We will show that this is indeed the case and, to this end, we show the following two observations. The frst one states that the *∂*-vertex on *P* has a *b*-coordinate that is at most the *b*-coordinate of the *∂*-vertex on *Q*, where *b* is the "original" color of *P*. Note that this *∂*-vertex is right before the respective *α*-vertex or before the single crossing point with non-integer coordinates. Since *P* is strictly *b*-monotone, the path *Q* can at most increase or decrease as fast as *P* from the point of intersection.

**Observation 5.8.** *Let P, Q be two b, c-crossing paths with ∂ b,c P* (*Q*) ̸= ⊥*. If P is a subpath of a shortest sb-tb-path and Q is a subpath of a shortest sc-tc-path, then* # » *∂ b,c P* (*Q*) *b* ≤ # » *∂ b,c Q* (*P*) *b and* # » *∂ b,c Q* (*P*) *c* ≤ # » *∂ b,c P* (*Q*) *c .*

*Proof.* Let *z* ∈ *ζ*(*P*) *b,c* ∩ *ζ*(*Q*) *b,c* have minimal *b*-coordinate. Note that

$$\left\| z - \overline{\partial\_P(Q)}^{b,c} \right\|\_{\infty} = \left\| z - \overline{\partial\_Q(P)}^{b,c} \right\|\_{\infty},$$

and since *ζ*(*P*) is strictly increasing in its *b*-coordinate, we can infer that

$$z^b - \overline{\partial\_P(Q)}^b = \left\| z - \overline{\partial\_P(Q)}^{b,c} \right\|\_{\infty} = \left\| z - \overline{\partial\_Q(P)}^{b,c} \right\|\_{\infty} \ge z^b - \overline{\partial\_Q(P)}^b.$$

This yields # » *∂P* (*Q*) *b* ≤ # » *∂Q*(*P*) *b* and the second inequality follows analogously.

The second observation is a simple but useful restatement of Lemma 5.1.

**Observation 5.9.** *Let b, c* ∈ [*k*] *and let* (*v, w*) *be a b-colored pair of vertices with v <b w. Then* #»*w b* − #»*w c* ≥ #»*v b* − #»*v c .*

*Proof.* By Lemma 5.1, #»*w c* − #»*v c* ≤ dist(*v, w*) = #»*w b* − #»*v b* . A simple arithmetic reformulation yields #»*w c* − #»*w b* ≤ #»*v c* − #»*v b* and multiplying both sides with −1 completes the proof.

We are now in the position to prove the statement that the four areas defned in Term (5.1) are pairwise disjoint.

**Lemma 5.10.** *Let P and Q be two b, c-crossing paths. The sets*

$$\left(\overrightarrow{s\_P} \diamond \overrightarrow{\partial\_P^{b,c}(Q)}\right)^{b,c}, \left(\overrightarrow{\varpi\_P^{b,c}(Q)} \diamond \overrightarrow{t\_P}\right)^{b,c}, \left(\overrightarrow{s\_Q} \diamond \overrightarrow{\partial\_Q^{b,c}(P)}\right)^{b,c}, \text{and } \left(\overrightarrow{\varpi\_Q^{b,c}(P)} \diamond \overrightarrow{t\_Q}\right)^{b,c}$$

*are pairwise disjoint (or undefned).*

*Proof.* Without loss of generality, let *P* be *b*-colored, *Q* be *c*-colored, *sP <b tP* , and *sQ <c tQ*. Recall that *sP* and *tP* are the start and end vertices of *P*, respectively. We further assume that all above sets are defned, that is, none of the described end points is ⊥. By Lemma 5.4, for any *x* ∈ # »*sP* ⋄ # »*∂P* and *y* ∈ *ϖ*# » *P* ⋄ # »*tP* it holds that *x* ≤ # »*∂P b < ϖ*# » *P b* ≤ *y b* , and thus ( # »*sP* ⋄ # »*∂P* )*b,c* ∩ ( *ϖ*# » *P* ⋄ # »*tP* )*b,c* = ∅. An analogous argument holds for ( # »*sP* ⋄ # »*∂P* )*b,c* and ( *ϖ*# » *P* ⋄ # »*tP* )*b,c* .

We will now use Lemma 5.3 to show that ( # »*sP* ⋄ # »*∂P* )*b,c* ∩ ( # »*sQ* ⋄ # »*∂Q* )*b,c* = ∅. Since all other remaining cases are analogous, this will conclude the proof. By Observation 5.9, it holds that

$$\max \{ \overrightarrow{s\_P}^b - \overrightarrow{s\_P}^c, \overrightarrow{\partial\_P}^b - \overrightarrow{\partial\_P}^c \} = \overrightarrow{\partial\_P}^b - \overrightarrow{\partial\_P}^c \text{ and }$$

$$\min \{ \overrightarrow{s\_Q}^b - \overrightarrow{s\_Q}^c, \overrightarrow{\partial\_Q}^b - \overrightarrow{\partial\_Q}^c \} = \overrightarrow{\partial\_Q}^b - \overrightarrow{\partial\_Q}^c.$$

Observe that # »*∂P b,c* ̸= # »*∂Q b,c* as otherwise *∂P* would lie on the intersection of *P* and *Q*, a contradiction. Hence # »*∂P b* ≠ # »*∂Q b* or # »*∂P c* ̸= # »*∂Q c* . In the former case, Observation 5.8 states that *∂Q >b ∂P* and in the latter case it states *∂P >c ∂Q*. Hence, # »*∂P c* + # »*∂Q b >* # »*∂P b* + # »*∂Q c* and thus # »*∂P b* − # »*∂P c <* # »*∂Q b* − # »*∂Q c* . *b,c* # »*∂P b,c* # »*∂Q b,c*

Setting *x* = # »*sP* , *y* = , *x*ˆ = # »*sQ b,c*, and *y*ˆ = in Lemma 5.3 then violates condition (ii) and hence ( # »*sP* ⋄ # »*∂P* )*b,c* ∩ ( # »*sQ* ⋄ # »*∂Q* )*b,c* = ∅.

We continue with the defnition of marbles for the cases where the two paths *P* and *Q* are *b, c*-non-crossing. Figure 5.2 shows that even in this case *sP* ⋄ *tP* and *sQ* ⋄ *tQ* in general are not disjoint (bottom left-hand corner). Since the two bottom cases are distinguished by the intersection of *sP* ⋄ *tP* and *sQ* ⋄ *tQ*, we start with a defnition of this intersection.

**Defnition 5.3.** Let *b, c* ∈ [*k*]. Let *P* be a *b*-colored path and let *Q* be a *c*-colored path. The *common b, c-area* of *P* and *Q* is

$$\Delta^{b,c}(P,Q) := (\overrightarrow{s\_P} \diamond \overrightarrow{t\_P})^{b,c} \cap (\overrightarrow{s\_Q} \diamond \overrightarrow{t\_Q})^{b,c}.$$

Note that if ∆*b,c*(*P, Q*) = ∅, then by Lemma 5.2, they do not share vertices with common vectors and hence they do not share common vertices. If ∆*b,c*(*P, Q*) ̸= ∅ and *P* and *Q* are *b, c*-crossing, then we can use Defnition 5.2 to defne the marbles. It hence remains to study the case where ∆*b,c*(*P, Q*) ̸= ∅ and *P* and *Q* are *b, c*-non-crossing. In this case we need at most one marble per path and this marble is defned as follows.

**Defnition 5.4.** Let *P* be a *b*-colored path, *Q* be a *c*-colored path, and let without loss of generality be *sQ <b tQ*.  If *P* ∩ *B* = ∅, then *δ b,c P* (*Q*) = ⊥.

#### **Observation 5.11.** *δ b,c P* (*Q*) *is well-defned.*

*Proof.* Since *P* is strictly monotone in the *b*-coordinate, it can clearly contain at most one point from *B*1 . .= {*v* ∈ *V* | *v* =*b sQ* ∧ *v <c sQ*} and one from *B*2 . .= {*v* ∈ *V* | *v* =*b tQ* ∧ *v >c tQ*}. It remains to show that it cannot intersect both sets. To this end, observe that Lemma 5.4 states for any *b*1 ∈ *B*1 and *b*2 ∈ *B*2 that |*b c* 1 − *b c* 2 | *>* |*s b Q* − *t b Q*| ≥ |*s b Q* − *t b Q*| = |*b b* 1 − *b b* 2 |, and therefore the pair (*b*1*, b*2) is not *b*-colored and thus *P* cannot contain both *b*1 and *b*2.

We next show that if ∆*b,c*(*P, Q*) ̸= ∅ and *P* and *Q* are *b, c*-non-crossing, then at least one of the vertices *δ b,c P* (*Q*) or *δ b,c Q* (*P*) exists. Afterwards we will show that these vertices guarantee that the respective new areas are disjoint.

**Lemma 5.12.** *Let P, Q be two b, c-non-crossing paths with* ∆*b,c*(*P, Q*) ̸= ∅*. Then, δ b,c P* (*Q*) ̸= ⊥ *or δ b,c Q* (*P*) ̸= ⊥*.*

*Proof.* Note that the defnition of ∆*b,c*(*P, Q*) requires that without loss of generality *P* is *b*-colored and *Q* is *c*-colored. We further assume without loss of generality that {*b, c*} = [2] and that *sP <b tP* and *sQ <c tQ*.

Suppose towards a contradiction that *δ b,c P* (*Q*) = *δ b,c Q* (*P*) = ⊥. Since *P, Q* are *b, c*-non-crossing and *δ b,c Q* (*P*) = ⊥, the path *Q* cannot cross the curve

$$\{x \in \mathbb{N}^2 \mid x^c = s\_P \land x^b < s\_P\} \cup \zeta(P)^{b,c} \cup \{x \in \mathbb{N}^2 \mid x^c = t\_P \land x^b > t\_P\}.$$

Since *Q* cannot cross the line, it is located completely on one side of it. Assume without loss of generality that *Q* (and thus in particular *tQ*) is located on the side containing (0*,* 0), that is, for all *v* in *P* and *w* in *Q* with *v b* = *w b* it holds that *v c > wc* .

Then there are three possible cases: *t b Q < sb P* , *t b Q* ∈ [*s b P , tb P* ], or *t b Q > tb P* . Note that in the frst case by Lemma 5.4 it holds for any *z* ∈ ∆*b,c*(*P, Q*) that

$$z^c - t\_Q^c \ge z^b - t\_Q^b > z^b - s\_P^b \ge z^c - s\_P^c,$$

a contradiction to *z* ∈ ( # »*sQ* ⋄ # »*tQ*) *b,c*. In the last case, a similar argument holds with

$$s\_P^b < t\_Q^b - z^b \le t\_Q^c - z^c < s\_P^c - z^c,$$

which is a contradiction to *z* ∈ ( # »*sP* ⋄ # »*tP* ) *b,c*. It remains to analyze the case where *t b Q* ∈ [*s b P , tb P* ]. Note that in this case there is a vertex *p* in *P* with *p b* = *t b Q*. Hence *t c Q < pc* , and *p* ∈ {*v* ∈ *V* | *v* =*b tQ* ∧ *v >c tQ*}. Thus *δ b,c P* (*Q*) = *p* ̸= ⊥, a contradiction.

The next lemma shows that if *P* and *Q* are *b, c*-non-crossing, but they have a common area ∆*b,c* and *δ b,c P* (*Q*) ̸= ⊥, then the area between *sQ* and *tQ* is disjoint from the two areas between *sP* and *δ b,c P* (*Q*) and between *δ b,c P* (*Q*) and *tP* . Hence *δ b,c P* (*Q*) is the last type of marble needed.

**Lemma 5.13.** *Let P be a b-colored path and let Q a c-colored path such that* ∆*b,c*(*P, Q*) ̸= ⊥ *and δ b,c P* (*Q*) ̸= ⊥*. Then,*

$$\left(\overrightarrow{s\_Q} \diamond \overrightarrow{t\_Q}\right)^{b,c} \text{ is } \operatorname{disjoint}\left(\overrightarrow{s\_P} \diamond \overrightarrow{\delta\_P^{b,c}(Q)}\right)^{b,c} \cup \left(\overrightarrow{\delta\_P^{b,c}(Q)} \diamond \overrightarrow{t\_P}\right)^{b,c}$$

*.*

*Proof.* For the sake of readability, we use *δ* . .= *δ b,c P* (*Q*). We will show that

$$\left(\overrightarrow{s\_Q} \diamond \overrightarrow{t\_Q}\right)^{b,c} \cap \left(\overrightarrow{s\_P} \diamond \overrightarrow{\delta}\right)^{b,c} = \emptyset.$$

The proof for ( #»*δ* ⋄ # »*tP* ) *b,c* is then completely analogous. Assume without loss of generality that *δ* =*b tQ* and *δ >c tQ*. Notice that

$$\begin{split} \max \{ \overrightarrow{s\_P}^b - \overrightarrow{s\_P}^c, \overrightarrow{\delta}^b - \overrightarrow{\delta}^c \} &\overset{\text{Obs. 5.9}}{=} \overrightarrow{\delta}^b - \overrightarrow{\delta}^c \\ &< \overrightarrow{t\_Q}^b - \overrightarrow{t\_Q}^c \overset{\text{Obs. 5.9}}{=} \min \{ \overrightarrow{s\_Q}^b - \overrightarrow{s\_Q}^c, \overrightarrow{t\_Q}^b - \overrightarrow{t\_Q}^c \}. \end{split}$$

Setting *x* . .= # »*sP b,c* , *y* . .= #»*δ b,c* , *x*ˆ . .= # »*sQ b,c*, and *y*ˆ . .= # »*tQ b,c* in Lemma 5.3 then yields that condition (ii) is violated and thus ( # »*sP* ⋄ #»*δ* ) *b,c* ∩ ( # »*sQ* ⋄ # »*tQ*) *b,c* = ∅.

We are fnally in the position to defne the set of marbles for a pair of paths. Afterwards we conclude this subsection with the main proposition that states that marbles uniquely classify solutions.

**Defnition 5.5.** Let *P* be a *b*-colored *sP* -*tP* -path and *Q* be a *c*-colored *sQ*-*tQ*path. The set of {*b, c*}*-marbles* of *P* with respect to *Q* is

$$\mathcal{M}\_P^{b,c}(Q) := \{ s\_P, t\_P, \mu\_P^{b,c}(Q) \mid \mu \in \{ \alpha, \omega, \partial, \varpi, \delta \} \} \backslash \{ \perp \}.$$

The next proposition states that if there are two diferent solutions and in particular two pairs (*P, Q*) and (*P* ′ *, Q*′ ) of solution paths with the same marbles, then *P* and *Q* share exactly the same vectors as *P* ′ and *Q*′ do. Recall that the shared vectors are a straight line segment and that once their ends are fxed, we can use the dynamic program by Fortune et al. [FHW80] to fnd disjoint paths between these ends.

**Proposition 5.14.** *Let P and P* ′ *be b-colored sP -tP -paths, and let Q and Q*′ *be c-colored sQ-tQ-paths.  Let *R* be the subpath of *P* that starts at *α b,c P* (*Q*) and ends at *ω b,c P* (*Q*) (or *R* = ∅ if *αP* = *ωP* = ⊥). From the defnition of *α* and *ω* and Lemma 5.6, it follows that {*v* ∈ *P* | *v* ∈ *b,c Q*} =*b,c R*. We now consider the two cases whether or not *P* and *Q* are *b, c*-crossing.

If *P* and *Q* are *b, c*-crossing, then by defnition *∂P* ̸= ⊥ and *ϖP* ̸= ⊥. It follows from Lemma 5.2 that the subpaths of *P* ′ from *sP* to *∂P* and from *ϖP* to *tP* use only vectors from # »*sP* ⋄ # »*∂P* and *ϖ*# » *P* ⋄ # »*tP* , respectively. As the analogous statement holds for the corresponding subpaths of *Q*′ , it follows from Lemma 5.10 that all these subpaths do not intersect in the projection to the *b*-*c*-plane. It remains to consider the subpath from *αP* to *ωP* .  Since those two straight line segments have the same ends, they are the same and thus {*v* ∈ *P* ′ | *v* ∈ *b,c Q*′} =*b,c R*.

If *P* and *Q* are *b, c*-non-crossing, then {*v* ∈ *P* ′ | *v* ∈ *b,c Q*′} *b,c* ⊆ ∆*b,c*(*P, Q*) and ∅ = *R*. We consider the two cases ∆*b,c*(*P, Q*) = ∅ and ∆*b,c*(*P, Q*) ̸= ∅. In the former case it holds that

$$\{v \in P \mid v \in^{b,c} Q\} = R = \emptyset = \Delta^{b,c}(P, Q) = \Delta^{b,c}(P', Q') = \{v \in P' \mid v \in^{b,c} Q'\}.$$

In the latter case, by Lemma 5.12 there is a *δ b,c P* (*Q*) ̸= ⊥ or *δ b,c Q* (*P*) ̸= ⊥. Without loss of generality, assume that *δ b,c P* (*Q*) ̸= ⊥. Then, *δ b,c P* (*Q*) ∈ M*b,c P* (*Q*) ⊆ *P* ′ and by Lemma 5.13

$$\begin{split} \left( \overbrace{v \in P' \mid v \in {}^{b,c}Q'}^{b,c} \right)^{b,c} &\subseteq \left( \overbrace{s\_{Q'} \diamond {t\_{Q'}}}^{b,c} \right)^{b,c} \cap \left( (\overbrace{s\_{P'} \diamond {\delta\_{P}^{b,c}(Q)})^{b,c}}^{b,c} \cup (\overbrace{\delta\_{P}^{b,c}(Q)}^{b,c} \diamond \overbrace{t\_{P'}})^{b,c} \right)^{b,c} \\ &= \left( \overbrace{s\_{Q} \diamond {t\_{Q}}}^{b} \right)^{b,c} \cap \left( (\overbrace{s\_{P} \diamond {\delta\_{P}^{b,c}(Q)}}^{b,c} \odot (\overbrace{\delta\_{P}^{b,c}(Q)}^{b,c} \diamond \overbrace{t\_{P}})^{b,c} \right)^{b,c} \\ &= \emptyset. \end{split}$$

Thus, {*v* ∈ *P* ′ | *v* ∈ *b,c Q*′} = ∅ = *R* = {*v* ∈ *P* | *v* ∈ *b,c Q*}.

### **5.2.2 More than Two Shortest Paths**

In the previous subsection, we looked at two shortest paths *P* and *Q* from *sP* to *tP* and *sQ* and *tQ*, respectively. We showed that selecting at most ten vertices from *P* and *Q* (fve per path; see Defnition 5.5) is sufcient to ensure that each pair (*P* ′ *, Q*′ ) of shortest *sP* -*tP* - and *sQ*-*tQ*-paths that also contain these vertices (M*b,c P* (*Q*) and M*b,c Q* (*P*)) "behave" like *P* and *Q* in the sense that *P* ′ and *Q*′ intersect in the same vectors as *P* and *Q* do (see Proposition 5.14). In this subsection, we defne a set C*,* |C| ∈ *O*(*k* · *k*!), that basically ensures the same properties for *k* paths. To formalize our goal for this subsection, we frst introduce the concept of *avoiding* paths which is a generalization of a slightly modifed version of *b, c*-non-crossing paths. The modifcation is to ignore the ends of *P* and *Q* to ensure that we can split paths at certain vertices and still can ensure that these diferent parts are avoiding.

**Defnition 5.6** (*I*-avoiding)**.** Let ∅ ⊂ *I* ⊆ [*k*]. Two paths *P* and *Q* are *Iavoiding* if *p /*∈ *I Q* for each inner vertex *p* of *P* and *q /*∈ *I P* for each inner vertex *q* of *Q*. Two vertex pairs (*sp, tp*) and (*sq, tq*) are *I*-avoiding if

$$(\overrightarrow{s\_p}^{\bullet I} \diamond \overrightarrow{t\_p}^{\bullet I}) \cap (\overrightarrow{s\_q}^{\bullet I} \diamond \overrightarrow{t\_q}^{\bullet I}) \subseteq \{\overrightarrow{s\_p}^{\bullet I}, \overrightarrow{t\_p}^{\bullet I}\} \cap \{\overrightarrow{s\_q}^{\bullet I}, \overrightarrow{t\_q}^{\bullet I}\}.$$

Note that being *I*-avoiding implies being *I* ′ -avoiding for all *I* ′ ⊇ *I*. We use *avoiding* as a shorthand for [*k*]-avoiding. Two paths *P*1 and *P*2 are *internally vertex-disjoint* if neither of them contains an inner vertex of the other path. Avoiding paths are clearly internally vertex-disjoint.

**Observation 5.15.** *Let P, Q be two avoiding paths. Then P is internally vertex-disjoint from Q.*

Moreover, for each pair of avoiding vertex pairs (*s, t*) and (*u, w*), the shortest *s*-*t*- and *u*-*v*-paths are internally vertex-disjoint.

**Lemma 5.16.** *Let* (*s, t*) *and* (*u, w*) *be two colored pairs of vertices. If the pairs* (*s, t*) *and* (*u, w*) *are avoiding, then each shortest s-t-path is internally disjoint from each shortest u-w-path.*

*Proof.* If (*s, t*) and (*u, w*) are avoiding, then by defnition and Lemma 5.2

$$(\overrightarrow{s\_p \diamond t\_p}^{I} \cap \overrightarrow{s\_q \diamond t\_q}^{I}) \subseteq (\overrightarrow{s\_p}^{\star I} \diamond \overrightarrow{t\_p}^{I}) \cap (\overrightarrow{s\_q}^{\star I} \diamond \overrightarrow{t\_q}^{I}) \subseteq \{\overrightarrow{s\_p}^{\star I}, \overrightarrow{t\_p}^{\star I}\} \cap \{\overrightarrow{s\_q}^{\star I}, \overrightarrow{t\_q}^{\star I}\},$$

and thus each shortest *s*-*t*-path and each shortest *u*-*w*-path only intersect in {*s, t*} ∩ {*u, w*} and are therefore internally vertex-disjoint.

With the notation of avoiding pairs, we can formulate our goal for this subsection. To this end, fx a solution P = (*Pi*)*i*∈[*k*] for a given instance (*G,*(*si , ti*)*i*∈[*k*]) of *k*-Disjoint Shortest Paths, that is, *Pi* is the *si*-*ti*-path in the solution. Essentially, we want to partition the paths in P into subpaths and assign a set Φ of *labels* to each subpath (Φ ⊆ [*k*]) such that the following two conditions are satisfed.

Note that (2.) will be the central argument in our algorithm for *k*-Disjoint Shortest Paths. The algorithm guesses the endpoints of these subpaths and based on (2.) the algorithm can then compute the inner vertices of subpaths with diferent label sets independently.

Note that for *k* = 2 the partition of *P*1 and *P*2 along the sets M*b,c P* (*Q*) and M*b,c Q* (*P*) satisfes the above. Each subpath of *Pi , i* ∈ [2], has label *i*. Moreover, the subpaths between the *α*- and *ω*-vertices have both labels 1 and 2. Hence, (1.) above is satisfed. Furthermore, (2.) follows from Proposition 5.14.

We now generalize this to arbitrary constant *k*. The basic idea behind defning a respective set C of marbles is depicted in Figure 5.4. Initially, each path *Pi* has label *i*. Whenever two paths *Pi* and *Pj* in the solution intersect in the (*i, j*)-projection (that is, the respective *α*- and *ω*-vertices are not ⊥), then the subpaths *P* ′ *i* and *P* ′ *j* in the intersection get both labels *i* and *j*. If a third path *P* ′ also intersects with *P* ′ *j* , then we try to use the intersections to move

**Figure 5.4:** The three main lines represent three paths *P*1, *P*2, and *P*3. The small black rectangles represent marbles on the respective path *Pi* and the *j*-colored lines above a path indicate that *Pi* and *Pj* intersect in the (*i, j*)-projection, that is, they contain vertices with vectors that are identical when projected in the (*i, j*)-plane. The paths *P*1 and *P*2 intersect in the (1*,* 2)-projection, *P*2 and *P*3 intersect in the (2*,* 3)-projection, but *P*1 and *P*3 do not intersect in the (1*,* 3)-projection. The subpaths of *P*1 and *P*3 where they intersect with *P*2 in the (1*,* 2*,* 3)-projection are depicted by *α* ′ 1*, ω*′ 1*, α*′ 3*,* and *ω* ′ 3. The colors above each subpath (and also the frst number therein) represent the labels of the respective subpath and the number (or sequence of numbers) display the sequence that led to the respective marbles (end vertices) of this subpath.

the label *i* via path *Pj* to some subpath of *P* ′ . Generalizing this, we consider for each *σ* = (*ℓ*1*, ℓ*2*, . . . , ℓh*) whether label *ℓ*1 could be "transported" from *Pℓ*1 to *Pℓ*2 , from *Pℓ*2 to *Pℓ*3 , and so on until from *Pℓh*−1 to *Pℓh*−1 . While the idea of transporting labels would also work with triples (transport label *a* via path *Pb* to path *Pc*), we do not have any bound on the number of resulting subpaths (as for each triple there might be many such subpaths). The reason for using sequences is that we will show that for each *σ* = (*ℓ*1*, ℓ*2*, . . . , ℓh*) at most one subpath of *Pℓh* can receive label *ℓ*1 via *σ*.

In the following, we use set(*τ* ) . .= {*ℓ*1*, . . . , ℓh*} to denote the set with all entries in a sequence *τ* = (*ℓ*1*, . . . , ℓh*). We next defne the *crossing set* C recursively for each Φ ⊆ [*k*]. This should be seen as the set of marbles of a solution. We will then show a result similar to Proposition 5.14 for arbitrary *k* that then allows us to fnd the desired partition of paths.

**Defnition 5.7.** Let (*G,*(*si , ti*)*i*∈[*k*]) be an instance of *k*-Disjoint Shortest Paths and let P = (*Pi*)*i*∈[*k*] be a solution to this instance, that is, *Pi* is the path between *si* and *ti* in the solution. For each Φ ⊆ [*k*] and each permutation *σ* = (*ℓ*1*, . . . , ℓ*|Φ|) of Φ, we defne the crossing set C *σ* and the endpoints T (*σ*) of intersections as follows.

$$\mathcal{T}(\sigma) := \{ \alpha\_{P\_j}^{i,j}(P\_i), \omega\_{P\_j}^{i,j}(P\_i) \} \text{ and } \mathcal{C}^{\sigma} := \mathcal{M}\_{P\_j}^{i,j}(P\_i) \backslash \{\perp\}.$$

• If |Φ| ≥ 3, then let *σ*start . .= (*ℓ*1*, . . . , ℓ*|Φ|−1) and *σ*end . .= (*ℓ*2*, . . . , ℓ*|Φ|). We denote by *Q* the maximum common subpath of *Pℓ*|Φ|−1 [T (*σ*start)] and *Pℓ*|Φ|−1 [T ((*ℓ*|Φ| *, ℓ*|Φ|−1))]. If T (*σ*start) = {⊥}, T (*σ*end) = {⊥}, or *V* (*Q*) = ∅, then let T (*σ*) . .= C *σ* . .= {⊥}*.* Otherwise, let

$$\begin{aligned} P &:= P\_{\ell|\Phi|}[\mathcal{T}(\sigma\_{\text{end}})], \\ \mathcal{T}(\sigma) &:= \{ \alpha\_P^{\ell\_1,\ell\_{|\Phi|}}(Q), \omega\_P^{\ell\_1,\ell\_{|\Phi|}}(Q) \}, \text{ and} \\ \mathcal{C}^{\sigma} &:= (\mathcal{M}\_P^{\ell\_1,\ell\_{|\Phi|}}(Q) \cup \mathcal{M}\_Q^{\ell\_1,\ell\_{|\Phi|}}(P)) \backslash \{\bot\}. \end{aligned}$$

The set C . .= ⋃ *σ* C *σ* is the *crossing set* of P.

**Observation 5.17.** *Let σ . .*= (*ℓ*1*, . . . , ℓ*|Φ|) *be any permutation of any* Φ ⊆ [*k*]*. If* T (*σ*) ̸= {⊥}*, then*

*In particular, crossing sets and endpoints are well-defned.*

*Proof.* We prove both claims by an induction over |Φ|. For |Φ| = 1, note that T (*σ*) = {*sℓ*1 *, tℓ*1 }. Clearly {*sℓ*1 *, tℓ*1 } ⊆ *Pℓ*1 as these are the ends of *Pℓ*1 and the pair {*sℓ*1 *, tℓ*1 } is by defnition *ℓ*1-colored.

Now assume that both claims hold for all Φ ′ with |Φ ′ | *<* |Φ|. Since T (*σ*) ̸= {⊥}, it holds that T (*σ*) = {*α ℓ*1*,ℓ*|Φ| *P* (*Q*)*, ω ℓ*1*,ℓ*|Φ| *P* (*Q*)}, where

$$Q = P\_{\ell\_{|\Phi|-1}}[\mathcal{T}((\ell\_1, \ell\_2, \dots, \ell\_{|\Phi|-1}))] \cap P\_{\ell\_{|\Phi|-1}}[\mathcal{T}((\ell\_{|\Phi|}, \ell\_{|\Phi|-1}))]$$

if |Φ| ≥ 3 and *Q* = *Pℓ*1 if |Φ| = 2. Note that *V* (*Q*) ̸= ∅ and hence if |Φ| ≥ 3, then by induction hypothesis *Q* ⊆ *Pℓ*|Φ|−1 and *Q* is *c*-colored for each *c* ∈ Φ \ {*ℓ*|Φ|}. If |Φ| = 2, then *Q* = *Pℓ*1 = *Pℓ*|Φ|−1 and *Q* is by defnition *ℓ*1-colored. Thus,

$$\mathcal{T}(\sigma) = \{ \alpha\_P^{\ell\_1, \ell\_{|\Phi|}}(Q), \omega\_P^{\ell\_1, \ell\_{|\Phi|}}(Q) \}$$

is well-defned and hence T (*σ*) ⊆ *Pℓ*|Φ| . Moreover, by Observation 5.7, it holds that T (*σ*) is *c*-colored for each *c* ∈ (Φ \ {*ℓ*|Φ|}) ∪ {*ℓ*|Φ|} = Φ.

Note that Observation 5.17 states that, for each sequence *σ* . .= (*ℓ*1*, ℓ*2*, . . . , ℓ*|Φ|), the set T (*σ*) describes a pair of vertices in *Pℓ*|Φ| . The next lemma states that for any sequence *σ* ′ = (*ℓi , ℓi*+1*, . . . , ℓ*|Φ|) with *i* ≥ 1 it holds that the subpath of *Pℓ*|Φ| between the two vertices in T (*σ*) is a subpath of the one between the two vertices in T (*σ* ′ ), that is, if we add more entries to the front of *σ* ′ , then we get smaller and smaller paths.

**Lemma 5.18.** *Let σ . .*= (*ℓ*1*, ℓ*2*, . . . , ℓ*|Φ|) *be any permutation of any* Φ ⊆ [*k*] *with* |Φ| ≥ 2*. If* T (*σ*) ̸= {⊥}*, then Pℓ*|Φ| [T (*σ*)] ⊆ *Pℓ*|Φ| [T ((*ℓ*2*, ℓ*3*, . . . , ℓ*|Φ|))]*.*

*Proof.* We prove the statement by a case distinction over |Φ|. If |Φ| = 2, then the statement is trivial as T (*σ*) ⊆ *Pℓ*|Φ| by Observation 5.17 and by Defnition 5.7 T ((*ℓ*|Φ|)) = {*sℓ*|Φ| *, tℓ*|Φ| }. If |Φ| ≥ 3, then note that *Pℓ*|Φ| [T (*σ*)] is by defnition of *α*- and *ω*-vertices the maximal subpath *P* of *Pℓ*|Φ| such that there is a subpath

> *Q* ⊆ *Pℓ*|Φ|−1 [T ((*ℓ*1*, ℓ*2*, . . . , ℓ*|Φ|−1))] with *P* = {*ℓ*1*,ℓ*2*,...,ℓ*|Φ|} *Q.*

Analogously, *Pℓ*|Φ| [T ((*ℓ*2*, ℓ*3*, . . . , ℓ*|Φ|))] is the maximal subpath *P* ′ of *Pℓ*|Φ| such that there is a subpath

$$Q' \subseteq P\_{\ell\_{\lfloor \Phi \rfloor - 1}}[\mathcal{T}((\ell\_2, \ell\_3, \dots, \ell\_{\lfloor \Phi \rfloor - 1}))] \text{ with } P' = {}^{\{\ell\_2, \ell\_3, \dots, \ell\_{\lfloor \Phi \rfloor}\}} \ Q'.$$

Since *Q* ⊆ *Q*′ by Defnition 5.7, it also holds that *P* ⊆ *P* ′ .

The next lemma states that when "transporting" the labels via a permutation *σ* = (*ℓ*1*, ℓ*2*, . . . , ℓ*|Φ|), then the intersecting subpath *P* in the target path *Pℓ*|Φ| "agrees" in all coordinates in set(*σ*) with the subpath *Q* of *Pℓ*|Φ|−1 where the label is transported from, that is, *P* =set(*σ*) *Q*.

**Lemma 5.19.** *Let* Φ ⊆ [*k*] *with* |Φ| ≥ 2*. Let σ . .*= (*ℓ*1*, ℓ*2*, . . . , ℓ*|Φ|) *be any permutation of* Φ*. If* T (*σ*) ̸= {⊥}*, then Pℓ*|Φ| [T (*σ*)] =Φ *Q*′ *for some subpath Q*′ *of Q . .*= *Pℓ*|Φ|−1 [T ((*ℓ*1*, ℓ*2*, . . . , ℓ*|Φ|−1))] ∩ *Pℓ*|Φ|−1 [T ((*ℓ*|Φ| *, ℓ*|Φ|−1))]*.*

*Proof.* We will again use induction over |Φ| to prove the claim. For |Φ| = 2, the claim follows from Observation 5.7. For |Φ| ≥ 3, let *σ*start . .= (*ℓ*1*, ℓ*2*, . . . , ℓ*|Φ|−1) and *σ*end . .= (*ℓ*2*, ℓ*3*, . . . , ℓ*|Φ|). By Lemma 5.18, *Pℓ*|Φ| [T (*σ*)] ⊆ *Pℓ*|Φ| [T (*σ*end)] and hence there is by induction hypothesis a subpath

$$R' \subseteq P\_{\ell\_{|\Phi|-1}}[\mathcal{T}(\sigma\_{\text{end}})] \cap P\_{\ell\_{|\Phi|-1}}[\mathcal{T}((\ell\_{|\Phi|}, \ell\_{|\Phi|-1}))]$$

with *Pℓ*|Φ| [T (*σ*)] =set(*σ*end) *R*′ . Furthermore, by Defnition 5.7 T ((*ℓ*1*, ℓ*|Φ|)) ̸= ⊥ and hence by induction hypothesis there is some subpath

$$Q' \subseteq Q \text{ with } P\_{\ell\_h}[\mathcal{T}(\sigma)] =^{\ell\_1, \ell\_h} Q'.$$

Note that *R*′ =*ℓ*|Φ| *Pℓ*|Φ| [T (*σ*)] =*ℓ*|Φ| *Q*′ and that *R*′ and *Q*′ are both subpaths of *Q*. Finally, since *Q* ⊆ *Pℓ*|Φ|−1 [T ((*ℓ*|Φ| *, ℓ*|Φ|−1))] is by Observation 5.17 *ℓ*|Φ| colored and *R*′ =*ℓ*|Φ| *Q*′ , it holds that *R*′ = *Q*′ . Thus, *Q*′ =set(*σ*) *Pℓ*|Φ| [T (*σ*)], which proves the claim.

In Subsection 5.2.1, we defned marbles, that is, specifc vertices of two paths *P, Q* such that when splitting *P* and *Q* at these vertices, then each resulting subpath *P* ′ of *P* and *Q*′ of *Q* fulfll either *P* ′ =*b,c Q*′ or *P* ′ and *Q*′ are avoiding. In this subsection, we generalized the notion of marbles to more than two paths at the expense of restricting them to solution paths. We conclude this subsection with the notion of *marble paths*, the fnal link between marbles and crossing sets that will allow us to guess marbles and then compute shortest paths between them almost independently. By that, we mean that we will defne labels for each subpath between marbles such that paths with diferent labels are avoiding and paths with the same labels have a common color. Afterwards, we will show in Section 5.3 how to compute disjoint paths between marble pairs with a common color.

**Defnition 5.8.** An *i-marble path T* is a set of vertices such that {*si , ti*} ⊆ *T* and for each *u, v* ∈ *T* the pair (*u, v*) is *i*-colored.  A segment is *minimal* if it contains exactly two vertices, and it is *j-colored* if (start(*S*)*,* end(*S*)) is *j*-colored. A path *P follows S* if *P* is *i*-colored, has end vertices start(*S*) and end(*S*), and *S* ⊆ *V* (*P*). Two segments *S* and *S* ′ are *avoiding* if each path *P* that follows *S* and each path *P* ′ that follows *S* ′ are pairwise avoiding. Two marble paths are *avoiding* if all their segments are pairwise avoiding.

Before we state the main result of this section, we will prove a series of lemmata that involve minimal segments of marble paths. The frst one states that adding more vertices to avoiding segments still results in avoiding segments.

 Let S* ′ ⊇ *S and U* ′ ⊇ *U be two segments with*

> start(*S* ′ ) = start(*S*)*,* end(*S* ′ ) = end(*S*)*,* start(*U* ′ ) = start(*U*)*, and* end(*U* ′ ) = end(*U*)*.*

*The segments S* ′ *and U* ′ *are avoiding.*

*Proof.* Assume towards a contradiction that *S* ′ and *U* ′ are not avoiding, that is, there are minimal subsegments *S* ∗ of *S* ′ and *U* ∗ of *U* ′ and paths *P* and *Q* such that *P* follows *S* ∗ and *Q* follows *U* ∗ and *P* and *Q* are not avoiding. Let *S* ′′ be the minimal segment in *S* with

$$\text{start}(S^{\prime\prime}) \le^i \text{start}(S^\*) < \text{end}(S^\*) \le \text{end}(S^{\prime\prime}).$$

Note that *S* ∗ ⊆ *S* ′′. Analogously, let *U* ′′ be the minimal segment in *U* with

$$\text{start}(U'') \le^i \text{start}(U^\*) < \text{end}(U^\*) \le \text{end}(U'').$$

Since *P* follows *S* ∗ , it is *i*-colored and contains all vertices in *S* ∗ . Hence it contains all vertices in *S* ′′ ⊆ *S* ∗ and thus follows *S* ′′. Analogously, *Q* follows *U* ′′ . Hence *S* ′′ and *U* ′′ are not avoiding and thus *S* and *U* are by defnition not avoiding, a contradiction.

The next two lemmata state that segments of marble paths *P* and *Q* defned by vertices in M are avoiding unless the ends of the segment are between the respective *α*- and *ω*-vertices. The frst lemma states that if *α a,b P* (*Q*) = ⊥, then the two marble paths are completely avoiding.

**Lemma 5.21.** *Let* (*sP , tP* ) *be an a-colored pair and let* {*sQ, tQ*} *be a b-colored pair.  If α a,b P* (*Q*) = ⊥*, then the marble paths* M*a,b P* (*Q*) *and* M*a,b Q* (*P*) *are avoiding.*

*Proof.* Note that since *α a,b P* (*Q*) = ⊥, it follows that {*v* ∈ *P* | *v* ∈ *a,b Q*} = ∅. Assume towards a contradiction that there are segments *S* of M*a,b P* (*Q*) and *S* ′ of M*a,b Q* (*P*) that are not avoiding. If *S* and *S* ′ are not minimal, then by defnition they contain minimal subsegments that are not avoiding. Hence we can assume without loss of generality that *S* and *S* ′ are minimal.

Let *P* ′ be an *a*-colored path that follows *S* and let *Q*′ be a *b*-colored path that follows *S* ′ such that *P* ′ and *Q*′ are not avoiding. Let further

$$P'' := P[s\_P, s\_{P'}] \bullet P' \bullet P[t\_{P'}, t\_P] \text{ and } Q'' := Q[s\_Q, s\_{Q'}] \bullet Q' \bullet Q[t\_{Q'}, t\_Q].$$

Note that *P* ′′ follows M*a,b P* (*Q*) and therefore M*a,b P* (*Q*) ⊆ *P* ′′. Analogously, *Q*′′ follows M*a,b Q* (*P*) and hence M*a,b Q* (*P*) ⊆ *Q*′′. By Proposition 5.14, it holds that

$$\{v \in P^{\prime\prime} \mid v \in ^{a,b} Q^{\prime\prime}\} = \{v \in P \mid v \in ^{a,b} Q\} = \emptyset,$$

that is, *P* ′′ and *Q*′′ are avoiding. Since *P* ′′ and *Q*′′ are avoiding, so are all subpaths of *P* ′′ and *Q*′′. Thus *P* ′ and *Q*′ are avoiding, a contradiction.

The next lemma deals with the case where *α a,b P* (*Q*) ̸= ⊥. Recall that in this case we only consider segments that do not contain *α a,b P* (*Q*) or *ω a,b P* (*Q*).

**Lemma 5.22.** *Let* (*sP , tP* ) *be an a-colored pair and let* (*sQ, tQ*) *be a b-colored pair.  If α a,b P* (*Q*) ̸= ⊥*, then let S*1 *and S*2 *be segments of the marble path* M*a,b P* (*Q*) *with* start(*S*1) = *sP ,* end(*S*1) = *α a,b P* (*Q*)*,*start(*S*2) = *ω a,b P* (*Q*)*, and* end(*S*2) = *tP . Let further S* ′ *be a segment of the marble paths* M*a,b Q* (*P*)*. Then S*1 *and S* ′ *are avoiding and so are S*2 *and S* ′ *.*

*Proof.* Note that *α a,b P* (*Q*) ̸= ⊥, Observation 5.7 and Lemma 5.10 imply that

$$\{v \in P \mid v \in ^{a,b}Q\} = P[\alpha\_P^{a,b}(Q), \omega\_P^{a,b}(Q)].$$

Assume towards a contradiction that *S*1 and *S* ′ are not avoiding or *S*2 and *S* ′ are not avoiding. Then there are paths *P*1 that follows *S*1, *P*2 that follows *S*2 and *Q*′ that follows *S* ′ such that *P*1 and *Q*′ are not avoiding or *P*2 and *Q*′ are not avoiding. Hence there are vertices *v* in *Q*′ and *w* in *P*1 or *P*2 that are inner vertices with *v* =*a,b w*. Let

$$P^\* := P\_1 \bullet P[\alpha\_P^{a,b}(Q), \omega\_P^{a,b}(Q)] \bullet P\_2 \text{ and } Q^\* := Q[s\_Q, s\_{Q'}] \bullet Q' \bullet Q[t\_{Q'}, t\_Q].$$

Note that *P* ∗ is *a*-colored as each of its subpaths is *a*-colored. Moreover, *P* ∗ follows M*a,b P* (*Q*) as it contains *sP , α a,b P* (*Q*)*, ω a,b P* (*Q*), and *tP* . Analogously, *Q*∗ follows M*a,b Q* (*P*). Proposition 5.14 then states that

$$\{v \in P^\* \mid v \in {}^{a,b}Q'\} = \{v \in P \mid v \in {}^{a,b}Q\} = P[\alpha\_P^{a,b}(Q), \omega\_P^{a,b}(Q)].$$

Thus, *w* ∈ *P*[*α a,b P* (*Q*)*, ω a,b P* (*Q*)] which is a contradiction to the assumption that *w* is an interior vertex of the *a*-colored paths *P*1 or *P*2.

The fnal lemma generalizes the two previous ones from M (comparison of two paths) to C (sequences of paths). Unfortunately, it contains a lot of rather tedious case distinctions. We remark that solving the respective cases is not particularly difcult or interesting.

**Lemma 5.23.** *Let* (*G,*(*si , ti*)*i*∈[*k*]) *be an instance of k-*Disjoint Shortest Paths*, let* P *. .*= (*Pi*)*i*∈[*k*] *be a solution to this instance, and let* Φ ⊆ [*k*]*. Let σ . .*= (*ℓ*1*, ℓ*2*, . . . , ℓ*|Φ|) *be a permutation of* Φ*, let σ*start *. .*= (*ℓ*1*, ℓ*2*, . . . , ℓ*|Φ|−1)*, and let* C *be the crossing set of* P*. Let g . .*= *ℓ*1*, i . .*= *ℓ*|Φ|−1*, and j . .*= *ℓ*|Φ| *.*

*(i) If* T (*σ*) = {⊥} *and* T (*σ*start) ̸= {⊥}*, then the two marble paths*

$$V(P\_i[\mathcal{T}(\sigma\_{\text{start}})]) \cap \mathcal{C} \text{ and } V(P\_j) \cap \mathcal{C}$$

*are avoiding.*

*(ii) If* T (*σ*) = {*u, v*} ̸= {⊥} *with u <j v, then the two marble paths*

*V* (*Pi* [T (*σ*start)]) ∩ C *and V* (*Pj* [*sj , u*]) ∩ C

*are avoiding and so are*

$$V(P\_i[\mathcal{T}(\sigma\_{\text{start}})]) \cap \mathcal{C} \text{ and } V(P\_j[v, t\_j]) \cap \mathcal{C}.$$

*Proof.* We will prove both claims by induction over |Φ|. *Base case:* Let |Φ| = 2 and hence *g* = *i* and *Pi* [T (*σ*start)] = *Pi* .

(i) Since T (*σ*) = {⊥}, it holds that *α i,j Pj* (*Pi*) = ⊥. By Defnition 5.7, it holds that M*i,j Pi* (*Pj* ) ⊆ *V* (*Pi*) ∩ C and M*i,j Pj* (*Pi*) ⊆ *V* (*Pj* ) ∩ C. By Lemma 5.21, M*i,j Pi* (*Pj* ) and M*i,j Pj* (*Pi*) are avoiding. Lemma 5.20 states *V* (*Pi*) ∩ C and *V* (*Pj* ) ∩ C are avoiding since

$$\begin{aligned} \text{start}(V(P\_i) \cap \mathcal{C}) &= s\_i = \text{start}(\mathcal{M}\_{P\_i}^{i,j}(P\_j)), \\ \text{end}(V(P\_i) \cap \mathcal{C}) &= t\_i = \text{end}(\mathcal{M}\_{P\_i}^{i,j}(P\_j)), \\ \text{start}(V(P\_j) \cap \mathcal{C}) &= s\_j = \text{start}(\mathcal{M}\_{P\_j}^{i,j}(P\_i)), \text{ and} \\ \text{end}(V(P\_j) \cap \mathcal{C}) &= t\_j = \text{end}(\mathcal{M}\_{P\_j}^{i,j}(P\_i)). \end{aligned}$$

(ii) Since *σ* = (*i, j*), it holds that *u* = *α i,j Pj* (*Pi*) and *v* = *ω i,j Pj* (*Pi*). By Defnition 5.7, it holds that M*i,j Pi* (*Pj* ) ⊆ *V* (*Pi*) ∩ C and M*i,j Pj* (*Pi*) ⊆ *V* (*Pj* ) ∩ C. By Lemma 5.22, M*i,j Pi* (*Pj* ) and {*sj , u*} are avoiding and so are M*i,j Pi* (*Pj* ) and {*v, tj*}. Thus the claim again follows from Lemma 5.20 and

$$\begin{aligned} \text{start}(V(P\_i) \cap \mathcal{C}) &= s\_i = \text{start}(\mathcal{M}\_{P\_i}^{i,j}(P\_j)), \\ \text{end}(V(P\_i) \cap \mathcal{C}) &= t\_i = \text{end}(\mathcal{M}\_{P\_i}^{i,j}(P\_j)), \\ \text{start}(V(P\_j[s\_j, u]) \cap \mathcal{C}) &= s\_j = \text{start}(\{s\_j, u\}), \\ \text{end}(V(P\_j[s\_j, u]) \cap \mathcal{C}) &= u = \text{end}(\{s\_j, u\}), \\ \text{start}(V(P\_j[v, t\_j]) \cap \mathcal{C}) &= v = \text{start}(\{v, t\_j\}), \text{ and } \\ \text{end}(V(P\_j[v, t\_j]) \cap \mathcal{C}) &= t\_j = \text{end}(\{v, t\_j\}). \end{aligned}$$

*Induction step:* Let |Φ| ≥ 3 and assume that the statement holds for all Φ ′ ⊆ [*k*] with 2 ≤ |Φ ′ | *<* |Φ|. Let *σ*end . .= (*ℓ*2*, ℓ*3*, . . . , ℓ*|Φ|) and *σ* ′ . .= (*ℓ*2*, ℓ*3*, . . . , ℓ*|Φ|−1).

(i) Since T (*σ*) = {⊥} and T (*σ*start) ̸= {⊥}, by Defnition 5.7, there are three possible cases:

$$\begin{aligned} \mathcal{T}(\sigma\_{\text{end}}) &= \{\bot\}, \\ V(Q) = V(P\_i[\mathcal{T}(\sigma\_{\text{start}})]) \cap V(P\_i[\mathcal{T}((j, i))]) &= \emptyset, \text{ or} \\ \alpha\_{P\_j[\mathcal{T}(\sigma\_{\text{end}})]}^{g, j}(Q) &= \bot. \end{aligned}$$

We will show that *V* (*Pi* [T (*σ*start)]) ∩ C and *V* (*Pj* ) ∩ C are avoiding in each of the three cases.

(1) We start with the case where T (*σ*end) = {⊥}. Since T (*σ*start) ̸= {⊥} it holds by Lemma 5.18 that

$$\emptyset \ne V(P\_i[\mathcal{T}(\sigma\_{\text{start}})]) \subseteq V(P\_i[\mathcal{T}(\sigma')])$$

and in particular, T (*σ* ′ ) ̸= {⊥}. Since T (*σ*end) = {⊥}, T (*σ* ′ ) ̸= {⊥}, and *σ*end is the permutation of a set Φ ′ with |Φ ′ | *<* |Φ|, the induction hypothesis states that

$$V(P\_i[\mathcal{T}(\sigma')]) \cap \mathcal{C} \text{ and } V(P\_j) \cap \mathcal{C}$$

are avoiding. By defnition, each subsegment of *V* (*Pi* [T (*σ* ′ )]) ∩ C is also avoiding *V* (*Pj* ) ∩ C and since *V* (*Pi* [T (*σ*start)]) ⊆ *V* (*Pi* [T (*σ* ′ )]) and T (*σ*start) ⊆ C, it holds that *V* (*Pi* [T (*σ*start)]) ∩ C is a subsegment of *V* (*Pi* [T (*σ* ′ )]) ∩ C.

(2) We continue with the case where

$$V(Q) := V(P\_i[\mathcal{T}(\sigma\_{\text{start}})]) \cap V(P\_i[\mathcal{T}((j, i))]) = \emptyset.$$

We consider the sequence (*j, i*) and the two cases T ((*j, i*)) = {⊥} and T ((*j, i*)) ̸= {⊥}. Since |{*j, i*}| = 2 *<* |Φ|, the induction hypothesis states that if T ((*j, i*)) = {⊥}, then

*V* (*Pj* ) ∩ C and *V* (*Pi*) ∩ C are avoiding

and if T ((*j, i*)) ̸= {⊥}, then

*V* (*Pj* )∩C avoids both *V* (*Pi* [*si , α i,j Pi* (*Pj* )])∩C and *V* (*Pi* [*ω i,j Pi* (*Pj* )*, ti* ])∩C*.*

In the former case, since *V* (*Pi* [T (*σ*start)])∩ C is a segment of *V* (*Pi*)∩ C, it holds by defnition that *V* (*Pi* [T (*σ*start)]) ∩ C and *V* (*Pj* ) ∩ C are avoiding. In the latter case, since *V* (*Q*) = ∅, it holds that

$$V(P\_i[\mathcal{T}(\sigma\_{\text{start}})]) \subseteq V(P\_i[s\_i, \alpha\_{P\_i}^{i,j}(P\_j)]) \text{ or}$$

$$V(P\_i[\mathcal{T}(\sigma\_{\text{start}})]) \subseteq V(P\_i[\omega\_{P\_i}^{i,j}(P\_j), t\_j]).$$

Since the two cases are analogous, we assume without loss of generality the former, that is, *V* (*Pi* [T (*σ*start)]) ⊆ *V* (*Pi* [*si , α i,j Pi* (*Pj* )]).

Since *V* (*Pi* [*si , α i,j Pi* (*Pj* )]) ∩ C and *V* (*Pj* ) ∩ C are avoiding and since

$$V(P\_i[\mathcal{T}(\sigma\_{\text{start}})]) \cap \mathcal{C} \subseteq V(P\_i[s\_i, \alpha\_{P\_i}^{i,j}(P\_j)]) \cap \mathcal{C},$$

by defnition *V* (*Pi* [T (*σ*start)]) ∩ C and *V* (*Pj* ) ∩ C are also avoiding.

(3) It remains to analyze the case where *α g,j Pj* [T (*σ*end)](*Q*) = ⊥. We assume that T (*σ*end) ̸= {⊥} and *V* (*Q*) ̸= ∅ as we can otherwise use the proofs above. Assume towards a contradiction that *V* (*Pj* ) ∩ C and *V* (*Pi* [T (*σ*start)]) ∩ C are not avoiding. Then there are minimal segments *Si* ⊆ *V* (*Pi* [T (*σ*start)]) ∩ C and *Sj* ⊆ *V* (*Pj* ) ∩ C that are not avoiding. We consider the two cases

$$\begin{aligned} S\_i &\subseteq V(P\_i[\mathcal{T}(\sigma\_{\text{start}})]) \cap V(P\_i[\mathcal{T}((j,i))]) = V(Q) \text{ and} \\ S\_i &\subseteq V(P\_i[\mathcal{T}(\sigma\_{\text{start}})]) \backslash V(P\_i[\mathcal{T}((j,i))]). \end{aligned}$$

Note that T ((*j, i*)) ⊆ C and that *Si* is minimal and hence this case distinction is complete. In the latter case, note that since *Si* and *Sj* are not avoiding, there is a path *Ri* that follows *Si* and a path *Rj* that follows *Sj* such that {*v* ∈ *Ri* | *v* ∈ *i,j Rj*} \ *Si* ≠ ∅. Then, it holds by Observation 5.7 {*v* ∈ *Pi* | *v* ∈ *i,j Pj*} ⊆ *V* (*Pi* [T ((*j, i*))]). Moreover, by Proposition 5.14 {*v* ∈ *Ri* | *v* ∈ *i,j Rj*} ⊆*i,j V* (*Pi* [T ((*j, i*))]). Hence

$$\{v \in R\_i \mid v \in ^{i,j} R\_j\} \subseteq ^{a,b} S\_i,$$

a contradiction.

If *Si* ⊆ *V* (*Pi* [T (*σ*start)])∩*V* (*Pi* [T ((*j, i*))]) = *V* (*Q*), then we distinguish between the two cases

$$S\_j \subseteq V(P\_j[\mathcal{T}(\sigma\_{\text{end}})]) \cap \mathcal{C} \text{ and } S\_j \text{ } \backslash V(P\_j[\mathcal{T}(\sigma\_{\text{end}})]) \neq \emptyset.$$

In the former case, it holds by Lemma 5.21 that M*g,j Pj* [T (*σ*end)](*Q*) and M*g,j Q* (*Pj* [T (*σ*end)]) are avoiding. Since

$$\begin{aligned} \mathcal{M}\_{P\_j}^{g,j}(\mathcal{T}(\sigma\_{\text{end}})[Q] &\subseteq V(P\_j[\mathcal{T}(\sigma\_{\text{end}})]) \cap \mathcal{C} \text{ and} \\ \mathcal{M}\_Q^{g,j}(P\_j[\mathcal{T}(\sigma\_{\text{end}})]) &\subseteq V(Q) \cap \mathcal{C}, \end{aligned}$$

it holds that *Si* and *Sj* are avoiding, a contradiction.

Finally, it remains to analyze the case where *Sj* \ *V* (*Pj* [T (*σ*end)]) ̸= ∅. Since T (*σ*start) ̸= {⊥} it holds by Lemma 5.18 that

$$\emptyset \ne V(P\_i[\mathcal{T}(\sigma\_{\text{start}})]) \subseteq V(P\_i[\mathcal{T}(\sigma')]).$$

and in particular, T (*σ* ′ ) ̸= {⊥}. Since by assumption T (*σ*end) ̸= {⊥}, the induction hypothesis states that

$$V(P\_i[\mathcal{T}(\sigma')]) \cap \mathcal{C} \text{ and } V(P\_j[s\_j, \text{start}(\mathcal{T}(\sigma\_{\text{end}}))]) \cap \mathcal{C}$$

are avoiding and so are

$$V(P\_i[\mathcal{T}(\sigma')]) \cap \mathcal{C} \text{ and } V(P\_j[\text{end}(\mathcal{T}(\sigma\_{\text{end}})), t\_j]) \cap \mathcal{C}.$$

Since, by Lemma 5.18,

$$S\_i \subseteq V(P\_i[\mathcal{T}(\sigma\_{\text{start}})]) \cap \mathcal{C} \subseteq V(P\_i[\mathcal{T}(\sigma')]) \cap \mathcal{C}$$

and since

$$\begin{aligned} S\_j &\subseteq V(P\_j[s\_j, \text{start}(\mathcal{T}(\sigma\_{\text{end}}))]) \cap \mathcal{C} \text{ or} \\ S\_j &\subseteq V(P\_j[\text{end}(\mathcal{T}(\sigma\_{\text{end}})), t\_j]) \cap \mathcal{C} \end{aligned}$$

it follows that *Si* and *Sj* are avoiding, a contradiction.

(ii) In this case it holds that T (*σ*) = {*u, v*} ̸= {⊥} with *u <j v* and it remains to show that

$$V(P\_i[\mathcal{T}(\sigma\_{\text{start}})]) \cap \mathcal{C} \text{ and } V(P\_j[s\_j, u]) \cap \mathcal{C}$$

are avoiding and so are

$$V(P\_i[\mathcal{T}(\sigma\_{\text{start}})]) \cap \mathcal{C} \text{ and } V(P\_j[v, t\_j]) \cap \mathcal{C}.$$

Since both cases are analogous, we will only show that *V* (*Pi* [T (*σ*start)]) ∩ C and *V* (*Pj* [*sj , u*]) ∩ C are avoiding. To this end, assume towards a contradiction that there are minimal segments

$$S\_i \subseteq V(P\_i[\mathcal{T}(\sigma\_{\text{start}})]) \cap \mathcal{C} \text{ and } S\_j \subseteq V(P\_j[s\_j, u]) \cap \mathcal{C}$$

that are not avoiding.

We consider the two cases *Si*\*V* (*Pi* [T ((*j, i*))]) ̸= ∅ and *Si* ⊆ *V* (*Pi* [T ((*j, i*))]). In the former case, note that if {*w, x*} . .= T ((*j, i*)) ̸= {⊥} with *w <i x*, then it holds by Lemma 5.22 that *V* (*Pi* [*si , w*]) ∩ C and *V* (*Pj* ) ∩ C are avoiding. If T ((*j, i*)) = {⊥}, then it holds by Lemma 5.21 that *V* (*Pi*) ∩ C and *V* (*Pj* ) ∩ C are avoiding. Hence in both cases *Si* and *Sj* are avoiding, a contradiction.

Now assume that *Si* ⊆ *V* (*Pi* [T ((*j, i*))]). Since *Si* ⊆ *V* (*Pi* [T (*σ*start)]), it holds by Lemma 5.18 that ∅ ̸= *V* (*Pi* [T (*σ*start)]) ⊆ *V* (*Pi* [T (*σ* ′ )]) and that

$$S\_i \subseteq V(Q) = V(P\_i[\mathcal{T}(\sigma\_{\text{start}})]) \cap V(P\_i[\mathcal{T}((j, i))]).$$

Note that if in this case T (*σ*end) = {⊥}, then by induction hypothesis *V* (*Pi* [T (*σ* ′ )]) ∩ C and *V* (*Pj* ) ∩ C are avoiding, and thus so are

$$V(P\_i[\mathcal{T}(\sigma\_{\text{start}})]) \cap \mathcal{C} \supseteq S\_i \text{ and } V(P\_j) \cap \mathcal{C} \supseteq S\_j,$$

a contradiction.

It remains to analyze the case where {*y, z*} . .= T (*σ*end) ̸= {⊥}. We resolve this case with a fnal case distinction:

$$S\_j \mid V(P\_j[\mathcal{T}(\sigma\_{\text{end}})]) \neq \emptyset \text{ or } S\_j \subseteq V(P\_j[\mathcal{T}(\sigma\_{\text{end}})]).$$

In the former case *Sj* ⊆ *V* (*Pj* [*sj , y*]) or *Sj* ⊆ *V* (*Pj* [*z, tj* ]). By Lemma 5.18, it holds that *Si* ⊆ *V* (*Pi* [T (*σ*start)]) ⊆ *V* (*Pi* [T (*σ* ′ )]). Since by Lemma 5.22

$$\begin{aligned} V(P\_j[s\_j, y]) &\cap \mathcal{C} \text{ and } \begin{aligned} V(P\_i[\mathcal{T}(\sigma')]) &\cap \mathcal{C} \text{ and }\\ V(P\_j[z, t\_j]) &\cap \mathcal{C} \text{ and } \begin{aligned} V(P\_i[\mathcal{T}(\sigma')]) &\cap \mathcal{C} \end{aligned} \end{aligned}$$

are avoiding, we conclude that *Si* and *Sj* are avoiding, a contradiction.

Finally, if *Sj* ⊆ *V* (*Pj* [T (*σ*end)]), then it holds by induction hypothesis and Lemma 5.18 that

$$S\_i \subseteq V(P\_i[\mathcal{T}(\sigma\_{\text{start}})]) \cap \mathcal{C} \subseteq V(P\_i[\mathcal{T}(\sigma')]) \cap \mathcal{C} \text{ and } S\_j \subseteq V(P\_j[\mathcal{T}(\sigma\_{\text{end}})]) \cap \mathcal{C}$$

are avoiding, a contradiction.

We conclude this section with the defnition of labels of segments and the proof that they guarantee that paths following two segments have either a common color or are avoiding. To this end, let *S* = {*u, v*} be a segment of an *i*-marble pathwith *u <i v*. The set of *labels* of *S* (labels[*S*]) is defned as

$$\{a \mid \exists \sigma := (\ell\_1 = a, \ell\_2, \dots, \ell\_{|\sigma|} = i). \ \{\alpha, \omega\} := \mathcal{T}(\sigma) \neq \{\bot\} \land \alpha \le^i u <^i v \le^i \omega\}.$$

**Proposition 5.24.** *Let* (*G,*(*si , ti*)*i*∈[*k*]) *be an instance of k-*Disjoint Shortest Paths *and let* P = (*Pi*)*i*∈[*k*] *be a solution to this instance. Let i, j* ∈ [*k*] *and let Ti* = *V* (*Pi*) ∩ C *be an i-marble path and Tj* ⊆ *V* (*Pj* ) ∩ C *be a j-marble path. Let Si* ⊆ *Ti and Sj* ⊆ *Tj be two minimal segments. If* labels[*Si* ] ̸= labels[*Sj* ]*, then Si and Sj are avoiding.*

*Proof.* We start with the case where *i /*∈ labels[*Sj* ]. Then either T ((*i, j*)) = {⊥} or *Sj* ∩ *Tj* [*u, v*] = ∅, where {*u, v*} . .= T ((*i, j*)) ̸= {⊥}. In both cases, *Sj* and *Si* are avoiding by Lemma 5.23. The case where *j /*∈ labels[*Si* ] is analogous.

It remains to consider the case where

$$i, j \in \text{labels}[S\_i] \cap \text{labels}[S\_j].$$

Let without loss of generality be *d* ∈ labels[*Si* ]\labels[*Sj* ]. By defnition of labels, there is a set Φ = {*ℓ*1*, ℓ*2*, . . . , ℓ*|Φ|} and a permutation *σ* = (*ℓ*1*, ℓ*2*, . . . , ℓ*|Φ|) of Φ

such that *ℓ*1 = *d*, *ℓ*|Φ| = *i*, T (*σ*) = {*α, ω*} ̸= {⊥}, and *Si* ⊆ *Pi* [*α, ω*] ∩ C. We consider the two cases *j /*∈ Φ and *j* ∈ Φ.

If *j /*∈ Φ, then let *σ* ′ . .= (*d* = *ℓ*1*, ℓ*2*, . . . , ℓ*|Φ| = *i, j*) and we distinguish between the two cases T (*σ* ′ ) ̸= {⊥} and T (*σ* ′ ) = {⊥}. If T (*σ* ′ ) ̸= {⊥}, then by defnition of labels and since *d /*∈ labels[*Sj* ], it holds that *Sj* \ *V* (*Pj* [T (*σ* ′ )]) ̸= ∅. Lemma 5.23 states that *Sj* and each minimal segment of *V* (*Pi* [T (*σ*)]) ∩ C are avoiding. Hence, *Si* and *Sj* are avoiding as *Si* ⊆ *V* (*Pi* [T (*σ*)])∩C. If T (*σ* ′ ) = {⊥}, then, by Lemma 5.23, it holds that *V* (*Pi* [T (*σ*)]) ∩ C and *Tj* . .= *V* (*Pj* ) ∩ C are avoiding. Thus by defnition *Si* and *Sj* are avoiding.

It remains to consider the case where *j* ∈ Φ = {*ℓ*1*, ℓ*2*, . . . , ℓ*|Φ|}. In this case let *x* ∈ [2*,* |Φ| − 1] such that *j* = *ℓx* and let *σi* . .= (*d* = *ℓ*1*, ℓ*2*, . . . , ℓi*) for all *h* ∈ [*x,* |Φ|] (*x* ≤ *h* ≤ |Φ|). Note that *σx* . .= (*d* = *ℓ*1*, ℓ*2*, . . . , ℓx* = *j*) and *σ*|Φ| = *σ*. Since *Si* ⊆ *V* (*Pi* [T (*σ*)]) ∩ C, it follows that T (*σ*) ̸= {⊥} and, by defnition of T , it holds for each *h* ∈ [*x,* |Φ|] that T (*σh*) ̸= {⊥}. Lemma 5.19 then states that for each *h* ∈ [*x,* |Φ|] and each subpath *Q*|Φ| of *Pi* [T (*σ*|Φ|)] = *Pi* [T (*σ*)] there is some subpath *Qh* of *Pℓh* [T (*σh*)] such that *Qh* =set(*σh*) *Qh*−1. Let *Q*|Φ| be such a path with {*sQ*|Φ| *, tQ*|Φ| } = *Si* . Thus,

$$Q\_{|\Phi|} = ^jQ\_{|\Phi|-1} = ^j\dots = ^jQ\_{x\_j}$$

and in particular {start(*Si*)*,* end(*Si*)} ⊆*j V* (*Pj* [T (*σx*)]).

Since *Si* ⊆ *V* (*Pi* [T (*σ*)]) ∩ C, it holds by Lemma 5.18 that

$$S\_i \subseteq V(P\_i[\mathcal{T}(\sigma)]) \cap \mathcal{C} \subseteq V(P\_i[\mathcal{T}((\ell\_x, \ell\_{x+1}, \dots, \ell\_{|\Phi|}))]) \cap \mathcal{C}.$$

Hence, it holds that {start(*Si*)*,* end(*Si*)} is *j*-colored and thus it holds for each path *Qi* that follows *Si* that *Qi* ⊆*j V* (*Pj* [T (*σx*)]). Since *d* ∈ labels[*S* ′ *j* ] for each *S* ′ *j* ⊆ *V* (*Pj* [T (*σx*)]) ∩ C, *d /*∈ labels[*Sj* ], and *Sj* is minimal, it follows that

$$S\_j \cap (V(P\_j[\mathcal{T}(\sigma\_x)]) \cap \mathcal{C}) \subseteq \{\text{start}(S\_i), \text{end}(S\_i)\} \cap \mathcal{T}(\sigma\_x).$$

Moreover, since *Pj* is strictly increasing in the *j* th coordinate, it follows for each path *Qi* that follows *Si* and each path *Qj* that follows *Sj* that

$$\overline{V(Q\_i)}^j \cap \overline{V(Q\_j)}^j \subseteq \overline{V(Q\_i)}^j \cap \overline{V(P\_j[\mathcal{T}(\sigma\_x)])}^j \subseteq (\{\overline{s\_{Q\_i}}, \overline{t\_{Q\_i}}\} \cap \{\overline{s\_{Q\_j}}, \overline{t\_{Q\_j}}\})^j.$$

Hence, each such pair of paths is avoiding (no two inner vertices share the same vector) and thus it holds by defnition that *Si* and *Sj* are avoiding.

# **5.3 An** *XP***-Algorithm for** *k***-Disjoint Shortest Paths**

In this section, we present our main theorem, that is, an *XP*-algorithm for *k*-Disjoint Shortest Paths with respect to the number *k* of terminal pairs. In a nutshell, we frst guess all marble paths *Ti* and the respective ends T corresponding to the crossing set C of some solution (if one exists). We then compute all minimal segments of each marble path *Ti* , compute their respective labels, and partition the segments such that all minimal segments in the same part of the partition are strictly monotone in a common coordinate and two minimal segments in distinct parts of the partition are avoiding. The crucial improvement over the algorithm by Lochet [Loc21] is that our partition is much smaller. Afterwards, we fnd via dynamic programming for all segments in one part of the partition disjoint paths that follow the respective segments.

To this end, we introduce *c*-layered DAGs and the problem *p*-Disjoint Paths on *c*-layered DAGs. For a graph *G* with vectors #»*v* for all *v* ∈ *V* (as defned in Subsection 5.2.1), the *c-layered DAG Dc* of *G* is the directed graph *Dc* = (*V, A*), where *A* = {(*x, y*) | {*x, y*} ∈ *E*(*G*) ∧ #»*y c* − #»*x c* = 1}. Notice that a path *P* = (*v*1*, v*2*, . . . , vp*) is *c*-colored if and only if # » *vi*+1 *c* − #»*vi c* = 1 for all *i* ∈ [*p* − 1] or #»*vi c* − # » *vi*+1 *c* = 1 for all *i* ∈ [*p* − 1].  Then, *P* is *c*-colored if and only if *Pm* is and hence if and only if the directed path (*V* (*P*)*, A*(*P*)) or the directed path (*V* (*P*)*, A*(*Pm*)) is a path in *Dc*. Finally, observe that *A*(*Pm*) = *A*−1 (*P*), that is, *Pm* and *P* have the same vertices but the edges are oppositely directed.

**Observation 5.25.** *A path P in G is c-colored if and only if* (*V* (*P*)*, A*(*P*)) *or* (*V* (*P*)*, A*−1 (*P*) *is a path in the c-layered DAG Dc of G.*

We continue with a defnition of *p*-Disjoint Paths on *c*-layered DAGs. Here, we are given a *c*-layered DAG *Dc* and a list (*si , ti*)*i*∈[*p*] of (possibly intersecting) terminal pairs. We then ask whether there are pairwise internally vertex-disjoint *si*-*ti*-path in *Dc*. Formally, it is defned as follows.

*p*-Disjoint Paths on *c*-layered DAGs

**Input:** A *c*-layered DAG *Dc* and *p* pairs (*si , ti*)*i*∈[*k*] of vertices.

**Question:** Are there *p* internally vertex-disjoint paths *Pi* in *Dc* such that *Pi* is a shortest *si*-*ti*-path for each *i* ∈ [*p*]?

With these defnitions, we can state our algorithm. Algorithm 5.1 provides pseudo-code.

**Algorithm 5.1:** Our algorithm for *k*-Disjoint Shortest Paths.

**1 function** solve(*G,* (*si , ti*)*i*∈[*k*]) **2 foreach** guess (*Ti*)*i*∈[*k*] , Ends of the crossing set **do** /\* We assume subsequently that the guesses are correct, that is, if there is a solution P . .= (*Pi*)*i*∈[*k*] , then *Ti* = *V* (*Pi*) ∩ C for all *i* ∈ [*k*] and Ends = T . \*/ **3 foreach** *i* ∈ [*k*] **do 4** P*i* ← ∅ // *Pi* contains all segments corresponding to *Di* **5 foreach** minimal segment *S* of some *Ti* with *i* ∈ [*k*] **do 6** marks[*Si* ] ← ∅ **7 foreach** permutation *σ* = (*ℓ*1*, ℓ*2*, . . . , i*) with Ends(*σ*) = {*α, ω*} ̸= {⊥} and *α* ≤*i* start(*Si*) *<i* end(*Si*) ≤*i ω* **do 8** marks[*Si* ] ← marks[*Si* ] ∪ set(*σ*) **9** *j* ← min marks[*S*] **10** *x* ← arg min{ #»*v j* | *v* ∈ {start(*S*)*,* end(*S*)}} **11** *y* ← arg max{ #»*v j* | *v* ∈ {start(*S*)*,* end(*S*)}} **12** P*j* = P*j* ∪ {(*x, y*)} **13 foreach** *j* ∈ [*k*] **do 14** Order P*j* = ((*x*1*, y*1)*,*(*x*2*, y*2)*, . . .*) such that # »*x*1 *j* ≤ # »*x*2 *j* ≤ *. . .* **15 if** all instances (*Di ,*P*i*) of |P*i* |-Disjoint Paths on *i*-layered DAGs are yes-instances and the combined solutions form a solution of *k*-Disjoint Shortest Paths **then 16 return** true **17 return** false

Fortune et al. [FHW80] showed that *p*-Disjoint Path on DAGs can be solved in *n O*(*p*) time. Since *c*-layered DAGs are DAGs, we could use their algorithm in Algorithm 5.1 and achieve a running time of *n O*(*k*!). However, to drop the Landau notation in the exponent, we show that *p*-Disjoint Paths on *c*-layered DAGs can be solved in *O*(*n p*+1) time. Afterwards, we show that Algorithm 5.1 is correct and runs in *O*(*n* 16*k*+*k*!+*k*+1) time.

The idea behind the dynamic program for *p*-Disjoint Paths on *c*-layered DAGs is as follows. Given an *i*-layered DAG *Di* , a number *p*, and a set of terminal pairs (*sj , tj* )*, j* ∈ [*p*], where #»*sj i <* #»*tj i* and #»*sj i* ≤ #»*sℓ i* for all *j < ℓ* ∈ [*p*], the dynamic program is a table *T*[*x*1*, x*2*, . . . , xp*] ∈ {true*,* false} that stores true roughly if the following two criteria are fulflled.

Thus, *T*[*t*1*, t*2*, . . . , tp*] = true if and only if there is a set of internally vertexdisjoint *sj* -*tj* -paths.

Note that if *si* =*c sj* and *ti* =*c tj* for all *i, j* ∈ [*p*], then there is a fairly straightforward dynamic program for *p*-Disjoint Paths on *c*-layered DAGs. Store for increasing values of *d* ∈ [ #»*si c ,* #»*ti c* ] and for each tuple (*x*1*, x*2*, . . . , xp*) of vertices with #»*xi c* = *d* for all *i* ∈ [*p*] whether there are pairwise disjoint paths from *si* to *xi* (the paths may possibly share their end vertices *si* and/or *ti* if *xi* = *ti*). The table corresponding to this dynamic program has *O*(*n* · *n p* ) table entries (at most *n* values for *d* and for each *d* there are at most *n p* sequences of *p* vertices). Each table entry can be computed in *O*(*n p* ) time by iterating over all table entries for *d* − 1 and (*x* ′ 1 *, x*′ 2 *, . . . , x*′ *p* ) and checking whether (*x* ′ 1 *, x*1)*,*(*x* ′ 2 *, x*2)*, . . . ,*(*x* ′ *p , xp*) ∈ *A*. This would lead to an overall running time of *O*(*n* 2*p*+1) for *p*-Disjoint Paths on *c*-layered DAGs. Note further that ensuring that *si* =*c sj* and *ti* =*c tj* is not difcult either. One can simply replace each *si* and *ti* with new terminals and add paths of according lengths between the new and the old terminal vertices. An example of this roughly outlined construction is given in Figure 5.5. However, there is another dynamic program that is faster (*O*(*n p*+1) time instead of *O*(*n* 2*p*+1) time) and that also works for general DAGs. Basically, instead of moving all *xi* from one layer to the next in one step, we order them and move the *xi* that is frst in this ordering. This has the advantage that for computing one table entry, we only have to consider *O*(*n*) table entries instead of *O*(*n p* ).

**Lemma 5.26.** *An instance of p*-Disjoint Paths on DAGs *on a graph with n vertices can be solved in O*(*n p*+1) *time.*

*Proof.* Let *D* = (*V, A*) be a DAG and let (*si , ti*)*i*∈[*p*] be a set of *p* terminal pairs. We defne *V* end . .= ⋃ *i*∈[*p*] {*si , ti*} to be the set of all terminals. We also choose an arbitrary topological order of *D* and denote by *u* ≺ *v* that *u* comes before *v*

**Figure 5.5:** *Left-hand side:* An example of 3-Disjoint Paths on *c*-layered DAGs. The *c*-coordinate of vertices is illustrated by their horizontal position. The terminal pairs are (*s*1*, t*1), (*s*2*, t*2), and (*s*3*, t*3) and *s*2 = *s*3. A solution is highlighted.

*Right-hand side:* An equivalent instance in which *si* =*c sj* for all *i, j* ∈ [*p*]. The smaller vertices are the vertices that are newly introduced by the construction. The corresponding solution is again highlighted. Note that since *s*2 = *s*3, after adding *s*′ 2 and *s*′ 3, the solution is not internally vertex-disjoint if *s*2 was not duplicated.

in this topological order. We assume without loss of generality that *si* ⪯ *sj* for all *i < j* ∈ [*p*]. We further assume that *si* ⪯ *ti* for all *i* ∈ [*p*] as otherwise there can be no path from *si* to *ti* and that *p* ≤ *n* as we can iterate over all pairs (*si, ti*) and delete those that are connected by an arc (*si, ti*) ∈ *A*. All remaining paths have at least one inner vertex that has to be from *V* \ *V* end and that has to be unique for each path. Hence, if there are at least *n* + 1 pairs remaining, then the instance has no solution.

We build a table *T*[*x*1*, x*2*, . . . , xp*] ∈ {true*,* false} that stores true if and only if the following three criteria are fulflled.

If the table is completely flled, then there is a set of internally vertex-disjoint shortest *sj* -*tj* -paths if and only if *T*[*t*1*, t*2*, . . . , tp*] = true as the frst two requirements are trivially fulflled. We initialize the table with *T*[*s*1*, s*2*, . . . , sp*] . .= true as internally vertex-disjoint *si*-*si*-paths trivially exist. Moreover, for each tuple (*x*1*, . . . , xp*) ∈ *V p* if *xi* ≺ *si* or *ti* ≺ *xi* or *xi* ∈ *V* end \ {*si, ti*} for at least one *i* ∈ [*p*], then we set *T*[*x*1*, . . . , xp*] . .= false. Note that there are *np* possible tuples and initializing each entry takes *O*(*n*) time.

We next show how to compute the entries of *T*. To this end, for some tuple (*x*1*, x*2*, . . . , xp*), let *xℓ* be a vertex such that *xℓ* ̸= *sℓ* and *xi* ⪯ *xℓ* for all *xi* with *i* ∈ [*p*] and *xi* ̸= *si* . Moreover, let

$$N^\*(x\_i) := \{ v \mid (v, x\_i) \in A \land v \in (V \mid (V^{\text{end}} \mid \{s\_i\})) \mid \{x\_1, \dots, x\_p\} \}.$$

Finally, let

$$T[x\_1, x\_2, \dots, x\_p] := \bigvee\_{x\_\ell' \in N^\star(x\_\ell)} T[x\_1, x\_2, \dots, x\_{\ell-1}, x\_\ell', x\_{\ell+1}, \dots, x\_p].$$

We now show by induction on the sum of positions in the topological order of all *xi* that *T*[*x*1*, x*2*, . . . , xp*] = true if and only if the three criteria are fulflled. In the base case, *T*[*s*1*, s*2*, . . . , sp*] = true, or there is some *xi* such that *xi* ≺ *si* and therefore *T*[*x*1*, x*2*, . . . , xp*] = false. Note that there is no *si*-*xi*-path in the latter case.

Now to show the statement for some table entry *T*[*x*1*, x*2*, . . . , xp*], assume that the statement holds for all table entries *T*[*x* ′ 1 *, x*′ 2 *, . . . , x*′ *p* ] such that *x* ′ *i* ⪯ *xi* for all *i* ∈ [*p*] and *x* ′ *j* ≺ *xj* for at least one *j* ∈ [*p*]. To this end, frst assume that *T*[*x*1*, x*2*, . . . , xp*] = true. Since *T*[*x*1*, x*2*, . . . , xp*] = true, it was not set to false in the initialization and thus i) and ii) are satisfed. By construction, there is an *x* ′ *ℓ* ∈ *N*∗ (*xℓ*) such that *T*[*x*1*, x*2*, . . . , xℓ*−1*, x*′ *ℓ , xℓ*+1*, . . . , xp*] = true. By induction hypothesis, there are internally vertex-disjoint *sℓ*-*x* ′ *ℓ* - and *sj* -*xj* -paths for all *j* ∈ [*p*] \ {*ℓ*} such that *sℓ* ⪯ *x* ′ *ℓ* ⪯ *tℓ* and *x* ′ *ℓ* ∈ *V* \ (*V* end \ {*sℓ, tℓ*}). Since by defnition of *xℓ* it holds that *xi* ≺ *xℓ* for all *xi* with *i* ∈ [*p*] and *xi* ̸= *si* , it holds that *xℓ* is not contained in any of the *si*-*xi*-paths for *i* ∈ [*p*]. Hence the *sℓ*-*x* ′ *ℓ* -path can be extended by the edge (*x* ′ *ℓ , xℓ*) and the resulting path combined with the other *si*-*xi*-paths satisfes iii).

To show the other direction assume that *x*1*, x*2*, . . . , xp* satisfy i) to iii). Then consider the *sℓ*-*xℓ*-path and the predecessor *x* ′ *ℓ* of *xℓ*. Note that *x* ′ *ℓ* exists as otherwise *xi* = *si* for all *i* ∈ [*p*] and hence we are in the base case. By construction, *x* ′ *ℓ* ∈ *N*∗ (*xℓ*) ⊆ *V* \ (*V* end \ {*si*}). Note further that *x* ′ *ℓ* ≺ *xℓ* ⪯ *tℓ*, implying *x* ′ *ℓ* ≠ *tℓ* and hence i) is also satisfed by *x* ′ *ℓ* . Further, since there is an *sℓ*-*x* ′ *ℓ* -path (a subpath of the *sℓ*-*xℓ* path), it holds that *s* ⪯ *x* ′ *ℓ* ≺ *xℓ* ⪯ *tℓ* and thus *x* ′ *ℓ* also satisfes ii). Finally, iii) is also satisfed by the *sℓ*-*x* ′ *ℓ* -subpath combined with the other *si*-*xi*-paths. The induction hypothesis then states that *T*[*x*1*, x*2*, . . . , xℓ*−1*, x*′ *ℓ , xℓ*+1*, . . . , xp*] = true. Since *x* ′ *ℓ* ∈ *N*∗ (*xℓ*), it holds that *T*[*x*1*, x*2*, . . . , xp*] = true. Thus, the statement holds for all table entries *T*[*x*1*, x*2*, . . . , xp*].

It remains to analyze the running time. There are at most *n p* possible table entries and computing one takes *O*(*n*) time as *V* end*, ℓ*, and *N*∗ (*xℓ*) can be computed in *O*(*p* + *n*) ⊆ *O*(*n*) time and iterating over at all neighbors of *xℓ* takes *O*(*n*) time. Hence the overall running time is *O*(*n p*+1).

After showing how to solve the subproblems, it remains to show that Algorithm 5.1 is correct and to analyze its running time. We start with the analysis of the running time.

#### **Lemma 5.27.** *Algorithm 5.1 runs in O*(*k* · *n* 16*k*·*k*!+*k*+1) *time.*

*Proof.* First, observe that there are at most *k* · *k*! diferent permutations of subsets of *k* objects as there are exactly *k*! permutations of exactly *k* objects and each of these can be truncated at *k* positions to get any permutation of any smaller (non-empty) subset of objects. Second, observe that by Defnition 5.7 there are at most eight vertices guessed for each sequence *σ* as if *δ i,j P* (*Q*) ̸= ⊥, then *α i,j P* (*Q*) = *ω i,j P* (*Q*) = *∂ i,j P* (*Q*) = *ϖ i,j P* (*Q*) = ⊥. Hence, at most 8*k* ·*k*! vertices need to be guessed, which requires at most *n* 8*k*·*k*! attempts.

Next we analyze the running time of each iteration of the main foreach-loop in Algorithm 5.1. Notice that by Defnition 5.7, for each sequence *σ* there are at most four vertices on a marble path *Ti* and that each of these vertices increases the number of minimal segments *S* on *Ti* by at most one. Note that for each *σ* the set C *σ* contains vertices from at most two paths. Thus, we create at most 8*k* · *k*! new segments overall. Since we start with *k* marble paths, there are at most 8*k* ·*k*! +*k* minimal segments. Thus, there are at most (8*k* ·*k*! +*k*)·(*k* ·*k*!) iterations of the loop in Line 7, each of which takes constant time. Each iteration of Line 14 can be done in *O*(*n*) time using bucket sort and hence the overall running time for all iterations is in *O*(*n* · *k*).

Next, there are *k* instances of *pi*-Disjoint Paths on *i*-layered DAGs that are solved using Lemma 5.26, where *pi* ≤ 8*k* · *k*! + *k* for all *i* ∈ [*k*]. By Lemma 5.26 the running time for solving one instance is *O*(*n* 8*k*·*k*!+*k*+1) and the running time for solving all instances is hence *O*(*k* ·*n* 8*k*·*k*!+*k*+1). Lastly, we verify in Algorithm 5.1 that the solutions found can indeed be merged into one solution for *k*-Disjoint Shortest Paths. Note that we only stated the decision version of *p*-Disjoint Paths on *c*-layered DAGs but the actual solution can be found using a very similar algorithm where we do not only store true or false in the table *T* but also some set of disjoint paths corresponding to each table entry that stores true. Verifying a solution can for example be done in *O*(*k* · *n*) time by iterating over all solution paths and verify that between each pair of

consecutive vertices there is an edge, that all paths are shortest paths, and that all paths are internally vertex-disjoint. This can be done by marking all inner vertices of each path and if some vertex is already marked once and visited again, then return false and otherwise return true. Thus the overall running time of Algorithm 5.1 is

$$O(n^{8k\cdot k!} \cdot ((8k\cdot k! + k)\cdot (k\cdot k!) + n\cdot k + k\cdot n^{8k\cdot k! + k + 1} + n\cdot k) \subseteq O(k\cdot n^{16k\cdot k! + k + 1}).\qed$$

For the correctness of Algorithm 5.1, we need to show that each part of the partition of minimal segments can be solved independently. This follows from Proposition 5.24 together with the fact that Algorithm 5.1 exhaustively tries all possibilities for the crosssing set C. Together with Lemma 5.27, this implies our main theorem.

**Theorem 5.28.** *k-*Disjoint Shortest Paths *is solvable in O*(*k* · *n* 16*k*·*k*!+*k*+1) *time.*

*Proof.* We use Algorithm 5.1 and focus on the correctness as the running time is already analyzed in Lemma 5.27. If Algorithm 5.1 returns true, then Line 16 is executed and a solution is verifed. It remains to show that if there is some solution, then Algorithm 5.1 returns true. If there is some solution P = (*Pi*)*i*∈[*k*] , then let C be its crossing set (Defnition 5.7). Then, there is some iteration of Line 2 where all guesses are correct, that is, Ends = T and *Ti* = *V* (*Pi*) ∩ C. We now consider this iteration of Line 2.