# Servicing Timed Requests on a Line

Angelos Gkikas1 Tomasz Radzik1
1Department of Informatics, Kings College London
<EMAIL_ADDRESS>

###### Abstract

We consider an off-line optimisation problem where $k$ robots must service $n$
requests on a single line. A request $i$ has weight $w_{i}$ and takes place at
time $t_{i}$ at location $d_{i}$ on the line. A robot can service a request
and collect the weight $w_{i}$, if it is present at $d_{i}$ at time $t_{i}$.
The objective is to find $k$ robot-schedules that maximize the total weight.
The optimisation problem is motivated by a robotics application [1] and can be
modeled as a minimum cost flow problem with unit capacities in a flow network
$\mathcal{N}$. Consequently, we ask for a collection of $k$ node-disjoint
paths from the source $s$ to the sink $t$ in $\mathcal{N}$, with minimum total
weight. It was shown in [1] that the flow network $\mathcal{N}$ can be
implicitly represented by $n$ points on the plane which yields to an $O(n\log
n)$-time algorithm for $k=1$ and the special case where all requests have the
same weight. However, for $k\geq 2$ the problem can be solved in $O(kn^{2})$
time with the successive shortest path algorithm which does not use this
implicit representation. We consider arbitrary request weights and show a
recursive $O(k^{2k}n\log^{2k}n)$-time algorithm which improves the previous
bound if $k$ is considered constant. Our result also improves the running time
of previous algorithms for other variants of the optimisation problem.
Finally, we show problem properties that may be useful within the context of
applications that motivate the problem and may yield to more efficient
algorithms.

##  1 Introduction

We consider the following optimisation problem of servicing timed requests on
the line. For a given integer $k\geq 1$ and a set of $n$ timed requests
$\\{(x_{i},t_{i},w_{i}),1\leq i\leq n\\}$, where $x_{i}\in(-\infty,+\infty)$,
$t_{i}\geq 0$ and $w_{i}\geq 0$ are the location (on the line), the time and
the weight of request $i$, respectively, maximise the total weight of requests
which can be serviced by $k$ robots. Initially, at time $t=0$, all robots are
at the origin point of the line and they can move freely along the line,
changing direction and speed when needed, but never exceeding a given maximum
speed $v$. To service request $i$, one of the robots has to be at location
$d_{i}$ exactly at time $t_{i}$. Servicing a request is instantaneous and the
robot can move immediately to serve another request.

This is an off-line optimisation problem with all data about the requests
known in advance, which appeared, for example, in the context of the _ball
collecting problems_ (BCPs) considered by Asahiro et al.[1]. The basic BCP is
essentially the optimisation problem stated in the previous paragraph. There
are $n$ weighted balls approaching the line $L$ where the robots can move.
Each ball will cross $L$ at a specified time and point, and if a robot is
there, then the ball is intercepted (collected). For the weighted case the
objective is to compute the movement of the robots so that the total weight of
the intercepted balls is maximised. For the unweighted case (i.e. all balls
have the same weight) the objective is to maximise the number of intercepted
balls.

Asahiro et al.[1] studied a number of BCP variants, putting them in the
context of the _Kinetic Travelling Salesman Problem_ (KTSP) and establishing
the tractability–intractability (polynomiality vs. NP-hardness) frontier
through the landscape of the studied variants. The literature of the KTSP
consists of similar work, focusing on approximation algorithms [2, 3, 4],
polynomial time exact algorithms [4, 5, 6] for special problem settings and
real world applications[7, 8, 9].

Variants of the BCP are obtained by giving each robot $i$ its own line $L_{i}$
where it moves and intercepts balls, or by not-fixing the position (i.e. the
angle) of the common line $L$ (or the positions of the robots’ individual
lines $L_{i}$), asking instead for the optimal position of the line to be
determined as part of the output, or by considering different optimisation
objectives (e.g., minimizing the number of robots needed to collect all
balls). Asahiro et al. [1] showed that maximising the total weight of
collected balls when robots move on a common line $L$ is polynomially
solvable, but $\mathcal{NP}$-Hard when each robot moves on its own line. They
also showed that the BCP problems with a common line $L$, which is not fixed
but part of the optimisation decision, can be solved by solving $O(n^{2})$
instances with a fixed line.

The problem of servicing timed requests on the line corresponds to the
weighted ball collecting problem, so we will refer to it as BCP, or BCP$(k)$:
a given number of $k$ robots, a single given (fixed) line $L$, and the
objective of maximising the total weight. As shown in Asahiro et al. [1], for
$k\geq 2$ the objective of maximising the total weight with $k$ robots can be
modeled as a minimum cost flow problem in a directed acyclic graph ($DAG$)
$G^{*}$, which has $n$ nodes representing balls and two additional special
source and sink nodes $s$ and $t$, respectively. There is an edge in $G^{*}$
from a node $v^{\prime}$, representing ball $b^{\prime}$, to a node
$v^{\prime\prime}$, representing ball $b^{\prime\prime}$, if there is enough
time for a robot to move from intercepting $b^{\prime}$ to intercepting
$b^{\prime\prime}$. An $s-t$ path in $G^{*}$ represents a schedule for one
robot and its weight is equal to the total weight of the balls intercepted by
the robot.

The corresponding minimum cost flow problem has unit node capacities (maximum
one unit of flow through each node) and node weights equal to negations of the
weights of balls, so is equivalent to finding $k$ node-disjoint paths from $s$
to $t$ (the paths share only nodes $s$ and $t$) such that the total weight of
the selected paths is minimised. This problem can be solved in $O(kn^{2})$
time by the successive shortest path algorithm [10]. The quadratic dependence
on $n$ is due to the fact that graph $G^{*}$ can have quadratic number of
edges. Looking into some technical details, graph $G^{*}$ has actually $2n+2$
nodes since each node representing a ball is split into two nodes (connected
by an edge) as in the standard reduction from node capacities to edge
capacities.

The $DAG$ $G^{*}$ can be implicitly represented by a set ${\cal{P}}$ of $2n+2$
points in the 2-D Euclidean plane, illustrated in Figure 1. The BCP input with
$5$ requests given in Figure 1(a) is shown in Figure 1(b) in the location-time
coordinates (the distances and times are normalised so that the maximum speed
of a robot is equal to $1$). The arrows show the edges of $G^{*}$. Vertex $t$,
not shown in the diagram, is on the time axis sufficiently high so that there
are edges to $t$ from all other nodes. For clarity, we also do not show the
splitting of nodes into two. For the unweighted BCP and $k=1$, Asahiro et al.
[1] show an $O(n\log n)$-time algorithm using the implicit plane
representation of graph $G^{*}$ with the points in ${\cal{P}}$. However, for
the weighted BCP and $k=1$, the problem is solved in the standard way of
computing a longest path in a directed acyclic graph $G^{*}$, which requires
$O(n^{2})$ time. For $k\geq 2$, [1] gives only the $O(kn^{2})$ computation as
indicated above, which applies to both unweighted and weighted BCP.

We show that the implicit plane representation of graph $G^{*}$ can lead also
to efficient algorithms for the weighted BCP for $k\geq 1$. More precisely,
for the weighted BCP and the special case $k=1$ we show an iterative algorithm
with running time of $O(n\log^{3}n)$ which improves the previous bound of
$O(n^{2})$. For the weighted BCP and $k\geq 2$, we show a recursive algorithm
for finding a minimum weight collection of $k$ node-disjoint $s-t$ paths in
graph $G^{*}$ with the running time of $O(k^{3k}n\log^{2k+3}n)$, improving the
previous bound of $O(kn^{2})$ if $k$ is considered constant. This result also
gives an algorithm with the running time of $O(k^{3k}n^{3}\log^{2k+3}n)$ for
the BCP variant where the placement of the line $L$ is to be chosen. A summary
of the previous and new results for the $BCP$ is shown in Table 1.

We also show properties of BCP solutions that may be useful within the context
of applications that motivate the problem. Specifically, an $s-t$ path in
$G^{*}$ is a schedule for one robot in the BCP, and the representation of this
path as a concatenation of straight-line segments on the plane (e.g. path
$(s,1,2,4)$ in Figure 1(b)) gives the direction and the speed for each part of
the schedule. If two paths on the plane cross, then the two robots following
these paths collide (are at the same point at the same time). We show that for
$k\geq 2$, there is at least one minimum-weight collection of $k$ node-
disjoint non-crossing $s-t$ paths, which ensures that the $k$ robots do not
collide, and that such a collection of optimal non-crossing paths can be
computed from any optimal collection of paths within $O(kn\log n)$ time.

Table 1: (Weighted) BCP: maximize the total weight Line $L$ |  $k=1$ [1] |  $k=1$ |  $k\geq 2$ [1] | $k\geq 2$
---|---|---|---|---
as part of input | $O(n^{2})$ | $O(n\log^{3}n)$ | $O(kn^{2})$ | $O(k^{3k}n\log^{2k+3}n)$
as part of output | $O(n^{4})$ | $O(n^{3}\log^{3}n)$ | $O(kn^{4})$ | $O(k^{3k}n^{3}\log^{2k+3}n)$

(a)

(b)

Figure 1: Figure 1(a): Five timed requests $1,2,3,4,5$ on the line $L$. Figure
1(b): Representation of the BCP input in the location-time coordinates and the
$\alpha$-$\beta$ coordinates.

The remaining part of the paper is organised in the following way. In section
2 we discuss the directed acyclic graph (DAG) model and its implicit planar
representation. In section 3 we describe the input and output of algorithm
$\mathcal{A}_{k}$ and provide an overview of its recursive structure. In
section 4 we consider the special case $k=2$ as an introduction to our
recursive approach. In section 5 we consider the general case $k\geq 3$. In
section 6 we show the additional property of BCP solutions which ensures the
$k$ robots do not collide.

##  2 Preliminaries

###  2.1 DAG model of BCP

The input of the BCP, as specified in [1], consists of $n$ tuples
$(x_{1},y_{1},v_{1}),..,(x_{n},y_{n},v_{n})$ and two additional parameters $v$
and $k$. The parameter $k$ is the number of (identical) robots and $v$
specifies their maximum speed. The tuple $(x_{i},y_{i},v_{i})$, for $1\leq
i\leq n$, specifies speed $v_{i}$ of ball $b_{i}$ and the initial position
$(x_{i},y_{i})$ in a $2D$ plane with $x$ and $y$ coordinates. We assume that
$y_{i}\geq 0$. Starting at time $t=0$, ball $b_{i}\in B$ moves from
$(x_{i},y_{i})$ with constant speed of $v_{i}$ towards the $x$-axis, reaching
the point $(x_{i},0)$ at time $t_{i}={y_{i}}/{v_{i}}$. A robot intercepts (or
collects) ball $b_{i}$, if this robot is at time $t_{i}$ at point $(x_{i},0)$.
In this BCP model, to optimise the interception of balls, we need to know only
the numbers $x_{i}$ and $t_{i}$, so we will assume that these numbers are
given directly as the input.

Notice that two or more balls can cross the line $L$ at the same time $t$ at
the same distance $x$ from the origin. When a robot is at time $t$ at $x$, it
can intercept all these balls. In the graph model, we assume that if $w$ balls
are at the same time at the same place on the line, then they are represented
by a single ball with weight $w$. That is, the input to the problem is $n$
weighted timed requests $\\{(x_{i},t_{i},w_{i}),1\leq i\leq n\\}$, where
$x_{i}\in(-\infty,+\infty)$, $t_{i}\geq 0$ and $w_{i}\geq 0$ are the location
(on the line), the time and the weight of request $i$, respectively. We assume
that the speed $v$ of the $k$ robots is equal to $1$ (this is achieved by
dividing $x_{i}$ by $v$ for $i=1,2,\ldots,n$).

We model the input as a directed graph $G(V,E)$ with $n$ nodes $(1,2,..,n)$
representing the $n$ balls and two special nodes $s$ and $t$. For $1\leq i\leq
n$, $1\leq j\leq n$, $i\neq j$, we have an edge $(i,j)$ in $G$, if and only
if, $|x_{j}-x_{i}|\leq t_{j}-t_{i}$ (recall that after normalising, $v=1$),
which means that if a robot is at point $x_{i}$ at time $t_{i}$, having
presumably just intercepted ball $b_{i}$, then it can arrive at point $x_{j}$
by time $t_{j}$ to intercept ball $b_{j}$. For $1\leq i\leq n$, we also have
an edge $(s,i)$, if a robot starting at time $t=0$ from the origin $O$ of $L$
can reach point $x_{i}$ by time $t_{i}$ (to intercept ball $b_{i}$), and we
have all edges $(i,t)$. Graph $G(V,E)$ is acyclic since an edge $(i,j)$
implies that $t_{i}<t_{j}$. We assign weight $w_{i}$ to node $i$ and weight
$0$ to nodes $s$ and $t$. There are no edges $(s,i)$ for the balls $b_{i}$
which cannot be intercepted (because $x_{i}>t_{i}$). Such balls can be removed
from the input and they do not have to be included in graph $G$. We can
therefore assume that graph $G$ has an edge $(s,i)$ for each ball $b_{i}$.
Figure 2 shows the directed acyclic graph $G$ constructed from the BCP input
shown in Figure 1(a).

An $s-t$ path $(s,i_{1},i_{2},\ldots,i_{p},t)$ in $G$ corresponds to a
feasible movement of one robot which intercepts balls
$b_{i_{1}},b_{i_{2}},\ldots,b_{i_{p}}$, in this order. The weight of this path
(the sum of the weights of the nodes on this path) is equal to the total
weight of the intercepted balls. Consequently, we can find a schedule for one
robot that maximizes the number of intercepted balls by finding the maximum
weight path from $s$ to $t$ in the directed acyclic graph $G$. This can be
done in the standard way by negating the weights and move from node weights to
edge weights. That is, we construct graph $G^{\prime}(V^{\prime},E^{\prime})$
with the same set of nodes and edges, such that the weight $w^{\prime}(i,j)$
of an edge $(i,j)\in E^{\prime}$ is equal to
$w^{\prime}(i,j)=-(w(i,j)+w_{j})$. Finding the maximum weight path from $s$ to
$t$ in $G$ is equivalent to finding a shortest (that is, minimum weight) path
from $s$ to $t$ in $G^{\prime}$. Since graph $G$ (and subsequently
$G^{\prime}$) may have $\Theta(n^{2})$ edges in the worst case, without
referring to a special structure of $G$, we can only conclude that such a path
can be computed in $O(n^{2})$ time.

Figure 2: The Directed Acyclic Graph corresponds of the BCP input shown Figure
1(a) for the appropriate values of $x_{i},t_{i}$. The weight of each node
$i\in V\setminus{\\{s,t\\}}$ is equal to $w_{i}$.

For $k\geq 2$ the problem asks for $k$ node-disjoint paths from $s$ to $t$ in
$G$ such that the total weight of the selected paths is minimized. The
condition of node-disjoint paths refers to the internal nodes and ensures that
no intercepted ball is counted twice. We change from node-disjoint paths to
edge-disjoint paths in the standard way by considering the following modified
graph $G^{*}$ obtained from $G$ by splitting nodes, as explained below.

Every node $i\in V\setminus\big{\\{}s,t\big{\\}}$ in $G$ is represented in
$G^{*}$ by two nodes $i^{-},i^{+}$ connected by a short edge from $i^{-}$ to
$i^{+}$. The set $V^{*}$ of nodes in $G^{*}$ includes also nodes $s$ and $t$.
Each edge $(i,j)$ in $G$, where $i,j\in V\setminus(s,t)$ is replaced by a long
edge $(i^{+},j^{-})$. Each edge $(s,i)$ is replaced by a long edge $(s,i^{-})$
and each edge $(i,t)$ is replaced by a long edge $(i^{+},t)$ for
$i=1,2,\ldots,n$. We note that two paths from $s$ to $t$ share a node $i$ in
$G$, if, and only if, the corresponding paths in $G^{*}$ share edge
$(i^{-},i^{+})$. The weights are moved from nodes in $G$ onto the
corresponding short edges in $G^{*}$: the weight of every short edge $e$
connecting nodes $i^{-},i^{+},\forall i\in V^{*}\setminus\\{s,t\\}$ is equal
to $-w_{i}$. The weight of each long edge is equal to zero. The capacity of
every edge (long and short) is set equal to $1$. Figure 3 illustrates the
obtained directed acyclic graph $G^{*}$ by applying the transformation
described above to graph $G$ of Figure 2.

Each collection of $k$ node disjoint $s-t$ paths in $G$ corresponds in a
natural way to a collection of $k$ edge-disjoint $s-t$ paths in $G^{*}$, with
corresponding paths having the same weight. Finding $k$ edge-disjoint $s-t$
paths with the minimum total weight is equivalent to finding a minimum-cost
flow with source $s$, destination $t$ and demand $k$, assuming unit edge
capacities. A collection of $k$ node-disjoint $s-t$ paths in $G^{*}$ (which
must be also edge-disjoint) with minimum total weight gives an optimal
schedule for $k$ robots in the BCP.

A collection of $k$ node-disjoint paths from $s$ to $t$ in $G^{*}$ with the
minimum total weight can be found in $O(kn^{2})$ time by the successive
shortest path algorithm [10]. For $k=1$ and the unweighted BCP, that is, when
we are looking for a shortest $s-t$ path in $G$ and all nodes have weight
equal to $1$, it is shown in [1] that such a path can be found in $O(n\log n)$
time by using the special geometric representation of graph $G$ described in
Section 2.2. For $k=1$ and the weighted BCP computing a shortest $s-t$ path in
$G$ requires $O(n^{2})$ time. For $k\geq 2$, [1] gives only the
straightforward $O(kn^{2})$ computation as indicated above which applies both
to the weighted and unweighted case. The main contributions of our work is
that the geometric representation of graph $G$ can lead also to efficient
algorithms for the weighted BCP and $k\geq 1$.

Figure 3: Directed Acyclic Graph $G^{*}$ with $2n+2$ nodes. The weight of a
short edge $(x^{-},x^{+})$ is equal to $-w_{x}$ (for clarity we assume that
$w_{x}=1$ $\forall x\in V^{*}$). The weight of a long edge $(x,y)$ is equal to
$0$.

###  2.2 The plane representation of DAG $G^{*}$

It was shown in [1] that the directed acyclic graph $G$ (and graph $G^{*}$)
can be implicitly represented with a set of points ${\cal{P}}$ on the
Euclidean 2-D plane. There are $2n+2$ points in ${\mathcal{P}}$ which
correspond to the nodes in graph $G^{*}$. There are two special points $s$ and
$t$ which correspond to the special nodes in $G^{*}$. The remaining $2n$
”regular” points can be seen as $n$ pairs of points
$(1^{-},1^{+}),...,(n^{-},n^{+})$. For $i=1,2,...,n$, a pair of points
$(i^{-},i^{+})$ in $\cal{P}$ corresponds to pair of nodes $(i^{-},i^{+})$ in
$G^{*}$ and therefore corresponds to ball $b_{i}$ of the BCP input. Because of
this correspondence, we will use the terms ball, node and point (in
${\mathcal{P}}$) interchangeably (remembering that the special nodes/points
$s$ and $t$ do not correspond to any ball). The placement of a pair of points
$(i^{-},i^{+})\in\cal{P}$ in the $2$-D plane is described with coordinates
$\alpha$ and $\beta$ defined in the following way:

  * •

$\alpha_{i}=t_{i}+x_{i}\quad$ and $\quad\beta_{i}=t_{i}-x_{i}$

  * •

$\alpha_{i}^{+}=\alpha_{i},\quad\beta_{i}^{+}=\beta_{i}\quad$ and
$\quad\alpha_{i}^{-}=\alpha^{+}_{i}-\epsilon,\quad\beta_{i}^{-}=\beta_{i}^{+}-\epsilon$

where $\epsilon$ is an arbitrary small number to ensure that $i^{-}$ and
$i^{+}$ are sufficiently ”close” to each other such that there is no point
$j\neq i$ satisfying $\alpha_{i}^{-}\leq\alpha_{j}\leq\alpha_{i}^{+}$ or
$\beta_{i}^{-}\leq\beta_{j}\leq\beta_{i}^{+}$. This transformation essentially
consists of rotating the location-time coordinates by $45^{\circ}$ to the new
system of $\alpha$-$\beta$ coordinates – see Figure 1(b).

To simplify matters we will refer to pair of points $(i^{-},i^{+})$ by simply
referring to point $i$. Figure 4(a) shows the $\alpha-\beta$ planar
representation of the directed acyclic graph $G^{*}$ shown in Figure 3 (for
clarity we do not show the splitting of points into two). The $\alpha-\beta$
planar representation (which can be constructed in $\Theta(n)$ time),
implicitly represents the directed acyclic graphs $G$ and $G^{*}$. There is an
edge in $G$ from node $i$ to node $j$, if, and only if, a robot can intercept
ball $b_{j}$ after intercepting ball $b_{i}$. This means that
$t_{i}-t_{j}\geq|x_{i}-x_{j}|$, which is equivalent to having
$\alpha_{i}\geq\alpha_{j}$ and $\beta_{i}\geq\beta_{j}$.

(a)

(b)

Figure 4: Figure 4(a) shows the implicit plane representation of $G^{*}$ in
the $\alpha-\beta$ coordinate system. Figure 4(b) shows the transformation of
the input such that all points have distinct integer $\alpha$ and $\beta$
coordinates.

We want the set of points $\cal{P}$ to represent correctly the topology (the
edges) of graph $G^{*}$, but otherwise the values of the coordinates of the
points in $\cal{P}$ are not important. We can therefore assume that $s=(0,0)$,
$t=(n+1,n+1)$, each regular point in $\cal{P}$ has integral coordinates and
any two distinct points in $\cal{P}$ have both coordinates distinct. This can
be achieved by sorting the $\alpha$ and $\beta$ coordinates of all points in
$\cal{P}$ and setting the value of the $m^{th}$ smallest $\alpha$ (resp.
$\beta$) coordinate equal to $m$, where $m=1,2,..,n$.

Notice that two points $i$ and $j$ can not have the same $\alpha$ and $\beta$
coordinate because this implies that balls $b_{i}$ and $b_{j}$ cross the line
$L$ at the same time at the distance from the origin and thus $b_{i}$ and
$b_{j}$ correspond to the same point $i$. It is possible however for two
points $i$ and $j$ in $\cal{P}$ to share the same $\alpha$ or $\beta$
coordinate. If for two points $i$ and $j$ in $\cal{P}$ we have
$\alpha_{i}=\alpha_{j}$ (resp. $\beta_{i}=\beta_{j}$) but
$\beta_{i}\leq\beta_{j}$ (resp. $\alpha_{i}\leq\alpha_{j}$) then to ensure
that $\cal{P}$ represents correctly the topology (the edges) of graph $G^{*}$
we set the value of $\alpha_{i}$ equal to $m$ and the value of $\alpha_{j}$
equal to $m+1$. Figure 4(b) illustrates an example of the replacement of the
$\alpha$ and $\beta$ coordinates with integral values(for clarity we do not
show the splitting of points into two).

For two points $i$ and $j$ in the plane, with coordinates
$(\alpha_{i},\beta_{i})$ and $(\alpha_{j},\beta_{j})$, respectively, we write
$i\prec j$ to denote that point $j$ dominates point $i$ in the sense that
$i\neq j$, $\alpha_{i}\leq\alpha_{j}$ and $\beta_{i}\leq\beta_{j}$. We write
$i\bowtie j$ to denote that points $i$ and $j$ are distinct and neither
$i\prec j$ nor $j\prec i$. We have $(0,0)=s\prec t$ and for each regular point
$i$ in ${\cal{P}}$, $s\prec i\prec t$. Thus for any two points $i$ and $j$ in
$\cal{P}$ (regular or special) $(i,j)$ is an edge in $G^{*}$ if, and only if,
$i\prec j$.

##  3 Algorithm $\mathcal{A}_{k}$

###  3.1 Input and Output

Consider the implicit representation of the directed acyclic graph $G^{*}$
with the points in $\mathcal{P}$. The edges of $G^{*}$ are represented by
straight-line segments in the $\alpha$-$\beta$ plane.

######  Definition 1.

We say that two node-disjoint edges $(u,v)$ and $(x,y)$ in $G^{*}$ _cross_ ,
if the two (closed) segments $[u,v]$ and $[x,y]$ in the plane have a common
point.

Recall that we can assume w.l.o.g. that the $\alpha$ coordinates and the
$\beta$ coordinates of the $n$ nodes are distinct integers in $[1,n]$ (see
subsection 2.2). We also assume that all points are in general position (the
reduction to achieve this requires increasing the range of the integer
coordinates). Therefore, if two edges node-disjoint edges $(u,v)$ and $(x,y)$
in $G^{*}$ cross then the common point of the closed segments does not
correspond to a point in $\mathcal{P}$. We say that two paths $Q$ and
$Q^{\prime}$ in $G^{*}$ _cross_ , if there is an edge $(u,v)\in Q$ crossing
with an edge $(x,y)\in Q^{\prime}$. We say that a path $Q$ in $G^{*}$ is non-
self-crossing if $Q$ does not traverse two edges that cross.

To provide an overview of our algorithm in the context of the minimum cost
flow problem, we denote by $\mathcal{N}$ the flow network based on graph
$G^{*}$, as discussed in subsection 2.1, with negative node weights (i.e.
weights of the short edges) and all edges (short and long) having unit
capacities. For network $\mathcal{N}$ and $k-1$ node-disjoint $s$-$t$ paths
$\mathcal{Y}_{1},\mathcal{Y}_{2},$ $\ldots,$ $\mathcal{Y}_{k-1}$ in
$\mathcal{N}$, which represent an integral flow of value $k-1$ in
$\mathcal{N}$, we define the residual network ${\mathcal{N}}_{k-1}$ in the
usual way, by reversing the edges of the paths
$\mathcal{Y}_{1},\mathcal{Y}_{2},\ldots,$ $\mathcal{Y}_{k-1}$. The base case
is $\mathcal{N}_{0}\equiv\mathcal{N}$.

We show an algorithm $\mathcal{A}_{k}$ which for an input
$(\mathcal{N};\mathcal{Y}_{1},\mathcal{Y}_{2},\ldots,\mathcal{Y}_{k-1})$,
where $\mathcal{Y}_{1},\mathcal{Y}_{2},$ $\ldots,$ $\mathcal{Y}_{k-1}$ are
$k-1$ node-disjoint _non-crossing_ $s$-$t$ paths minimizing the total weight
of any collection of $k-1$ _node-disjoint_ $s$-$t$ paths, computes a shortest
path tree $T^{*}$ rooted at $s$ in the residual network $\mathcal{N}_{k-1}$.
The paths $\mathcal{Y}_{1},\mathcal{Y}_{2},$ $\ldots,$ $\mathcal{Y}_{k-1}$ in
$\mathcal{N}$ are given in a left-right order in their plane representation.
We maintain two global arrays $h$ and $predecessor$, which are indexed by the
points $\mathcal{P}\setminus\\{s\\}$. At the end of the computation, for each
$x\in\mathcal{P}\setminus\\{s\\}$, the values $h(x)$ and $predecessor(x)$
should be the shortest path weight from $s$ to $x$ and the predecessor of
point $x$ in the tree $T^{*}$.

When $k=2$, we have only one path $\mathcal{Y}_{1}$, so the condition that
paths $\mathcal{Y}_{1},\mathcal{Y}_{2},$ $\ldots,$ $\mathcal{Y}_{k-1}$ are
_non-crossing_ is trivially satisfied. For subsequent values of $k$, this
condition will be ensured inductively. From now on, when we refer to paths
$\mathcal{Y}_{1},\mathcal{Y}_{2},$ $\ldots,$ $\mathcal{Y}_{k-1}$, we assume
that they are non-crossing paths representing a minimum-cost flow value of
$k-1$. The paths $\mathcal{Y}_{1},\mathcal{Y}_{2},$ $\ldots,$
$\mathcal{Y}_{k-1}$ in network $\mathcal{N}$ and the computed $s$-$t$ shortest
path in the residual network $\mathcal{N}_{k-1}$ give in the usual way a
minimum-cost flow of value $k$ in $\mathcal{N}$. This flow is represented by
$k$ node-disjoint $s$-$t$ paths $Y_{1},Y_{2},..,Y_{k}$ in $\mathcal{N}$, which
are not necessarily non-crossing. Let $\mathcal{P}_{k}\subseteq\mathcal{P}$
the set of all points covered by paths $Y_{1},Y_{2},..,Y_{k}$. The following
theorem states that a valid input for algorithm $\mathcal{A}_{k+1}$ exists and
can be computed in an efficient way.

######  Theorem 1.

Given a point set $\mathcal{P}_{k}$ such that all points $\mathcal{P}_{k}$ can
be covered with $k$ paths, there is an $O(kn\log n)$ algorithm
$\widetilde{U}_{k}$ which computes a collection of $k$ node-disjoint non-
crossing $s$-$t$ paths
$\mathcal{Y}_{1},\mathcal{Y}_{2},\ldots,\mathcal{Y}_{k}$ covering all points
in $\mathcal{P}_{k}$.

The proof of Theorem 1 is given separately in Section 6. Starting with the
network $\mathcal{N}$, we compute a minimum-cost integral flow of value $k$ in
$\mathcal{N}$, which gives a solution for BCP, by iterating algorithm
$\mathcal{A}_{i}$ followed by algorithm $\widetilde{U}_{i}$, for
$i=1,2,\ldots,k$. Algorithm $\mathcal{A}_{k}$ is an instance of the
_relaxation technique_ for the single-source shortest paths problem [11] in
the residual network $\mathcal{N}_{k-1}$. Arrays $h$ and $predecessor$ are
only updated by the following $\mbox{\it relax}(y,x)$ operation, where $(y,x)$
is an edge and $w(x)$ is the weight of node $x$: If $h(x)>h(y)+w(x)$, then
$h(x)\leftarrow h(y)+w(x)$ and $predecessor(x)\leftarrow y$.

In algorithm $\mathcal{A}_{k}$ relax operations occur in groups: $\mbox{\it
Relax}(x)\equiv\\{\mbox{\it relax}(y,x):y\prec x\\}$. The detailed description
of operation Relax and its implementation details are given in Subsection 3.3.
For the worst-case running-time efficiency, we implement operation $\mbox{\it
Relax}(x)$ not by performing explicitly all operations $\mbox{\it relax}(y,x)$
(this would take $O(n)$ time), but by finding a point $z\prec x$ such that
$h(z)=\min\\{h(y):y\prec x\\}$ and performing only $\mbox{\it relax}(z,x)$.
Finding point $z$ takes $O(\log^{3}(n))$ time using a data structure
introduced for the two-dimensional orthogonal-search problem[12].

###  3.2 Overview of Algorithm $\mathcal{A}_{k}$

In this section we give an overview of algorithm $\mathcal{A}_{k}$ for $k\geq
3$. The detailed description and the analysis of algorithm $\mathcal{A}_{k}$
for $k\geq 3$ is given in section 5. The analysis of algorithm
$\mathcal{A}_{k}$ for the special case $k=2$ is given separately in section 4.
This special case does not refer to some of the elaborations of the general
case, so the arguments are simpler and shorter, and can be treated as
preliminaries to the general case.

To facilitate the recursive structure of algorithm ${\mathcal{A}_{k}}$, we
extend the input specification to a sub-network of $\mathcal{N}_{k-1}$ induced
by the points in $\mathcal{P}$ with the $\beta$ coordinates in the interval
$(\beta_{1},\beta_{2}]$, for given $\beta_{1}<\beta_{2}$. We denote this sub-
network by
$(\mathcal{N};\mathcal{Y}_{1},\mathcal{Y}_{2},\ldots,\mathcal{Y}_{k-1})[\beta_{1},\beta_{2}]$,
or $\mathcal{N}[\beta_{1},\beta_{2}]$ for short. The initial input, that is,
the input to the initial call to algorithm ${\mathcal{A}_{k}}$, is the whole
residual network $\mathcal{N}_{k-1}$ which is defined by the interval
$(0,n+1]$.

Arrays $h$ and $predecessor$ are global and initialized outside of the
computation of algorithm ${\mathcal{A}_{k}}$ (details of this global
initialisation are in subsection 3.3). The subsequent recursive calls to
${\mathcal{A}_{k}}$ continue from the current state of these arrays, without
re-initialising. More precisely, when algorithm $\mathcal{A}_{k}$ is applied
to a sub-network $\mathcal{N}^{\prime}=\mathcal{N}[\beta_{1},\beta_{2}]$ (a
recursive call), then the computation starts with each point $x$ in
$\mathcal{N}^{\prime}$ having some value $h(x)\leq 0$, and array $predecessor$
restricted to $\mathcal{N}^{\prime}$ representing a forest in
$\mathcal{N}^{\prime}$. At the end of the computation, for each point $x$ in
the sub-network, $h(x)$ is equal to the weight of some path to $x$, hopefully
smaller than its starting value, and array $predecessor$ represents a new
forest.

A call to algorithm ${\mathcal{A}_{k}}$ for a sub-network
$\mathcal{N}[\beta_{1},\beta_{2}]$ includes two recursive calls to
${\mathcal{A}_{k}}$ applied to sub-networks
$\mathcal{N}[\beta_{1},(\beta_{1}+\beta_{2})/2]$ and
$\mathcal{N}[(\beta_{1}+\beta_{2})/2,\beta_{2}]$. We denote by
$\mathcal{N}_{1}$ and $\mathcal{N}_{2}$ these two sub-networks, respectively,
or the sets of nodes (points) in these sub-networks, depending on the context.
The sub-network $\mathcal{N}_{1}$ (the lower half) has $\lceil 2n/2\rceil$
points from $\mathcal{P}$ and the sub-network $\mathcal{N}_{2}$ (the upper
half) has $\lfloor 2n/2\rfloor$ points from $\mathcal{P}$.

The base case of the recursion are sub-problems of size smaller than some
constant threshold. Algorithm $\mathcal{A}_{k}$ also includes a coordination
phase which takes place between the two recursive calls and consists of
calling a coordination algorithm $\mathcal{C}_{k}$ on
$\mathcal{N}[\beta_{1},\beta_{2}]$.

While the recursive calls to algorithm $\mathcal{A}_{k}$ on $\mathcal{N}_{1}$
and $\mathcal{N}_{2}$ consider paths which are wholly either in
$\mathcal{N}_{1}$ or $\mathcal{N}_{2}$, the coordination algorithm
$\mathcal{C}_{k}$ is responsible for considering paths which have points both
in $\mathcal{N}_{1}$ and $\mathcal{N}_{2}$. Putting everything together, when
algorithm $\mathcal{A}_{k}$ is applied to a sub-network
$\mathcal{N}[\beta_{1},\beta_{2}]$ the computation consists of three phases.
The first phase is the recursive call of algorithm $\mathcal{A}_{k}$ to sub-
network $\mathcal{N}_{1}$, the second phase is the coordination of
$\mathcal{N}_{1}$ and $\mathcal{N}_{2}$ by algorithm $\mathcal{C}_{k}$ and the
third phase is the recursive call of algorithm $\mathcal{A}_{k}$ to
$\mathcal{N}_{2}$.

######  Definition 2.

We say that the computation of a shortest-path algorithm, or a part of such
algorithm, follows a given path $Q=(x_{0},x_{1},\ldots,x_{m})$, if the
computation includes all relax operations $\mbox{\it relax}(x_{i},x_{i+1})$,
$i=1,2,\ldots,m-1$ in this order.

Note that each operation $\mbox{\it relax}(x_{i},x_{i+1})$ may be implicitly
included within operation $\mbox{\it Relax}(x_{i+1})$. Recall that for a sub-
network $\mathcal{N}[\beta_{1},\beta_{2}]$ a path $Q$ in the sub-network is
non-self-crossing if $Q$ does not traverse two edges that cross.

######  Definition 3.

For a sub-network
$(\mathcal{N};\mathcal{Y}_{1},\mathcal{Y}_{2},\ldots,\mathcal{Y}_{k-1})[\beta_{1},\beta_{2}]$
and a point $v$ in this sub-network, we define path $\widetilde{Q}_{v}$ as the
minimum weight path among all non-self-crossing paths in this sub-network
which end at $v$. We denote by $\widetilde{h}(v)$ the weight of path
$\widetilde{Q}_{v}$.

The following theorem describes the specification of algorithm
$\mathcal{A}_{k}$.

######  Theorem 2.

When algorithm $\mathcal{A}_{k}$ is applied to a sub-network
$(\mathcal{N};\mathcal{Y}_{1},\mathcal{Y}_{2},\ldots,\mathcal{Y}_{k-1})[\beta_{1},\beta_{2}]$,
the computation follows every non-self-crossing path in this sub-network and
the running time is $O(k^{3k}n\log^{2k+3}n)$ where $n$ is the size of the sub-
network.

If the computation follows a path $Q=(x_{0},x_{1},\ldots,x_{m})$, then at the
end of this computation, the computed shortest path weight $h(x_{m})$ is at
most the weight of $Q$. Theorem 2 implies the following corollary.

######  Corollary 1.

When the call of algorithm $\mathcal{A}_{k-1}$ on a sub-network
$(\mathcal{N};\mathcal{Y}_{1},\mathcal{Y}_{2},\ldots,\mathcal{Y}_{k-1})[\beta_{1},\beta_{2}]$
terminates for every point $v$ in the sub-network we have
$h(v)\leq\widetilde{h}(v)$.

The proof of Theorem 2 consists of showing that the computation of
$\mathcal{A}_{k}(\,\mathcal{N}[\beta_{1},\beta_{2}]\,)$ follows every non-
self-crossing path in $\mathcal{N}[\beta_{1},\beta_{2}]$. First we analyse the
combinatorial structure of a non-self crossing path $Q$ by considering its
geometric representation on the $\alpha-\beta$ plane and then we show how the
consecutive computational phases of algorithm $\mathcal{A}_{k}$ follow the
consecutive sections of path $Q$.

To use Theorem 2 to conclude that algorithm $\mathcal{A}_{k}$ applied to the
whole residual network $\mathcal{N}_{k-1}$ is correct, that is, that the
computed tree is indeed a shortest path tree in $\mathcal{N}_{k-1}$, we need
Theorem 3 (given below) which asserts that there are non-self-crossing
shortest paths in $\mathcal{N}_{k-1}$. To simplify the presentation of a non-
self-crossing path followed by algorithm $\mathcal{A}_{k}$ (not necessarily a
shortest path) we distinguish between _red_ and _black_ points and edges.

The red points and red edges are the points and edges on the paths
$\mathcal{Y}_{1},\mathcal{Y}_{2},\ldots,\mathcal{Y}_{k-1}$. All other points
and edges are black. Recall that in the residual network $\mathcal{N}_{k-1}$,
the red edges (short and long) of the paths
$\mathcal{Y}_{1},\mathcal{Y}_{2},\ldots,\mathcal{Y}_{k-1}$ have reversed
direction and negated weights, as in the standard way. That is, a long red
edge $(u,v)\in\mathcal{Y}_{j}$ where $j\in[1,k-1]$ such that $u\prec v$ has
weight equal to $0$ and reversed direction from $v$ to $u$. A short edge
$(u^{-},u^{+})$ has direction from $u^{+}$ to $u^{-}$ and weight equal to
$w_{u}$.

######  Theorem 3.

For a sub-network $\mathcal{N}[\beta_{1},\beta_{2}]$, there exists a non-self-
crossing shortest path to every point $v$ in the sub-network.

###### Proof.

For a sub-network $\mathcal{N}[\beta_{1},\beta_{2}]$ consider a point $v$ in
this sub-network. Among all shortest paths to point $v$ let $Q^{*}$ be the
shortest path with the minimum number of edges. We claim that $Q^{*}$ is non-
self-crossing. Assume towards contradiction that $Q^{*}$ is self-crossing.

Recall that each point $x$ is a pair of points $(x^{-},x^{+})$ connected with
a short edge of capacity $1$. We denote by $h(x)$ the weight of the sub-path
of $Q^{*}$ to point $x^{+}$ and by $h^{-}(x)$ the weight of the sub-path of
$Q^{*}$ to point $x^{-}$. Notice that if $x$ is a black point then the path to
$x^{+}$ must traverse the short residual edge $(x^{-},x^{+})$ with weight
$-w_{x}<0$. Therefore we have that $h(x)=h^{-}(x)-w_{x}$. If $x$ is a red
point then the short edge $(x^{+},x^{-})$ is not residual and its weight is
equal to $w_{x}>0$, which means that the path to $x^{+}$ can not traverse the
short red edge $(x^{+},x^{-})$ and therefore we have $h(x)\leq h^{-}(x)\leq
h(x)+w(x^{+},x^{-})$.

It is easy to see that if $Q^{*}$ is self-crossing then it must traverse at
least on red edge of a path $\mathcal{Y}_{j}$ where $j\in[1,k-1]$. Notice that
since paths $\mathcal{Y}_{1},\mathcal{Y}_{2},\ldots,\mathcal{Y}_{k-1}$ are
non-crossing pairwise, if $Q^{*}$ is self-crossing then either $Q^{*}$ has two
black edges $(u,v)$ and $(x,y)$ that cross (see Figure 5(a)) or a black edge
$(u,v)$ crossing with a red edge $(y,x)$ (see Figure 5(b)).

Without loss of generality, we assume that edge $(u,v)$ appears before edge
$(x,y)$ in $Q^{*}$. Let $\pi$ be the crossing point of edge $(u,v)$ and edge
$(x,y)$. Since $\pi$ is a point on the closed segment $[u,v]$ of the black
edge $(u,v)$ we have that $u\prec\pi$. Similarly, since $\pi$ is a point on
the closed segment $[x,y]$ of the black edge $(x,y)$ (resp. red edge $(y,x)$)
we have that $\pi\prec y$. Thus, we conclude that $u\prec y$. Symmetrically,
we obtain that $x\prec v$.

We first claim that $h(u)=h^{-}(y)$. If $h(u)<h^{-}(y)$, then consider the
path $Q_{u}^{\cup}\\{(u^{+},y^{-})\\}$ to point $y^{-}$ where $Q_{u}$ is the
sub-path of $Q^{*}$ to point $u^{+}$. The weight of the long edge
$(u^{+},y^{-})$ is equal to zero and since $h(u)<h^{-}(y)$, the weight of path
$Q_{u}\cup\\{(u^{+},y^{-})\\}$ is smaller than the weight of path $Q_{y}$
where $Q_{y}$ is the sub-path of $Q^{*}$ to point $y^{-}$. However, this makes
a contradiction that $Q_{y}$ is a shortest path to point $y^{-}$. If
$h(u)>h^{-}(y)$, then we obtain that $h^{-}(v)>h(x)$ since the weight of the
long edges $(u^{+},v^{-})$ and $(x^{+},y^{-})$ is equal to zero. Consider the
cycle $C=Q_{vx}\cup\\{(x^{+},v^{-})\\}$ where $Q_{vx}$ is the sub-path of
$Q^{*}$ from $v^{-}$ to $x^{+}$. If $h^{-}(v)>h(x)$ then the total weight of
cycle $C$ is negative. This makes a contradiction since there are no negative
cycles in the residual network.

Let $m^{*}$ be the number of edges in path $Q^{*}$. Consider the decomposition
of $Q^{*}$ into $Q_{u}\cup Q_{uy}\cup Q_{y}$ where $Q_{u}$ is the sub-path of
$Q^{*}$ from its starting point to point $u^{+}$, $Q_{uy}$ is the sub-path of
$Q^{*}$ from $u^{+}$ to $y^{-}$ and $Q_{y}$ is the sub-path of $Q^{*}$ from
$y^{-}$ to $v$. Consider the path $Q=Q_{u}\cup\\{(u^{+},y^{-})\\}\cup Q_{y}$
and let $m$ be the number of edges in path $Q$. Path $Q$ has the same weight
as $Q^{*}$ since $h(u)=h^{-}(y)$. Further, $m<m^{*}$ since the sub-path
$Q_{uy}$ consists of at least two edges. However, this makes a contradiction
since $Q^{*}$ is chosen as the shortest path to $v$ with the minimum number of
edges. ∎

(a)

(b)

Figure 5: Figures 5(a) and 5(b): The schematic representation of the proof for
Theorem 3.

Consider the computation of $\mathcal{A}_{k}(\mathcal{N}_{k-1})$, that is, the
initial call of algorithm $\mathcal{A}_{k}$ to the whole residual network
$\mathcal{N}_{k-1}$. The array $predecessor$ is initialised to some tree
rooted at $s$. The details of this initialisation are given in subsection 3.3.
Array $predecessor$ is updated only by the relax operation. Therefore, by the
general properties of the shortest-paths relaxation technique, since there are
no negative cycles in $\mathcal{N}_{k-1}$, the array $predecessor$ always
represents some tree. Let $h$ and $predecessor$ be the arrays when the
computation terminates. From Corollary 1, for every point $v$ in
$\mathcal{N}_{k-1}$, we have $h(v)\leq\widetilde{h}(v)$. From Theorem 3,
$\widetilde{h}(v)=h^{*}(v)$, where $h^{*}(v)$ is the weight of a shortest path
from $s$ to $v$ in $\mathcal{N}_{k-1}$. Therefore we have that $h^{*}(v)\leq
h(v)\leq\widetilde{h}(v)=h^{*}(v)$, so $h(v)=h^{*}(v)$. Thus, the computed
tree must be a shortest-path tree (from the general properties of the
relaxation technique: $h(v)$ is never smaller than the weight of the current
tree path from $s$ to $v$).

For the special case $k=1$, in Section 4 we show an iterative algorithm
$\mathcal{A}_{1}$ with the running time of $O(n\log^{3}n)$ which considers all
points in topological order (two points $x$ and $x^{\prime}$ are in
topological order if $x\prec x^{\prime}$) and for each point $x$ performs
operation $\mbox{\it Relax}(x)$. Algorithm $\mathcal{A}_{1}$ essentially
implements the standard methodology111For any directed acyclic graph (DAG)
$G$, a shortest path between two points in $G$ can be computed by traversing
the nodes in topological order and for each node $v$ perform operation relax
in all edges outgoing from $v$. of computing a shortest path in a directed
acyclic graph, but accounts for incoming edges (instead of outgoing edges)
using operation $\mbox{\it Relax}(x)$. A topological order of the points can
be found in $O(n\log n)$-time as shown in [1]. Operation $\mbox{\it Relax}(x)$
takes $O(\log^{3}(n))$ amortized time using a data structure for orthogonal-
search queries [12].

For $k\geq 2$ the proof of Theorem 2 is outlined below. For some
$\beta_{1},\beta_{2}$ such that $0\leq\beta_{1}\leq\beta_{2}\leq n+1$ consider
a sub-network $\mathcal{N}[\beta_{1},\beta_{2}]$ and let $Q$ be a non-self-
crossing path in this sub-network. Without loss of generality, we assume that
$Q$ has points both in $\mathcal{N}_{1}$ and $\mathcal{N}_{2}$.

######  Definition 4.

If path $Q$ starts in $\mathcal{N}_{1}$ then we define $x\in\mathcal{N}_{1}$
to be the last point in $Q$ such that all points before $x$ are in
$\mathcal{N}_{1}$. If path $Q$ starts in $\mathcal{N}_{2}$ we define
$x\in\mathcal{N}_{2}$ to be the starting point of $Q$.

######  Definition 5.

If path $Q$ ends in $\mathcal{N}_{1}$ then we define
$x^{\prime}\in\mathcal{N}_{1}$ to be the last point of $Q$. If path $Q$ ends
in $\mathcal{N}_{2}$ we define $x^{\prime}$ to be the first point of $Q$ in
$\mathcal{N}_{2}$ such that all points after $x^{\prime}$ are in
$\mathcal{N}_{2}$.

Notice that points $x$ and $x^{\prime}$ are always unique and well-defined for
any path $Q$ in a sub-network $\mathcal{N}[\beta_{1},\beta_{2}]$. Path $Q$ can
be decomposed into three parts $(Q_{x},q_{xx^{\prime}},Q_{x^{\prime}})$ where
$Q_{x}$ is the sub-path of $Q$ from its starting point to point $x$,
$q_{xx^{\prime}}$ is the sub-path of $Q$ from $x$ to $x^{\prime}$ and
$Q_{x^{\prime}}$ is the sub-path of $Q$ from point $x^{\prime}$ to its end
point. Following Definitions 4 and 5, observe that if $x$ is in
$\mathcal{N}_{1}$ then the sub-path $Q_{x}$ has only points in
$\mathcal{N}_{1}$ and if $x$ is in $\mathcal{N}_{2}$ then $Q_{x}$ is empty.
Similarly, if $x^{\prime}$ is in $\mathcal{N}_{2}$ then all points in the sub-
path $Q_{x^{\prime}}$ are in $\mathcal{N}_{2}$ and if $x^{\prime}$ is in
$\mathcal{N}_{1}$ then $Q_{x^{\prime}}$ is empty. The sub-path
$q_{xx^{\prime}}$ has points both in $\mathcal{N}_{1}$ and $\mathcal{N}_{2}$
and it is empty if $x=x^{\prime}$.

Theorem 4 describes the specification of the coordination algorithm
$\mathcal{C}_{k}$. Using Theorem 4, the proof of Theorem 2 follows by double
induction on both parameter $k$ and the size of the network $n$.

######  Theorem 4.

For $k\geq 2$, assuming that Theorem 2 is true for $k-1$, when algorithm
$\mathcal{C}_{k}$ is applied to a sub-network
$(\mathcal{N};\mathcal{Y}_{1},\mathcal{Y}_{2},\ldots,\mathcal{Y}_{k-1})[\beta_{1},\beta_{2}]$
the computation follows the sub-path $q_{xx^{\prime}}$ of every non-self-
crossing path $Q$ in this sub-network.

We say that the sub-path $q_{xx^{\prime}}$ of $Q$ crosses from
$\mathcal{N}_{2}$ to $\mathcal{N}_{1}$ if it traverses a red edge
$(u,u^{\prime})\in\mathcal{Y}_{j},j\in[1,k-1]$ such that $u\in\mathcal{N}_{2}$
and $u^{\prime}\in\mathcal{N}_{1}$. Notice that for $k\geq 2$ there are
exactly $k-1$ red edges
$(u_{1},u^{\prime}_{1}),\ldots,(u_{k-1},u^{\prime}_{k-1})$ that cross from
$\mathcal{N}_{2}$ to $\mathcal{N}_{1}$. The proof of Theorem 4 depends on the
fact that for a sub-network $\mathcal{N}[\beta_{1},\beta_{2}]$, the sub-path
$q_{xx^{\prime}}$ can cross at most $(k-1)$ times from $\mathcal{N}_{2}$ to
$\mathcal{N}_{1}$ (as each such crossing traverse one of the $k-1$ red edges
from $\mathcal{N}_{2}$ to $\mathcal{N}_{1}$) and on the analysis of the
structure of a non-self-crossing path $Q$.

##### Computational Example

To resolve any ambiguity, in Figures 6(a), 6(b), 6(c) and 6(d) we show an
example of the input and output of algorithm $\mathcal{A}_{k}$ for the special
case $k=2$. Figure 6(a) shows the implicit representation of the residual
network $\mathcal{N}_{k-1}$ for $k=2$. The red segment represents path
$\mathcal{Y}_{1}=(s,y_{2},y_{3},y_{4},y_{5},t)$.

For clarity we do not show the black edges (long and short). Further, to
simplify matters, we assume that the weight of each point $i$ is equal to $1$.
That is, the weight of a black short edge $(i^{-},i^{+})$ is equal to $-1$ and
the weight of a red short edge is equal to $1$.

Figure 6(b) shows the shortest path tree $T$ computed by algorithm
$\mathcal{A}_{2}$ in the residual network $\mathcal{N}_{1}$. The computed
shortest path from $s$ to $t$ in $T$ is path
$Q=(s,b_{3},b_{4},y_{4},y_{3},y_{2},b_{2},b_{5},b_{6},t)$. Figure 6(c) shows
the two optimal node-disjoint paths $Y_{1}$ and $Y_{2}$ (which can cross) in
$\mathcal{N}$ if we obtain the flow for $k=2$ in the usual way.

Finally, Figure 6(d) shows the resulting collection of two optimal node-
disjoint, non-crossing paths $\mathcal{Y}_{1}$ and $\mathcal{Y}_{2}$ in
$\mathcal{N}$ obtained by the additional post-processing algorithm
$\widetilde{U}_{2}$, which will be the input for algorithm
$\mathcal{A}_{3}$.222Observe that we need at least 3 robots to collect balls
$b_{3},b_{4}$ and $y_{3}$ and the schedule shown for two robots collects every
ball except $y_{3}$ so it must be optimal.

To conclude that algorithm $\mathcal{A}_{2}$ computes a shortest path from $s$
to $t$ in the residual network, we will show that the sequence of relax
operations executed during the computation includes a sub-sequence of relax
operations which corresponds, or ’follows’, a non-self-crossing shortest path.
For the example shown in Figures 6(a),6(b),6(c) and 6(d), this sub-sequence of
relax operations is
$(s,b_{3}),(b_{3},b_{4}),(b_{4},y_{4}),(y_{4},y_{3}),(y_{3},y_{2}),(y_{2},b_{2}),(b_{2},b_{5}),(b_{5},b_{6}),(b_{6},t)$.
Notice that only the relative order of these relax operations is important.

(a)

(b)

(c)

(d)

Figure 6: Figure 6(a),6(b),6(c) and 6(d) show a computational example of
algorithm $\mathcal{A}_{k}$ for $k=2$.

###  3.3 Implementation Details

Before we discuss the implementation details of algorithm $\mathcal{A}_{k}$ we
remind the reader the structural details of the residual network
$\mathcal{N}_{k-1}$. Recall that all nodes and edges of the paths
$\mathcal{Y}_{1},\mathcal{Y}_{2},\ldots,$ $\mathcal{Y}_{k-1}$ are red. All
other nodes and edges are black. As discussed in subsection 2.1, the node set
$V(\mathcal{N}_{k-1})\setminus{\\{s,t\\}}$ consists of $n$ pairs of nodes
$(1^{-},1^{+}),(2^{-},2^{+}),\ldots,(n^{-},n^{+})$ connected with a short
edge. To simplify matters, we refer to a pair of nodes $(x^{-},x^{+})$ as a
pair node $x$ in $\mathcal{N}_{k-1}$ or as a pair point $x$ in $\mathcal{P}$,
depending on the context.

For two pair nodes $x$ and $y$, if the residual network $\mathcal{N}_{k-1}$
has an edge $(y,x)$, then for the corresponding pair points $x$ and $y$ in
$\mathcal{P}$ we say that $x$ dominates $y$ which is denoted by $y\prec x$.
For two pair points $y$ and $x$ such that $y\prec x$, the residual network
$\mathcal{N}_{k-1}$ has either a long black edge $(y^{+},x^{-})$ or a long red
edge $(x^{-},y^{+})$ (the latter if edge $(y,x)\in\mathcal{Y}_{j}$ where
$j\in[1,k-1]$), with weight equal to zero.

For a black pair node $x$, the weight of the short edge $(x^{-},x^{+})$ is
equal to $-w_{x}<0$. For a red pair node $x$ the short edge $(x^{-},x^{+})$
has reversed direction from $x^{+}$ to $x^{-}$ and weight equal to $w_{x}>0$.
The capacity of every edge regardless of colour (red or black) or type (long
or short) is equal to $1$.

##### Initialisation of arrays $h$ and $pred$

Consider the two arrays $h$ and pred, which are indexed by the nodes
$V(\mathcal{N}_{k-1})\setminus\\{s\\}$. For a pair node $x\in
V(\mathcal{N}_{k-1})\setminus\\{s\\}$, terms $h(x)$ and $h^{-}(x)$ denote the
current shortest path weight from the source $s$ to point $x^{+}$ and $x^{-}$,
respectively. Similarly, we denote by $\mbox{\it pred}(x)$ and $\mbox{\it
pred}^{-}(x)$ the predecessor of node $x^{+}$ and $x^{-}$ in the current tree.
We initialize arrays $h$ and pred in the following way.

For each black pair node $x\in V(\mathcal{N}_{k-1})$, we set $\mbox{\it
pred}^{-}(x)=s$, $h^{-}(x)=0$, $\mbox{\it pred}(x)=x^{-}$ and $h(x)=-w_{x}$.
For each red edge $(x^{-},y^{+})$ in $\mathcal{N}_{k-1}$ we set $\mbox{\it
pred}^{-}(x)=s$, $h^{-}(x)=0$, $\mbox{\it pred}(y)=x^{-}$ and $h(y)=0$. For
node $t$, we set $\mbox{\it pred}(t)=s$ and $h(t)=0$. Finally, to have the
initial tree which reaches all nodes in $\mathcal{N}_{k-1}$, for each red edge
$(s,x^{-})$ in $\mathcal{N}_{k-1}$ , we set $\mbox{\it pred}^{-}(x)=x^{+}$ and
$h^{-}(x)=w_{x}$, and for each red edge $(t,x^{+})$ in $\mathcal{N}_{k-1}$, we
set $\mbox{\it pred}(x)=t$ and $h(x)=0$.

The initialization of arrays $h$ and pred described above is valid for the
relaxation technique since array pred defines a tree in $\mathcal{N}_{k-1}$
which is rooted at $s$ and for each node $x$ in $\mathcal{N}_{k-1}$ other than
$s$, $h(x)$ is the weight of the tree path from $s$ to $x$. An algorithm based
on the relaxation technique updates arrays $h$ and pred only by the following
classic $\mbox{\it relax}(y,x)$ operation [11]: if $h(x)>h(y)+w(y,x)$, then
$h(x)\leftarrow h(y)+w(y,x)$ and $\mbox{\it pred}(x)\leftarrow y$, where
$(y,x)$ is an edge in the input graph (or equivalently $y\prec x$), and
$w(y,x)$ is the weight of this edge. Notice that for an operation $\mbox{\it
relax}(x,y)$ edge $(x,y)$ can be either short or long.

At the end of the computation, for each node $x$, $h(x)$ (resp. $h^{-}(x)$)
should be equal to the shortest-path weight from $s$ to $x$ (resp. $x^{-}$),
and array pred should represent a shortest path tree from the source $s$ to
all reachable nodes. Since we want to compute a shortest path from $s$ to $t$,
we will only require (and we will verify in the proofs) that at the end of the
computation array pred includes a shortest path from $s$ to $t$ and that
values $h(x)$ and $h^{-}(x)$ are correct for each node $x$ on this path.

An algorithm based on operation $\mbox{\it relax}(x,y)$ computes a shortest
$s$-$t$ path for a given input network, if there is a shortest $s$-$t$ path
$(s=x_{0},x_{1},x_{2},\ldots,x_{q}=t)$ such that the sequence of relax
operations executed by the algorithm includes as a sub-sequence $\mbox{\it
relax}(x_{i-1},x_{i})$, $i=1,2,\ldots,q$. Only the relative order of such
operations $\mbox{\it relax}(x_{i-1},x_{i})$ is important, but they do not
have to be consecutive. They can be interleaved in arbitrary way with any
number of other relax operations.

##### Two-Dimensional Orthogonal Search Problem

In the Two-Dimensional Orthogonal Search Problem we are given a set $S$ of $n$
points in a two dimensional plane where each point $i$ for $i=1,2,\ldots,n$ is
identified with two coordinates $(x_{i},y_{i})$ and a weight value $u_{i}$.
Given a rectangle query $R=[x_{1},x_{2}]$x$[y_{1},y_{2}]$ the orthogonal
search problem asks for the point $j$ within $R$ that has the minimum weight
value $u_{j}$. The operation of retrieving the point with the minimum $u$
value within $R$, can be seen as an answer to a query which has to be
completed relatively fast.

We want to store all points in $S$ in a data structure such that given a query
(i.e. a rectangle $R$) we can perform the two basic operations: (i) Report the
point with the minimum weight value within rectangle $R$ and (ii) Update the
weight value of a given point in $S$. In such data structures the operations
would usually be either only queries (the static version of the problem) or
queries and insertions and deletions of points (the dynamic version of the
problem). When we update the weight value of a point $i$ from $u_{i}$ to
$u^{\prime}_{i}$ in $S$, we assume that we delete point $i$ and add a new
point $i^{{}^{\prime}}$ with weight $u^{\prime}_{i}$.

A variety of dynamic data structures such as range trees [13] [14] [15],
layered range trees[16] [12] and weight balanced trees[17] have been designed
for dynamic and static versions of the Orthogonal Searching Problem. In [13]
it was shown that the asymptotic upper bound of the time to respond to one
query (i.e report the minimum weight point within a rectangle $R$) is
$O(\log^{3}(n))$ in the case of a two dimensional space. Furthermore, it was
shown that the upper bound on the running time of a sequence of $n$ operations
which can be queries, insertions and deletions is $O(n\log^{2}n)$.

##### Operation Relax

When algorithm ${\mathcal{A}_{k}}$ is applied to a sub-network
$\mathcal{N}[\beta_{1},\beta_{2}]$ of the residual network
$\mathcal{N}_{k-1}$, operations relax are grouped together for the edges
incoming to the same pair node. For a pair node $x$, we define operation
$\mbox{\it Relax}(x)$ as a sequence of all operations $\\{\mbox{\it
relax}(y^{+},x^{-}):(y^{+},x^{-})\in\mathcal{N}[\beta_{1},\beta_{2}]\\}$, in
arbitrary (because not relevant) order, followed by the relax operation
applied to the residual edge outgoing from $x^{-}$ (if any). That edge is
either $(x^{-},x^{+})$, for a black pair node $x$, or $(x^{-},\pi_{x}^{+})$,
for a red pair node $x$ on a path $\mathcal{Y}_{j},j\in[1,k-1]$ with
predecessor $\pi_{x}$.

For the worst-case running-time efficiency, we implement operations
$\\{\mbox{\it
relax}(y^{+},x^{-}):(y^{+},x^{-})\in\mathcal{N}[\beta_{1},\beta_{2}]\\}$ not
by performing all of them explicitly (this would take $O(n)$ time) but by
finding the pair node $y_{min}$ such that
$h(y_{min})=\min\\{h(y):(y^{+},x^{-})\in\mathcal{N}[\beta_{1},\beta_{2}]\\}$
and performing only operation $\mbox{\it relax}(y^{+}_{min},x^{-})$. We keep
all pair nodes in $\mathcal{N}[\beta_{1},\beta_{2}]$ in a data structure for
answering rectangle queries [13]. The weight-value of a pair node $y$ in this
data structure is equal to the current shortest path weight $h(y)$.

For a sub-network $\mathcal{N}[\beta_{1},\beta_{2}]$ and a pair node $x$ in
this sub-network, we denote by $D_{x}[\beta_{1},\beta_{2}]$ the set of all
pair nodes $y$ in the sub-network such that there is an edge $(y^{+},x^{-})$,
or equivalently $y\prec x$. Notice that for a pair node $y\in
D_{x}[\beta_{1},\beta_{2}]$ the corresponding pair point $y$ in $\mathcal{P}$
must be within the rectangle $R_{x}=[0,\alpha_{x}]\times[\beta_{1},\beta_{x}]$
since $y\prec x$ (i.e. $\alpha_{y}\leq\alpha_{x}$ and
$\beta_{y}\leq\beta_{x}$). Thus, for a pair node $x$ finding pair node
$y_{min}$ in $D_{x}[\beta_{1},\beta_{2}]$ amounts to finding the minimum value
pair point in rectangle $R_{x}$.

For a black pair node $x$, finding pair node $y_{min}$ consists of answering
the rectangle query for $R_{x}$ since every edge
$(y^{+},x^{-})\in\mathcal{N}_{k-1}[\beta_{1},\beta_{2}]$ is a residual edge.
For a red pair node $x$ on some path $\mathcal{Y}_{j}$ where $j\in[1,k-1]$, we
first remove from the data structure the predecessor pair node $\pi_{x}$ of
$x$ on $\mathcal{Y}_{k}$ (since $(\pi_{x}^{+},x^{-})$ is not a residual edge),
then find $y_{min}$ by answering the rectangle query for $R_{x}$, and finally
re-insert $\pi_{x}$ back to the data structure. Each single operation on the
data structure from [13] (rectangle query, update of the value of a given
element, deleting a given element, or inserting a new element) takes
$O(\log^{3}n)$ time, so the running time of operation Relax is $O(\log^{3}n)$.

##  4 Shortest Path Algorithm $\mathcal{A}_{k}$ for $k=2$

In this section we consider the special case $k=2$ as an introduction to our
recursive approach. For a sub-network
$(\mathcal{N};\mathcal{Y}_{1})[\beta_{1},\beta_{2}]$ or
$\mathcal{N}[\beta_{1},\beta_{2}]$ for short, when algorithm $\mathcal{A}_{2}$
is applied to this sub-network, the computation consists of three phases.
Consider the two sub-networks $\mathcal{N}[\beta_{1},(\beta_{1}+\beta_{2})/2]$
and $\mathcal{N}[(\beta_{1}+\beta_{2})/2,\beta_{2}]$ which we denote by
$\mathcal{N}_{1}$ and $\mathcal{N}_{2}$, respectively. The first phase is the
recursive call of algorithm $\mathcal{A}_{2}$ on $\mathcal{N}_{1}$. The second
phase calls the coordination algorithm $\mathcal{C}_{2}$ on sub-network
$\mathcal{N}[\beta_{1},\beta_{2}]$. The third phase is the recursive call of
algorithm $\mathcal{A}_{2}$ on $\mathcal{N}_{2}$. The description of algorithm
$\mathcal{A}_{2}$ is shown in pseudo-code in Algorithm 1.

$\mathcal{N}_{1}\leftarrow\mathcal{N}[\beta_{1},(\beta_{1}+\beta_{2})/2];$
$\mathcal{N}_{2}\leftarrow\mathcal{N}[(\beta_{1}+\beta_{2})/2,\beta_{2}];$

$\mathcal{A}_{2}(\mathcal{N}_{1});$

$\mathcal{C}_{2}(\mathcal{N}[\beta_{1},\beta_{2}]);$

$\mathcal{A}_{2}(\mathcal{N}_{2});$

Algorithm 1 Algorithm $\mathcal{A}_{2}$ on input
$(\mathcal{N};\mathcal{Y}_{1})[\beta_{1},\beta_{2}]\equiv\mathcal{N}[\beta_{1},\beta_{2}]$

When algorithm $\mathcal{C}_{2}$ is applied to a sub-network
$\mathcal{N}[\beta_{1},\beta_{2}]$ the computation consists of three steps.
The first and third step call algorithm $\mathcal{A}_{1}$ on the sub-network
$\mathcal{N}[\beta_{1},\beta_{2}]\setminus\mathcal{Y}_{1}$ which denotes the
sub-network without the red edges of path $\mathcal{Y}_{1}$. The second step
calls algorithm $\Delta(\mathcal{Y}_{1})$ on the sub-network
$\mathcal{N}[\beta_{1},\beta_{2}]$. The computational steps of algorithm
$\mathcal{C}_{2}$ are described in pseudo-code in Algorithm 2.

For an input sub-network $\mathcal{N}[\beta_{1},\beta_{2}]$ algorithm
$\mathcal{A}_{1}$ consists of two steps. The first step computes a topological
order of all points in the sub-network using the $O(n\log n)$-time algorithm
of Asahiro. et al. [1]. The second step considers the points of the sub-
network in topological order, that is, for two points $v$ and $v^{\prime}$
such that $v\prec v^{\prime}$ point $v$ is considered first and when a point
$v$ is considered it performs operation $\mbox{\it Relax}(v)$ as described in
Sub-section 3.3.

For a sub-network $\mathcal{N}[\beta_{1},\beta_{2}]$, algorithm
$\Delta(\mathcal{Y}_{1})$ traverses the red edges of path $\mathcal{Y}_{1}$ in
the sub-network (if any) and performs operation relax on the red edges(long
and short). Specifically, let $y_{i}$ for $i=1,2,\ldots,m$ be the $i^{th}$ red
point on path $\mathcal{Y}_{1}$ in the sub-network, such that $y_{1}\prec
y_{2}\prec\ldots\prec y_{m}$. Algorithm $\Delta(\mathcal{Y}_{1})$ performs
operation $\mbox{\it relax}(y^{+}_{j},y^{-}_{j})$ and operation $\mbox{\it
relax}(y^{-}_{j},y^{+}_{j-1})$ for $j=m,m-1,\ldots,2$. For $j=1$ only
operation $\mbox{\it relax}(y^{+}_{j},y^{-}_{j})$ is performed since edge
$(y^{-}_{j},y^{+}_{j-1})$ does not exist.

$\mathcal{A}_{1}(\mathcal{N}[\beta_{1},\beta_{2}]\setminus\mathcal{Y}_{1});$

$\Delta(\mathcal{Y}_{1});$

$\mathcal{A}_{1}(\mathcal{N}[\beta_{1},\beta_{2}]\setminus\mathcal{Y}_{1});$

Algorithm 2 Algorithm $\mathcal{C}_{2}$ on input
$\mathcal{N}[\beta_{1},\beta_{2}]$

For a sub-network $\mathcal{N}[\beta_{1},\beta_{2}]$ we say that a path $Q$ is
non-chromatic (red-chromatic) if it traverses only black (red) edges. Lemmas 1
and 2 describe the specification of algorithms $\mathcal{A}_{1}$ and
$\Delta(\mathcal{Y}_{1})$, respectively.

######  Lemma 1.

When algorithm $\mathcal{A}_{1}$ is applied to a sub-network
$\mathcal{N}[\beta_{1},\beta_{2}]$ the computation follows every non-chromatic
path in the sub-network and the running time is $O(n\log^{3}n)$ where $n$ is
the size of the sub-network.

###### Proof.

Let $Q$ be a path in the sub-network $\mathcal{N}[\beta_{1},\beta_{2}]$ such
that $Q$ traverses only black edges. Consider the ordering of the edges
$(y_{1},y_{2})(y_{2},y_{3}),...,(y_{m-1},y_{m})$ in $Q$. Recall that every
point $v$ in sub-network $\mathcal{N}[\beta_{1},\beta_{2}]$ is a pair of
points $(v^{-},v^{+})$ which are connected with a short edge of capacity $1$.
We show that the computation of algorithm $\mathcal{A}_{1}$ includes a
sequence of relax operations on edges
$(y_{1}^{-},y_{1}^{+}),(y_{1}^{+},y^{-}_{2}),\ldots,(y_{m-1}^{+},y^{-}_{m}),(y_{1}^{-},y_{1}^{+})$
in this relative order.

For a black edge $(x,y)$ points $x$ and $y$ can be either black or red.
Therefore, if $Q$ includes a red point $v$ (i.e. a point on path
$\mathcal{Y}_{1}$) then $v$ must be either the starting or ending point of
$Q$. In detail, if the starting point $y_{1}$ of $Q$ is red, then the first
edge of $Q$ is edge $(y_{1}^{+},y_{2}^{-})$ and if the ending point $y_{m}$ of
$Q$ is red, then the last edge of $Q$ is edge $(y_{m-1}^{+},y^{-}_{m})$. This
is because the short red edges $(y^{-}_{1},y^{+}_{1})$ and
$(y^{-}_{m},y^{+}_{m})$ are not residual edges.

Because $Q$ traverses only black edges, for edge $(y_{i},y_{i+1})\in Q$ where
$i=1,2,\ldots,m-1$ it holds that $y_{i}\prec y_{i+1}$. Algorithm
$\mathcal{A}_{1}$ considers all points in the sub-network in topological order
and when a point $x$ is considered it performs operation $\mbox{\it
Relax}(x)$. Therefore, for any $i\in[1,m-1]$ and an edge $(y_{i},y_{i+1})\in
Q$ operation $\mbox{\it Relax}(y_{i})$ precedes operation $\mbox{\it
Relax}(y_{i+1})$.

For a point $x$ operation $\mbox{\it Relax}(x)\equiv\\{\mbox{\it
relax}(y^{+},x^{-}):y\in D_{x}[\beta_{1},\beta_{2}]\\}$ is equivalent to
sequence of operations $\mbox{\it relax}(y^{+},x^{-})$ for every point $y$ in
the sub-network such that $y\prec x$ (as defined in sub-section 3.3). Thus,
operation $\mbox{\it relax}(y_{i-1}^{+},y_{i}^{-})$ is implicitly included in
operation $\mbox{\it Relax}(y_{i})$ for $i=2,3,\ldots,m$. Further, for
$i=1,2,\ldots,m$ if point $y_{i}$ is black then operation $\mbox{\it
Relax}(y_{i})$ also includes operation $\mbox{\it
relax}(y_{i}^{-},y^{+}_{i})$. For the special case $i=1$(resp. $i=m$), if
point $y_{i}$ is red then the first (resp. last) relax operation in the
sequence is on edge $(y_{1}^{+},y^{-}_{2})$ (resp. $(y_{m-1}^{+},y^{-}_{m})$).

We conclude that the computation of algorithm $\mathcal{A}_{1}$ includes all
operations $\mbox{\it relax}(y_{i-1},y_{i})$ for $i=2,3,\ldots,m$ and all
operations $\mbox{\it relax}(y_{i}^{-},y_{i}^{+})$ for $i=1,2,\ldots,m$, in
this relative order. One operation Relax requires $O(\log^{3}n)$ where $n$ is
the size of the sub-network $\mathcal{N}[\beta_{1},\beta_{2}]$ and therefore
the total running time of algorithm $\mathcal{A}_{1}$ is $O(n\log^{3}n)$. ∎

######  Lemma 2.

When algorithm $\Delta(\mathcal{Y}_{1})$ is applied on a sub-network
$\mathcal{N}[\beta_{1},\beta_{2}]$ the computation follows every red-chromatic
path in the sub-network and the running time is $O(n)$ where $n$ is the size
of the sub-network.

###### Proof.

Algorithm let $m^{\prime}$ be the number of red points on path
$\mathcal{Y}_{1}$ and denote by $y_{i}$ for $i=1,2,\ldots,m$ the $i^{th}$ red
point such that $y_{1}\prec y_{2}\prec\ldots\prec y_{m}$. Let $Q$ be a path in
the sub-network such that $Q$ traverses only red edges. Denote by
$(y_{i},y_{i+1}),\ldots,(y_{j-1},y_{j})$ the ordering of the red edges in $Q$
where $i,j\in[1,m]$ and $j\leq i$. Algorithm $\Delta(\mathcal{Y}_{1})$
performs all relax operations
$(y^{+}_{m},y^{-}_{m})(y^{-}_{m},y^{+}_{m-1}),\ldots,(y^{-}_{2},y^{+}_{1}),(y^{+}_{1},y^{-}_{1})$.

The proof simply follows by induction for $k=i,i-1,\ldots,j$. Path
$\mathcal{Y}_{1}$ can have at most $n$ points and therefore it can have at
most $(n-1)$ edges. Operation relax takes constant time and therefore the
total time needed is $O(n)$. ∎

Recall that for sub-network $\mathcal{N}[\beta_{1},\beta_{2}]$ and a given
path $Q=(x_{0},x_{1},\ldots,x_{m})$, in this sub-network (not necessarily a
shortest path or an $s$-$t$ path) we say that the computation follows path
$Q$, if the computation includes all relax operations $\mbox{\it
relax}(x_{i},x_{i+1})$, $i=1,2,\ldots,m-1$ in this order. Each operation
$\mbox{\it relax}(x_{i},x_{i+1})$ may be implicitly included within operation
$\mbox{\it Relax}(x_{i+1})$. The following theorem describes the specification
of algorithm $\mathcal{A}_{2}$.

######  Theorem 5.

When algorithm $\mathcal{A}_{2}$ is applied to a sub-network
$\mathcal{N}[\beta_{1},\beta_{2}]$ the computation follows every path in the
sub-network and the running time is $O(n\log^{4}n)$ where $n$ is the size of
the sub-network.

Recall that if the computation follows path $Q=(x_{0},x_{1},\ldots,x_{m})$,
then at the end of this computation, the computed shortest path weight
$h(x_{m})$ is at most the weight of $Q$. Therefore, Theorem 5 implies that at
the termination of the computation of algorithm $\mathcal{A}_{2}$ on a sub-
network $\mathcal{N}[\beta_{1},\beta_{2}]$, for every point $v$ in the sub-
network we have $h(v)=h^{*}(v)$ where $h^{*}(v)$ is the weight of a shortest
path to $v$.

###  4.1 Proof of Theorem 5

For a sub-network $\mathcal{N}[\beta_{1},\beta_{2}]$ let $Q$ be a path in the
sub-network. Denote by $\mathcal{N}_{1}$ and $\mathcal{N}_{2}$ the sub-
networks $\mathcal{N}[\beta_{1},(\beta_{2}+\beta_{1})/2]$ and
$\mathcal{N}[(\beta_{2}+\beta_{1})/2,\beta_{2}]$, respectively. Without loss
of generality, we assume that $Q$ has points both in $\mathcal{N}_{1}$ and
$\mathcal{N}_{2}$.

Recall that according to Definition 4, if path $Q$ starts in $\mathcal{N}_{1}$
then we define $x\in\mathcal{N}_{1}$ to be the last point in $Q$ such that all
points before $x$ are in $\mathcal{N}_{1}$. If path $Q$ starts in
$\mathcal{N}_{2}$ we define $x$ to be the starting point of $Q$. Similarly,
according to Definition 5, if path $Q$ ends in $\mathcal{N}_{1}$ then we
define $x^{\prime}\in\mathcal{N}_{1}$ to be the ending point of $Q$. If path
$Q$ ends in $\mathcal{N}_{2}$ we define $x^{\prime}$ to be the first point of
$Q$ in $\mathcal{N}_{2}$ such that all points after $x^{\prime}$ are in
$\mathcal{N}_{2}$.

We can decompose $Q$ into the following parts
$Q_{x},q_{xx^{\prime}},Q_{x^{\prime}}$ where $Q_{x}$ is the sub-path of $Q$
from its starting point to point $x$, $q_{xx^{\prime}}$ is the sub-path of $Q$
from $x$ to $x^{\prime}$ and $Q_{x^{\prime}}$ is the sub-path of $Q$ from
point $x^{\prime}$ to the ending point of $Q$. Definition 4 implies that if
sub-path $Q_{x}$ is not empty then all points in $Q_{x}$ are in
$\mathcal{N}_{1}$. Similarly, Definition 5 implies that if $Q_{x^{\prime}}$ is
not empty then all points in $Q_{x^{\prime}}$ are in $\mathcal{N}_{2}$. The
proof of Theorem 5 is outlined below.

When algorithm $\mathcal{A}_{2}$ is applied to a sub-network
$\mathcal{N}[\beta_{1},\beta_{2}]$ the first phase of the computation is the
recursive call of algorithm $\mathcal{A}_{2}$ on $\mathcal{N}_{1}$. The second
phase of the computation calls algorithm $\mathcal{C}_{2}$ on sub-network
$\mathcal{N}[\beta_{1},\beta_{2}]$. Finally, the third phase of the
computation is the recursive call of algorithm $\mathcal{A}_{2}$ on
$\mathcal{N}_{2}$. The following theorem describes the specification of
algorithm $\mathcal{C}_{2}$.

######  Theorem 6.

When algorithm $\mathcal{C}_{2}$ is applied to a sub-network
$\mathcal{N}[\beta_{1},\beta_{2}]$ the computation follows the sub-path
$q_{xx^{\prime}}$ of every path $Q$ in the sub-network and the running time is
$O(n\log^{3}n)$ where $n$ is the size of the sub-network.

Figure 7: The structure of the sub-path $q_{xx^{\prime}}$ of $Q$ from $x$ to
$x^{\prime}$ if $q_{xx^{\prime}}$ crosses from $\mathcal{N}_{2}$ to
$\mathcal{N}_{1}$.

It remains to show the proof of Theorem 6 and to conclude the proof of Theorem
5. The following definitions facilitate the analysis of the combinatorial
structure of a path $Q$ in a sub-network $\mathcal{N}[\beta_{1},\beta_{2}]$,
followed by algorithms $\mathcal{C}_{2}$ and $\mathcal{A}_{2}$.

######  Definition 6.

For a path $Q$, a run $r$ is a maximal sub-path of $Q$ such that all edges in
$r$ are of the same colour.

A run is non-chromatic if it consists of black edges. A run is chromatic if
all of its edges are of red colour. Notice that an edge $e(u,u^{\prime})$ can
be traversed at most once by a (simple) path $Q$ and therefore we have the
following corollary.

######  Corollary 2.

Two chromatic runs $r$ and $r^{\prime}$ in $Q$ of the same colour $c_{i}$ are
edge-disjoint.

###### Proof of Theorem 6.

When algorithm $\mathcal{C}_{2}$ is applied to sub-network
$\mathcal{N}[\beta_{1},\beta_{2}]$ the computation consists of the following
three steps
$\mathcal{A}_{1}(\mathcal{N}[\beta_{1},\beta_{2}]),\Delta(\mathcal{Y}_{1}),\mathcal{A}_{1}(\mathcal{N}[\beta_{1},\beta_{2}])$.
Let $Q$ be a path in the sub-network $\mathcal{N}[\beta_{1},\beta_{2}]$ and
let $q_{xx^{\prime}}$ be the sub-path of $Q$ from $x$ to $x^{\prime}$. We show
that algorithm $\mathcal{C}_{2}$ follows path $q_{xx^{\prime}}$.

For $k=2$ there is a unique red edge $(u,u^{\prime})\in\mathcal{Y}_{1}$ such
that $u\in\mathcal{N}_{2}$ and $u^{\prime}\in\mathcal{N}_{1}$ crossing from
$\mathcal{N}_{2}$ to $\mathcal{N}_{1}$. We say that the sub-path
$q_{xx^{\prime}}$ of $Q$ crosses from $\mathcal{N}_{2}$ to $\mathcal{N}_{1}$
if it has a chromatic run that includes the red edge $(u,u^{\prime})$. We
consider two cases about the sub-path $q_{xx^{\prime}}$.

The first case is that $q_{xx^{\prime}}$ does not cross from $\mathcal{N}_{2}$
to $\mathcal{N}_{1}$ and the second case is that $q_{xx^{\prime}}$ crosses
from $\mathcal{N}_{2}$ to $\mathcal{N}_{1}$ exactly once. In the former case,
following the definition of points $x$ and $x^{\prime}$ the sub-path
$q_{xx^{\prime}}$ must consist of the single black edge $(x,x^{\prime})$.
Thus, according to Lemma 1 the computation of the first step of
$\mathcal{C}_{2}$, that is, the computation of algorithm $\mathcal{A}_{1}$,
follows the sub-path $q_{xx^{\prime}}$ since it traverses only one black edge.

In the latter case, the sub-path $q_{xx^{\prime}}$ must consist of the
following ordering of runs $(r_{b},r,r^{\prime}_{b})$ where $r_{b}$ and
$r^{\prime}_{b}$ are non-chromatic runs and $r$ is a red chromatic run which
includes the red edge $(u,u^{\prime})$. Thus, we can decompose
$q_{xx^{\prime}}$ into three parts
$(x,\pi^{*}_{1}),(\pi^{*}_{1},\tau^{*}_{1})$ and $(\tau^{*}_{1},x^{\prime})$
where $\pi^{*}_{1}$ and $\tau^{*}_{1}$ is the first and last point of the red
chromatic run $r$. An example of this decomposition is shown in Figure 7.

According to Lemma 1, the computation of the first step of $\mathcal{C}_{2}$,
that is, the computation of algorithm $\mathcal{A}_{1}$, follows the path from
$x$ to $\pi^{*}_{1}$ since it traverses only black edges. According to Lemma
2, the computation of the second step of $\mathcal{C}_{2}$, that is, algorithm
$\Delta(\mathcal{Y}_{1})$ follows the path from $\pi^{*}_{1}$ to
$\tau^{*}_{1}$ since it traverses only red edges. Finally, according to Lemma
1 the computation of the third step of $\mathcal{C}_{2}$, that is, algorithm
$\mathcal{A}_{1}$ follows the path from $\tau^{*}_{1}$ to $x^{\prime}$ since
it traverses only black edges.

The running time of algorithm $\mathcal{C}_{2}$ when applied to a sub-network
$\mathcal{N}[\beta_{1},\beta_{2}]$ of size $n$ is given by the following
relationship $T_{\mathcal{C}_{2}}(n)=2T_{\mathcal{A}_{1}}(n)+T_{\Delta}(n)$.
According to Lemma 1 and Lemma 2 we have that
$T_{\mathcal{A}_{1}}(n)=O(n\log^{3}n)$ and $T_{\Delta}(n)=O(n)$ and therefore
$T_{\mathcal{C}_{2}}(n)=O(n\log^{3}n)$. ∎

###### Proof of Theorem 5.

When algorithm $\mathcal{A}_{2}$ is applied to sub-network
$\mathcal{N}[\beta_{1},\beta_{2}]$ the computation consists of the following
three phases:
$\mathcal{A}_{2}(\mathcal{N}_{1}),\mathcal{C}_{2}(\mathcal{N}[\beta_{1},\beta_{2}]),\mathcal{A}_{2}(\mathcal{N}_{2})$
which denote the recursive call of algorithm $\mathcal{A}_{2}$ on
$\mathcal{N}_{1}$, the call of algorithm $\mathcal{C}_{2}$ on
$\mathcal{N}[\beta_{1},\beta_{2}]$ and the recursive call of algorithm
$\mathcal{A}_{2}$ on $\mathcal{N}_{2}$, respectively.

Let $Q$ be a path in this sub-network and consider the decomposition of $Q$
into $Q_{x},q_{xx^{\prime}},Q_{x^{\prime}}$. Recall that if sub-path $Q_{x}$
(resp. $Q_{x^{\prime}}$) is not empty then it must include points only in
$\mathcal{N}_{1}$ (resp. $\mathcal{N}_{2}$). By induction, Theorem 5 implies
that when algorithm $\mathcal{A}_{2}$ is applied to $\mathcal{N}_{1}$ then the
computation follows the sub-path $Q_{x}$ of $Q$ since it has points only in
$\mathcal{N}_{1}$. According to Theorem 6 when algorithm $\mathcal{C}_{2}$ is
applied to sub-network $\mathcal{N}[\beta_{1},\beta_{2}]$ the computation
follows the sub-path $q_{xx^{\prime}}$ of $Q$. Finally, by induction Theorem 6
implies that when algorithm $\mathcal{A}_{2}$ is applied to sub-network
$\mathcal{N}_{2}$ the computation follows the sub-path $Q_{x^{\prime}}$ of $Q$
since it has points only in $\mathcal{N}_{2}$.

The running time of algorithm $\mathcal{A}_{2}$ when applied to a sub-network
of size $n$ is given by the following recurrence relationship:
$T_{\mathcal{A}_{2}}(n)=T_{\mathcal{A}_{2}}(\frac{n}{2})+T_{\mathcal{C}_{2}}(n)+T_{\mathcal{A}_{2}}(\frac{n}{2})$
where $T_{\mathcal{C}_{2}}(n)$ is the running time of coordination algorithm
$\mathcal{C}_{2}$. According to Theorem 6, we have that
$T_{\mathcal{C}_{2}}(n)=O(n\log^{3}n)$ and therefore by solving the recurrence
relationship we obtain that $T_{\mathcal{A}_{2}}(n)=O(n\log^{4}n)$. ∎

##  5 Shortest Path Algorithm $\mathcal{A}_{k}$ for $k\geq 3$

For $k\geq 3$ when algorithm $\mathcal{A}_{k}$ is applied to a sub-network
$(\mathcal{N};\mathcal{Y}_{1},\mathcal{Y}_{2},\ldots,\mathcal{Y}_{k-1})[\beta_{1},\beta_{2}]$
or $\mathcal{N}[\beta_{1},\beta_{2}]$ for short, the computation consists of
three phases. The first phase and third phase are the recursive calls of
$\mathcal{A}_{k}$ on $\mathcal{N}_{1}$ and $\mathcal{N}_{2}$, respectively.
The second, coordination phase calls algorithm $\mathcal{C}_{k}$ to the sub-
network $\mathcal{N}[\beta_{1},\beta_{2}]$.

Algorithm $\mathcal{C}_{k}$ repeats for $(k-1)$ times the following three
steps. The first and third step consist of the following $k-1$ calls of
algorithm $\mathcal{A}_{k-1}$:
$\mathcal{A}_{k-1}(\mathcal{N}[\beta_{1},\beta_{2}]\setminus\mathcal{Y}_{1}),\ldots,$
$\mathcal{A}_{k-1}(\mathcal{N}[\beta_{1},\beta_{2}]\setminus\mathcal{Y}_{k-1})$.
Term $\mathcal{N}[\beta_{1},\beta_{2}]\setminus\mathcal{Y}_{i}$ denotes the
sub-network $\mathcal{N}[\beta_{1},\beta_{2}]$ without the red edges of paths
$\mathcal{Y}_{i}$. We group this sequence of calls to algorithm
$\mathcal{A}_{k-1}$ in this order to facilitate analysis and for simplicity we
denote this sequence by $\widehat{\mathcal{A}}_{k-1}$. The second step of
algorithm $\mathcal{C}_{k}$ calls algorithm $\mathcal{Z}_{k}$ which is applied
to the sub-network $\mathcal{N}[\beta_{1},\beta_{2}]$.

Algorithm $\mathcal{Z}_{k}$ has a recursive structure similar to algorithm
$\mathcal{A}_{k}$ except that it works in the opposite direction. In more
detail, the computation of algorithm $\mathcal{Z}_{k}$ consists of three
phases. The first and third phase are recursive calls to $\mathcal{Z}_{k}$ on
$\mathcal{N}_{2}$ and $\mathcal{N}_{1}$, respectively (so the first recursive
call is to the top half of the sub-network). The second, coordination phase
consists of two steps, as explained below.

The first step calls algorithm
$\Delta(\mathcal{Y}_{1},\mathcal{Y}_{2},\ldots,\mathcal{Y}_{k-1})$ which is
the natural generalisation of algorithm $\Delta(\mathcal{Y}_{1})$. That is,
algorithm $\Delta(\mathcal{Y}_{1},\mathcal{Y}_{2},\ldots,\mathcal{Y}_{k-1})$
traverses the red edges (short and long) of each path
$\mathcal{Y}_{1},\mathcal{Y}_{2},\ldots,\mathcal{Y}_{k-1}$ in the sub-network
starting from the last edge and moving towards the first edge. When a red edge
$(u,u^{\prime})$ is considered it performs operation $\mbox{\it
relax}(u,u^{\prime})$. The second step repeats for $(k-2)$ times two calls to
the sequence $\widehat{\mathcal{A}}_{k-1}$. That is, one iteration consists of
$2(k-1)$ calls to algorithm $\mathcal{A}_{k-1}$. Algorithms $\mathcal{A}_{k}$,
$\mathcal{C}_{k}$ and $\mathcal{Z}_{k}$ are described in pseudocode as
Algorithms 3, 4 and 5, respectively.

$\mathcal{N}_{1}\leftarrow\mathcal{N}[\beta_{1},(\beta_{1}+\beta_{2})/2]$
$\mathcal{N}_{2}\leftarrow\mathcal{N}[(\beta_{1}+\beta_{2})/2,\beta_{2}]$

$\mathcal{A}_{k}(\mathcal{N}_{1});$

$\mathcal{C}_{k}(\mathcal{N}[\beta_{1},\beta_{2}]);$

$\mathcal{A}_{k}(\mathcal{N}_{2});$

Algorithm 3 Algorithm $\mathcal{A}_{k}$ for input
$\mathcal{N}[\beta_{1},\beta_{2}]$

Repeat for $i=1,2,\ldots,k-1$

$\mathcal{A}_{k-1}(\mathcal{N}[\beta_{1},\beta_{2}]\setminus\mathcal{Y}_{1});,\ldots,\mathcal{A}_{k-1}(\mathcal{N}[\beta_{1},\beta_{2}]\setminus\mathcal{Y}_{k-1});$

$\mathcal{Z}_{k}(\mathcal{N}[\beta_{1},\beta_{2}]);$

$\mathcal{A}_{k-1}(\mathcal{N}[\beta_{1},\beta_{2}]\setminus\mathcal{Y}_{1});,\ldots,\mathcal{A}_{k-1}(\mathcal{N}[\beta_{1},\beta_{2}]\setminus\mathcal{Y}_{k-1});$

Algorithm 4 Algorithm $\mathcal{C}_{k}$ for input
$\mathcal{N}[\beta_{1},\beta_{2}]$

$\mathcal{N}_{1}\leftarrow\mathcal{N}[\beta_{1},(\beta_{1}+\beta_{2})/2]$
$\mathcal{N}_{2}\leftarrow\mathcal{N}[(\beta_{1}+\beta_{2})/2,\beta_{2}]$

$\mathcal{Z}_{k}(\mathcal{N}_{2});$

$\Delta(\mathcal{Y}_{1},\mathcal{Y}_{2},\ldots,\mathcal{Y}_{k-1});$

for  _$i=1,2,\ldots,(k-2)$_ do

$\mathcal{A}_{k-1}(\mathcal{N}[\beta_{1},\beta_{2}]\setminus\mathcal{Y}_{1});,\ldots,\mathcal{A}_{k-1}(\mathcal{N}[\beta_{1},\beta_{2}]\setminus\mathcal{Y}_{k-1});$

$\mathcal{A}_{k-1}(\mathcal{N}[\beta_{1},\beta_{2}]\setminus\mathcal{Y}_{1});,\ldots,\mathcal{A}_{k-1}(\mathcal{N}[\beta_{1},\beta_{2}]\setminus\mathcal{Y}_{k-1});$

end for

$\mathcal{Z}_{k}(\mathcal{N}_{1});$

Algorithm 5 Algorithm $\mathcal{Z}_{k}$ for input
$\mathcal{N}[\beta_{1},\beta_{2}]$

For a sub-network $\mathcal{N}[\beta_{1},\beta_{2}]$ let $Q$ be a non-self-
crossing path in this sub-network. Without loss of generality, we assume that
$Q$ has points both in $\mathcal{N}_{1}$ and $\mathcal{N}_{2}$. Analogously as
for $k=2$ and according to Definitions 4 and 5, path $Q$ can be decomposed
into three parts $(Q_{x},q_{xx^{\prime}},Q_{x^{\prime}})$ where $Q_{x}$ is the
sub-path of $Q$ from its starting point to point $x$, $q_{xx^{\prime}}$ is the
sub-path of $Q$ from $x$ to $x^{\prime}$ and $Q_{x^{\prime}}$ is the sub-path
of $Q$ from point $x^{\prime}$ to its ending point. Recall that if $Q_{x}$
(resp. $Q_{x^{\prime}}$) is not empty then it must include points only in
$\mathcal{N}_{1}$ (resp. $\mathcal{N}_{2}$).

For $k\geq 3$ the proof of Theorem 2 is outlined below. We assume by induction
that when algorithm $\mathcal{A}_{k}$ is applied to $\mathcal{N}_{1}$ the
computation follows every non-self-crossing path that has only points in
$\mathcal{N}_{1}$. Thus, the computation of the recursive call of algorithm
$\mathcal{A}_{k}$ on $\mathcal{N}_{1}$ follows the sub-path $Q_{x}$ of $Q$.
According to Theorem 4 the computation of algorithm $\mathcal{C}_{k}$ follows
the sub-path $q_{xx^{\prime}}$ of $Q$. Finally, we assume by induction that
when algorithm $\mathcal{A}_{k}$ is applied to $\mathcal{N}_{2}$ the
computation follows every non-self-crossing path that has only points in
$\mathcal{N}_{2}$. Thus, the computation of the second recursive call follows
the sub-path $Q_{x^{\prime}}$ of $Q$.

The remaining part of the section is organized in the following way: In
Subsection 5.1 we specify the structure of paths followed by algorithm
$\mathcal{C}_{k}$. In Subsection 5.2 we specify the structure of paths
followed by algorithm $\mathcal{Z}_{k}$. Finally, based on the analysis of
Subsection 5.2 in Subsection 5.3 we show the proof of Theorems 2 and 4 for
$k\geq 3$.

###  5.1 Algorithm $\mathcal{C}_{k}$

For a sub-network $\mathcal{N}[\beta_{1},\beta_{2}]$ and a non-self-crossing
path $Q$ in the sub-network, algorithm $\mathcal{C}_{k}$ is employed to follow
the sub-path $q_{xx^{\prime}}$ of $Q$ from $x$ to $x^{\prime}$ . In this sub-
section we outline the combinatorial structure of path $q_{xx^{\prime}}$. To
facilitate analysis we first introduce ”shades” of red colour to distinguish
between red edges of different paths
$\mathcal{Y}_{1},\mathcal{Y}_{2},..,\mathcal{Y}_{k-1}$. Specifically, the
edges of path $\mathcal{Y}_{i}$ for $i=1,2,\ldots,k-1$ are coloured with red
colour $c_{i}$.

Recall that according to Definition 6, a run $r$ is a maximal sub-path of a
path $Q$ such that all edges are of the same colour. A run is non-chromatic if
it consists of black edges. A run is chromatic if all of its edges are of the
same red colour $c_{i}$, for some $1\leq i\leq k-1$.

######  Definition 7.

For $0\leq d\leq k-1$ we say that a non-self-crossing path $Q$ (or a sub-path
of $Q$) is $d$-chromatic, if the number of red colours in all chromatic runs
is equal to $d$. A path $Q$ (or a sub-path of $Q$) that does not have a
chromatic run, is $0$-chromatic, or non-chromatic, and traverses only black
edges.

######  Definition 8.

We say that a $(k-1)$-chromatic path $Q$ is short $(k-1)$-chromatic if all
chromatic runs of colour $c_{1}$ appear before all chromatic runs of colour
$c_{k-1}$ or vice versa.

Recall that for a sub-network $\mathcal{N}[\beta_{1},\beta_{2}]$ we denote by
$\widehat{\mathcal{A}}_{k-1}$ the algorithm which performs the following
sequence of $(k-1)$ calls
$\mathcal{A}_{k-1}(\mathcal{N}[\beta_{1},\beta_{2}]\setminus\mathcal{Y}_{1}),\ldots,\mathcal{A}_{k-1}(\mathcal{N}[\beta_{1},\beta_{2}]\setminus\mathcal{Y}_{k-1})$
to algorithm $\mathcal{A}_{k-1}$. The following describes the specification of
$\widehat{\mathcal{A}}_{k-1}$ when applied to a sub-network.

######  Lemma 3.

For $k\geq 3$, assuming that Theorem 2 holds for $k-1$, when algorithm
$\widehat{\mathcal{A}}_{k-1}$ is applied to a sub-network
$\mathcal{N}[\beta_{1},\beta_{2}]$ then the computation follows any non-self-
crossing path $Q$ in the sub-network such that $Q$ is at most
$(k-2)$-chromatic.

###### Proof.

Sub-networks
$\mathcal{N}[\beta_{1},\beta_{2}]\setminus\mathcal{Y}_{1},\ldots,\mathcal{N}[\beta_{1},\beta_{2}]\setminus\mathcal{Y}_{k-1}$
do not have a negative cycle because there are sub-networks of the residual
network $\mathcal{N}_{k-1}$ (i.e. the sub-network for $\beta_{1}=0$ and
$\beta_{2}=n+1$) which does not have a negative cycle. Consider a non-self-
crossing path $Q$ such that $Q$ is at most $(k-2)$-chromatic. This means that
$Q$ can traverse red edges of all paths except one path $\mathcal{Y}_{i}$
where $i\in[1,k-1]$.

Thus, path $Q$ must be a non-self-crossing path in one of the sub-networks
$\mathcal{N}[\beta_{1},\beta_{2}]\setminus\mathcal{Y}_{1},\ldots,\mathcal{N}[\beta_{1},\beta_{2}]\setminus\mathcal{Y}_{k-1}$.
Without loss of generality, we assume that $Q$ is a path on sub-network
$\mathcal{N}[\beta_{1},\beta_{2}]\setminus\mathcal{Y}_{i}$ where
$i\in[1,k-1]$. Algorithm $\widehat{\mathcal{A}}_{k-1}$ consists of applying
algorithm $\mathcal{A}_{k-1}$ on sub-networks
$\mathcal{N}[\beta_{1},\beta_{2}]\setminus\mathcal{Y}_{1},\ldots,\mathcal{N}[\beta_{1},\beta_{2}]\setminus\mathcal{Y}_{k-1}$.
Thus, assuming that Theorem 2 holds for $k-1$, when algorithm
$\mathcal{A}_{k-1}$ is applied to sub-network
$\mathcal{N}[\beta_{1},\beta_{2}]\setminus\mathcal{Y}_{i}$ the computation
follows every non-self-crossing path in the sub-network. This completes the
proof. ∎

When algorithm $\widehat{\mathcal{A}}_{k-1}$ is applied twice on a sub-network
$\mathcal{N}[\beta_{1},\beta_{2}]$ (denoted by $\widehat{\mathcal{A}}_{k-1}$
$\widehat{\mathcal{A}}_{k-1}$) the computation consists of the following calls
to algorithm $\mathcal{A}_{k-1}$:
$\mathcal{A}_{k-1}(\mathcal{N}[\beta_{1},\beta_{2}]\setminus\mathcal{Y}_{1}),\ldots,\mathcal{A}_{k-1}(\mathcal{N}[\beta_{1},\beta_{2}]\setminus\mathcal{Y}_{k-1})$
and
$\mathcal{A}_{k-1}(\mathcal{N}[\beta_{1},\beta_{2}]\setminus\mathcal{Y}_{1}),\ldots,\mathcal{A}_{k-1}(\mathcal{N}[\beta_{1},\beta_{2}]\setminus\mathcal{Y}_{k-1})$
in this order.

######  Lemma 4.

For $k\geq 3$, assuming that Theorem 2 holds for $k-1$, when algorithm
$\widehat{\mathcal{A}}_{k-1}$ is applied twice to a sub-network
$\mathcal{N}[\beta_{1},\beta_{2}]$ then the computation follows any non-self-
crossing path $Q$ in the sub-network such that $Q$ which is short
$(k-1)$-chromatic.

###### Proof.

Consider a non-self-crossing path $Q$ from a point $u$ to a point $u^{\prime}$
such that $Q$ is short $(k-1)$-chromatic. Without loss of generality, we
assume that all chromatic runs of colour $c_{1}$ appear before all chromatic
runs of colour $c_{k-1}$ in $Q$. Let $u^{\prime\prime}$ be the first point of
the first chromatic run of colour $c_{k-1}$ in $Q$. The sub-path of $Q$ from
$u$ to $u^{\prime\prime}$ and the sub-path of $Q$ from $u^{\prime\prime}$ to
$u^{\prime}$ can be at most $(k-2)$-chromatic.

That is, there is no chromatic run of colour $c_{k-1}$ (resp. $c_{1}$) between
$u$ and $u^{\prime\prime}$ (resp. between $u^{\prime\prime}$ and
$u^{\prime}$). According to Lemma 3 when algorithm
$\widehat{\mathcal{A}}_{k-1}$ is applied on sub-network
$\mathcal{N}[\beta_{1},\beta_{2}]$ the computation follows every non-self-
crossing path which is at most $(k-2)$-chromatic. Thus, the first call to
$\widehat{\mathcal{A}}_{k-1}$ follows the sub-path of $Q$ from $u$ to
$u^{\prime\prime}$. Similarly, the second call to algorithm
$\widehat{\mathcal{A}}_{k-1}$ follows the sub-path of $Q$ from
$u^{\prime\prime}$ to $u^{\prime}$. ∎

Note that algorithm $\mathcal{C}_{k}$ includes at least two calls to algorithm
$\widehat{\mathcal{A}}_{k-1}$ (see steps 1 and 3 in Algorithm 4). This means
that if the sub-path $q_{xx^{\prime}}$ is at most $(k-2)$-chromatic or short
$(k-1)$-chromatic then according to Lemmas 3 and 4, the computation of
algorithm $\mathcal{C}_{k}$ follows the sub-path $q_{xx^{\prime}}$. Thus, for
the remaining part of the analysis we consider the case where
$q_{xx^{\prime}}$ is $(k-1)$-chromatic.

We need the following definitions to outline the combinatorial structure of a
$(k-1)$-chromatic non-self-crossing path in a sub-network
$\mathcal{N}[\beta_{1},\beta_{2}]$, with respect to the two sub-networks
$\mathcal{N}_{1}$ and $\mathcal{N}_{2}$.

######  Definition 9.

We say that a non-chromatic run crosses from $\mathcal{N}_{1}$ to
$\mathcal{N}_{2}$ if it traverses a black edge $(u,u^{\prime})$ such that
$u\in\mathcal{N}_{1}$ and $u^{\prime}\in\mathcal{N}_{2}$. We say that a
chromatic run $r$ of colour $c_{j}$ where $j\in[1,k-1]$ crosses from
$\mathcal{N}_{2}$ to $\mathcal{N}_{1}$ if it traverses a red edge
$(u,u^{\prime})\in\mathcal{Y}_{j}$ such that $u\in\mathcal{N}_{2}$ and
$u^{\prime}\in\mathcal{N}_{1}$.

If a run $r$ has only points in $\mathcal{N}_{1}$ (resp. $\mathcal{N}_{2}$) we
say that $r$ is placed in $\mathcal{N}_{1}$ (resp. $\mathcal{N}_{2}$).

######  Definition 10.

We say that a path $Q$ crosses from $\mathcal{N}_{2}$ to $\mathcal{N}_{1}$ if
$Q$ has a chromatic run $r$ which crosses from $\mathcal{N}_{2}$ to
$\mathcal{N}_{1}$. We say that a path $Q$ crosses from $\mathcal{N}_{1}$ to
$\mathcal{N}_{2}$ if $Q$ has a non-chromatic run that crosses from
$\mathcal{N}_{1}$ to $\mathcal{N}_{2}$.

Similarly as for $k=2$, if the sub-path $q_{xx^{\prime}}$ is not empty and
does not cross from $\mathcal{N}_{2}$ to $\mathcal{N}_{1}$ it must hold that
$x\in\mathcal{N}_{1}$, $x^{\prime}\in\mathcal{N}_{2}$ and the sub-path
$q_{xx^{\prime}}$ simply consists of the black edge $(x,x^{\prime})$. If the
sub-path $q_{xx^{\prime}}$ crosses at least once from $\mathcal{N}_{2}$ to
$\mathcal{N}_{1}$, observe that for $k\geq 3$ there are exactly $(k-1)$ red
edges which cross from $\mathcal{N}_{2}$ to $\mathcal{N}_{1}$ (one for each
path $\mathcal{Y}_{1},\mathcal{Y}_{2},...,\mathcal{Y}_{k-1}$).

Therefore, the sub-path $q_{xx^{\prime}}$ can cross at most $m\leq k-1$ times
from $\mathcal{N}_{2}$ to $\mathcal{N}_{1}$ (as each such crossing must
traverse one of the $k-1$ red edges from $\mathcal{N}_{2}$ to
$\mathcal{N}_{1}$). It is easy to see that every red edge of $q_{xx^{\prime}}$
crossing from $\mathcal{N}_{2}$ to $\mathcal{N}_{1}$ must appear after a black
edge crossing from $\mathcal{N}_{1}$ to $\mathcal{N}_{2}$.

######  Definition 11.

We define $w_{i}$ for $i=1,2,\ldots,m$ to be the last point in
$\mathcal{N}_{1}$ before the $i^{th}$ crossing of $q_{xx^{\prime}}$ from
$\mathcal{N}_{1}$ to $\mathcal{N}_{2}$. We denote by $q_{i}$ the sub-path of
$q_{xx^{\prime}}$ from $w_{i}$ to $w_{i+1}$.

For clarity, we denote $x$ and $x^{\prime}$ by $w_{1}$ and $w_{k}$,
respectively, and w.l.o.g, we assume that $m=k-1$. For $i=1$ and the special
case where $w_{1}$ is on $\mathcal{N}_{2}$ then $p_{1}$ does not cross from
$\mathcal{N}_{1}$ to $\mathcal{N}_{2}$. Similarly, for $i=k-1$ and the special
case where $w_{k}$ is on $\mathcal{N}_{2}$ then $p_{k-1}$ does not cross from
$\mathcal{N}_{2}$ to $\mathcal{N}_{1}$. Denote by
$w^{\prime}_{i}\in\mathcal{N}_{2}$ the successor of $w_{i}$ in $q_{i}$ for
$i=1,2,\ldots,k-1$. The following corollary outlines the structure of $q_{i}$
for $i=1,2,\ldots,k-1$.

######  Corollary 3.

For $i=1,2,\ldots,k-1$ the sub-path $q_{i}$ of $q_{xx^{\prime}}$ from $w_{i}$
to $w_{i+1}$ crosses the boundary between $\mathcal{N}_{1}$ and
$\mathcal{N}_{2}$ twice. The first crossing is from $\mathcal{N}_{1}$ to
$\mathcal{N}_{2}$ identified with the black edge $(w_{i},w^{\prime}_{i})$. The
second crossing is from $\mathcal{N}_{2}$ to $\mathcal{N}_{1}$ identified with
a red chromatic run $r^{*}$ of colour $c_{j}$ where $j\in[1,k-1]$.

For $i=1,2,\ldots,k-1$ the sub-path $q_{i}$ of $q_{xx^{\prime}}$ can be either
at most $(k-2)$-chromatic or $(k-1)$-chromatic. In the former case, according
to Lemma 3 the computation of the first step in the $i^{th}$ iteration of
algorithm $\mathcal{C}_{k}$, follows the sub-path $q_{i}$ of
$q_{xx^{\prime}}$. For the latter case, we provide the following definition to
facilitate analysis.

######  Definition 12.

For a sub-network $\mathcal{N}[\beta_{1},\beta_{2}]$ consider a
$(k-1)$-chromatic path $Q$ from a point $u$ to a point $u^{\prime}$. Let
$\pi,\tau$ be the points in $Q$ such that the sub-path of $Q$ from $u$ to
$\pi$ (resp. from $\tau$ to $u^{\prime}$) is a maximal $(k-2)$-chromatic path.

Points $\pi$ and $\tau$ are always unique and well-defined for any
$(k-1)$-chromatic path $Q$. Following Definition 12, let $\pi_{i}$ and
$\tau_{i}$ for $i=1,2,\ldots,k-1$ be the points in the sub-path $q_{i}$ of
$q_{xx^{\prime}}$ from $w_{i}$ to $w_{i+1}$. Consider the decomposition of
sub-path $q_{xx^{\prime}}$ into the following parts
$(w_{1},\pi_{1},\tau_{1},w_{2}),\ldots,(w_{k-1},\pi_{k-1},\tau_{k-1},w_{k})$,
as shown in Figure 8.

Note that for $i=1,2,\ldots,k-1$ if the path from $\pi_{i}$ to $\tau_{i}$ is
empty (i.e. $\tau_{i}$ appears before $\pi_{i}$ in $q_{i}$) then according to
Definition 12 the path from $\pi_{i}$ to $w_{i+1}$ is also $(k-2)$-chromatic.
In this case, based on Lemma 3 we will show that the computation of the first
and third step in the $i^{th}$ iteration of algorithm $\mathcal{C}_{k}$,
follows the sub-path $q_{i}$ of $q_{xx^{\prime}}$. From now on we consider the
case where the path from $\pi_{i}$ to $\tau_{i}$ is not empty (i.e. $\tau_{i}$
appears after $\pi_{i}$ in $q_{i}$).

Figure 8: The combinatorial structure of the sub-path $q_{xx^{\prime}}$ from
$x$ to $x^{\prime}$ of a non-self-crossing path $Q$, for $k\geq 3$. For
clarity, we assume that $m=k-1$.

######  Definition 13.

Consider the plane representation of the residual network $\mathcal{N}_{k-1}$.
We denote by $\Phi$ the closed subset of the plane whose boundary is described
by the leftmost and rightmost path $\mathcal{Y}_{1}$ and $\mathcal{Y}_{k-1}$,
respectively.

The exterior of $\Phi$ contains only black points. A black point $u$ in the
exterior of $\Phi$ must be either on the left side of path $\mathcal{Y}_{1}$
or on the right side of path $\mathcal{Y}_{k-1}$. For the former case we say
that $u$ is on the left exterior of $\Phi$, whereas in the latter case we say
that $u$ is on the right exterior of $\Phi$. We say that a red point $u$ is a
left (resp. right) boundary point of $\Phi$ if $u$ is a red point on path
$\mathcal{Y}_{1}$ (resp. $\mathcal{Y}_{k-1}$). We say that a red or black
point is in the interior of $\Phi$ if $u$ is a black point between two
consecutive paths $\mathcal{Y}_{j}$ and $\mathcal{Y}_{j+1}$ where
$j\in[1,k-2]$ or a red point on path $\mathcal{Y}_{j}$ where $j\in[2,k-2]$. A
boundary point or a point in the interior of $\Phi$ is said to be in $\Phi$.

An edge $(u,u^{\prime})$ is in $\Phi$ if the closed straight line segment
$[u,u^{\prime}]$, corresponding to edge $(u,u^{\prime})$) in the planar
representation, is in $\Phi$. Observe that all red edges of the paths
$\mathcal{Y}_{1},\mathcal{Y}_{2},\ldots,\mathcal{Y}_{k-1}$ must be in $\Phi$.
Thus, we have the following corollary.

######  Corollary 4.

For a sub-network $\mathcal{N}[\beta_{1},\beta_{2}]$ and a non-self-crossing
path $Q$ in this sub-network, all chromatic runs of $Q$ are in $\Phi$.

If a black edge is not in $\Phi$, denoted by $(u,u^{\prime})\notin\Phi$, then
the closed segment $[u,u^{\prime}]$ in the planar representation, must have a
closed (sub)-segment in the exterior of $\Phi$. A non-chromatic run $r$ is not
in $\Phi$ if it has at least one black edge $(u,u^{\prime})$ such that
$(u,u^{\prime})\notin\Phi$.

A black edge $(u,u^{\prime})\notin\Phi$ is a boundary edge if point $u$ is a
right or left boundary point. A black edge $(u,u^{\prime})\notin\Phi$ is a
crossing edge if point $u$ is in the interior of $\Phi$. Recall that paths
$\mathcal{Y}_{1},\mathcal{Y}_{2},\ldots,\mathcal{Y}_{k-1}$ are non crossing
pairwise and therefore a crossing edge $(u,u^{\prime})\notin\Phi$ must
necessarily cross at least one red edge of path $\mathcal{Y}_{1}$ or path
$\mathcal{Y}_{k-1}$.

For a sub-network $\mathcal{N}[\beta_{1},\beta_{2}]$ and a non-self-crossing
path $Q$ in the sub-network, consider the geometric representation of $Q$ with
the set of points on the plane. Path $Q$ can be seen as a concatenation of
straight line segments which represent the edges of $Q$ and form a continuous
segment $\phi$ in the planar representation.

To facilitate analysis, we distinguish between points and space points. A
point $u$ in $\phi$ corresponds to node $u$ in the directed acyclic graph
model (on which the sub-network $\mathcal{N}[\beta_{1},\beta_{2}]$ is based
on). A space point $l$ in $\phi$ is a geometrical point on the closed segment
$[u,u^{\prime}]$ of an edge $(u,u^{\prime})\in Q$ and does not correspond to a
node in the directed acyclic graph model.

######  Definition 14.

A sub-path $q$ of a non-self-crossing path $Q$ is a covering-path if the
continuous segment $\phi$ corresponding to $q$ connects two space points (or
points) on the right and left boundary of $\Phi$, respectively.

Notice that the continuous segment $\phi$ of a covering path $q$ forms a
boundary which splits $\Phi$ into two subsets, the bottom subset and the top
subset. Recall that for $i=1,2,\ldots,k-1$ we denote by $q_{i}$ the path from
$w_{i}$ to $w_{i+1}$. Further according to Definition 12, for
$i=1,2,\ldots,k-1$ path $q_{i}$ is decomposed into the following parts
$(w_{i},\pi_{i})(\pi_{i},\tau_{i}),(\tau_{i},w_{i+1})$ (see Figure 8).

######  Lemma 5.

For $i=1,2,\ldots,k-1$, all runs (chromatic and non-chromatic) in the sub-path
of $q_{i}$ from $\pi_{i}$ and $\tau_{i}$ are in $\Phi$.

###### Proof.

According to Corollary 4, all chromatic runs in the sub-path of $q_{i}$ from
$\pi_{i}$ and $\tau_{i}$ must be in $\Phi$. Thus, it remains to show that all
non-chromatic runs are also in $\Phi$. Assume towards contradiction that for
some $i\in[1,k-1]$ there is a non-chromatic run $r_{b}$ between $\pi_{i}$ and
$\tau_{i}$ such that $r_{b}$ is not in $\Phi$. This means that $r_{b}$ must
include at least one black edge which is not in $\Phi$.

We denote by $(u,u^{\prime})$ the first black edge in $r_{b}$ such that
$(u,u^{\prime})\notin\Phi$. Recall that a black edge which is not in $\Phi$
must be either a crossing edge or a boundary edge. Let $l$ be the space point
which is defined in the following way. If edge $(u,u^{\prime})$ is a boundary
edge then $l$ is defined as point $u$. If edge $(u,u^{\prime})$ is a crossing
edge then $l$ is defined as the first crossing point on the closed segment
$[u,u^{\prime}]$ with a red edge of path $\mathcal{Y}_{1}$ or path
$\mathcal{Y}_{k-1}$.

Without loss of generality, we assume that edge $(u,u^{\prime})$ is a crossing
edge and that space point $l$ is on path $\mathcal{Y}_{1}$. According to
Corollary 3 there is exactly one chromatic run $r^{*}$ in $q_{i}$ which
crosses from $\mathcal{N}_{2}$ to $\mathcal{N}_{1}$. There are two possible
cases: (1) edge $(u,u^{\prime})$ appears before $r^{*}$ and (2) edge
$(u,u^{\prime})$ appears after $r^{*}$.

##### Case 1

(see Figure 9(a))
According to Definition 12, the path from $w_{i}$ to $\pi_{i}$ is a maximal
$(k-2)$-chromatic path. If $\pi_{i}$ is a red point on path $\mathcal{Y}_{j}$
where $j\in[1,k-2]$ then the path from $w_{i}$ to $\pi_{i}$ has at least one
chromatic run of colour $c_{k-1}$. If $\pi_{i}$ is a red point on path
$\mathcal{Y}_{k-1}$ then clearly the path from $w_{i}$ to $\pi_{i}$ has at
least one chromatic run of colour $c_{k-1}$. Because $\pi_{i}$ appears before
edge $(u,u^{\prime})$ we conclude that there is at least one chromatic run of
colour $c_{k-1}$ before edge $(u,u^{\prime})$. Let $r$ be the last chromatic
run of colour $c_{k-1}$ before the black edge $(u,u^{\prime})$.

Let $p$ be the path from the last point of run $r$ to point $u^{\prime}$.
According to Definition 14 $p$ must be a covering path since there is a
continuous segment $\phi$ which connects a right boundary point (the first
point of run $r$ on $\mathcal{Y}_{k-1}$) and a left boundary point (the
crossing point $l$ on path $\mathcal{Y}_{1}$). Notice that all runs in $p$
appear before $r^{*}$ and therefore $p$ has only points in $\mathcal{N}_{2}$.
This means that the continuous segment $\phi$ is above the boundary separating
$\mathcal{N}_{1}$ and $\mathcal{N}_{2}$.

Let $\Phi\cap\mathcal{N}_{2}$ be the subset of $\Phi$ above the boundary
separating $\mathcal{N}_{1}$ and $\mathcal{N}_{2}$. Consider the subset
$\widetilde{\Phi}$ of $\Phi\cap\mathcal{N}_{2}$ which is described with the
following two boundaries. The top boundary is the continuous segment $\phi$.
The bottom boundary is the boundary separating $\mathcal{N}_{1}$ and
$\mathcal{N}_{2}$. In Figure 9(a), the subset $\widetilde{\Phi}$ of
$\Phi\cap\mathcal{N}_{2}$ is shown with the shaded area.

The last point of run $r^{*}$ must be in $\mathcal{N}_{1}$ since $r^{*}$
crosses from $\mathcal{N}_{2}$ to $\mathcal{N}_{1}$. Since $\widetilde{\Phi}$
is a subset of $\Phi\cap\mathcal{N}_{2}$, the last point of run $r^{*}$ must
be in the exterior of $\widetilde{\Phi}$. This means that the first point of
$r^{*}$ must be between the top and bottom boundary of $\widetilde{\Phi}$
since otherwise run $r^{*}$ crosses with the continuous segment $\phi$ which
implies a self-crossing. Thus, the first point of run $r^{*}$ must be in
$\widetilde{\Phi}$.

Let $p^{\prime}$ be the path from point $u$ to the first point of run $r^{*}$
and let $\phi^{\prime}$ be the continuous segment (corresponding to
$p^{\prime}$) from the space point $l$ to the first point of run $r^{*}$. All
runs in $p^{\prime}$ appear before $r^{*}$ which means that $p^{\prime}$ has
only points in $\mathcal{N}_{2}$. Thus, the continuous segment $\phi^{\prime}$
is above the boundary separating $\mathcal{N}_{1}$ and $\mathcal{N}_{2}$.
Since edge $(u,u^{\prime})\notin\Phi$, the continuous segment $\phi^{\prime}$
must have a closed segment $[l,l^{\prime}]$ in the exterior of
$\Phi\cap\mathcal{N}_{2}$ and subsequently in the exterior of
$\widetilde{\Phi}$.

If the closed segment $[l,u^{\prime}]$ does not cross any red edges, then
space point $l^{\prime}$ is defined as point $u^{\prime}$. If the closed
segment $[l,u^{\prime}]$ crosses with at least one red edge, then the first
crossing point on the closed segment $[l,u^{\prime}]$ must be with a red edge
of $\mathcal{Y}_{1}$, since there are no red edges in the exterior of $\Phi$
and subsequently in the exterior of $\widetilde{\Phi}$. In this case, space
point $l^{\prime}$ is defined as the first crossing point on the closed
segment $[l,u^{\prime}]$.

The continuous segment from any arbitrary space point on the closed segment
$[l,l^{\prime}]$ which is on the exterior of $\widetilde{\Phi}$ to the first
point of run $r^{*}$ which is in $\widetilde{\Phi}$ must cross the top
boundary of $\widetilde{\Phi}$. This implies, that path $p$ crosses with path
$p^{\prime}$, which makes a contradiction.

##### Case 2

(see Figure 9(b))
Consider the path $p$ from the last point of run $r^{*}$ to point $u^{\prime}$
and let $\phi$ be the continuous segment (corresponding to path $p$) from the
last point of run $r^{*}$ to the space point $l$ on edge $(u,u^{\prime})$. All
runs in $p$ appear after $r^{*}$, which means that $p$ has only points in
$\mathcal{N}_{1}$ and subsequently the continuous segment $\phi$ must be below
the boundary separating $\mathcal{N}_{1}$ and $\mathcal{N}_{2}$.

Let $\Phi\cap\mathcal{N}_{1}$ be the subset of $\Phi$ below the boundary
separating $\mathcal{N}_{1}$ and $\mathcal{N}_{2}$. Consider the subset
$\widetilde{\Phi}$ of $\Phi\cap\mathcal{N}_{1}$ which is described with the
following top and bottom boundary. The bottom boundary of $\widetilde{\Phi}$
is described with the continuous segment $\phi$. The top boundary of
$\widetilde{\Phi}$ is described with the boundary separating $\mathcal{N}_{1}$
and $\mathcal{N}_{2}$. In Figure 9(b), the subset $\widetilde{\Phi}$ of
$\Phi\cap\mathcal{N}_{1}$ is shown with the shaded area.

Let $p^{\prime}$ be the path from $u^{\prime}$ to point $w_{i+1}$. All runs in
$p^{\prime}$ appear after $r^{*}$ and therefore $p^{\prime}$ has only points
in $\mathcal{N}_{1}$. Path $p^{\prime}$ is non-self-crossing and therefore all
chromatic runs in $p^{\prime}$ must be in $\widetilde{\Phi}$. The only red
edges of path $\mathcal{Y}_{k-1}$ in $\widetilde{\Phi}$ (if any) are the red
edges traversed by path $p$. Therefore any red edges of path
$\mathcal{Y}_{k-1}$ in $\widetilde{\Phi}$ can not be traversed by $p^{\prime}$
which means that $p^{\prime}$ can be at most $(k-2)$-chromatic.

Points $u$ and $u^{\prime}$ are connected with a black edge. Hence, the path
form $u$ to $w_{i+1}$ can also be at most $(k-2)$-chromatic. According to
Definition 12 the path from $\tau_{i}$ to $w_{i+1}$ is a maximal
$(k-2)$-chromatic path. Therefore, point $\tau_{i}$ can not appear after point
$u$ in the path from $\pi_{i}$ to $w_{i+1}$ (i.e. either $\tau_{i}=u$ or
$\tau_{i}$ precedes $u$). All non-chromatic runs in the path from $\pi_{i}$ to
$u$ must be in $\Phi$ since edge $(u,u^{\prime})$ is the first black edge such
that $(u,u^{\prime})\notin\Phi$. Therefore, all non-chromatic runs between
$\pi_{i}$ and $\tau_{i}$ must also be in $\Phi$ since $\tau_{i}$ does not
appear after $u$. ∎

(a)

(b)

Figure 9: Figure 9(a): The schematic representation of Case 1 for the proof of
Lemma 5. Figure 9(b): The schematic representation of Case 2 for the proof of
Lemma 5.

For a sub-network $\mathcal{N}[\beta_{1},\beta_{2}]$ let $Q$ be a non-self-
crossing path in this sub-network. Consider the sub-path $q_{xx^{\prime}}$ of
$Q$ from $x$ to $x^{\prime}$ and more specifically its decomposition as shown
in Figure 8 (for clarity we denote $x$ and $x^{\prime}$ by $w_{1}$ and
$w_{k}$, respectively, and assume that $m=k-1$). For $i=1,2,\ldots,k-1$ recall
that $q_{i}$ denotes the sub-path of $q_{xx^{\prime}}$ from $w_{i}$ to
$w_{i+1}$. Without loss of generality, we assume that path $q_{i}$ for
$i=1,2,\ldots,k-1$ is $(k-1)$-chromatic. Let $\mathcal{C}^{i}_{k}$ for
$i=1,2,\ldots,k-1$ denote the $i^{th}$ iteration of algorithm
$\mathcal{C}_{k}$. The proof of Theorem 4 is outlined below.

For $i=1,2,\ldots,k-1$ the first step of $\mathcal{C}^{i}_{k}$ calls algorithm
$\widehat{\mathcal{A}}_{k-1}$ on sub-network
$\mathcal{N}[\beta_{1},\beta_{2}]$. According to Lemma 3 when algorithm
$\widehat{\mathcal{A}}_{k-1}$ is applied on a sub-network the computation
follows every non-self-crossing path $Q$ such that $Q$ is at most
$(k-2)$-chromatic. According to Definition 12, the sub-path of $q_{i}$ from
$w_{i}$ to $\pi_{i}$ is at most $(k-2)$-chromatic. Thus the computation of the
first step follows the sub-path of $q_{i}$ from $w_{i}$ to $\pi_{i}$.

The second step of algorithm $\mathcal{C}^{i}_{k}$ calls algorithm
$\mathcal{Z}_{k}$ on sub-network $\mathcal{N}[\beta_{1},\beta_{2}]$. As we
will show in the next sub-section when algorithm $\mathcal{Z}_{k}$ is applied
on a sub-network the computation follows any non-self-crossing path $Q$ such
that all runs (chromatic and non-chromatic) in $Q$ are in $\Phi$. According to
Lemma 5, all runs in the sub-path of $q_{i}$ from $\pi_{i}$ to $\tau_{i}$ are
in $\Phi$. Thus, the computation of algorithm $\mathcal{Z}_{k}$ follows the
sub-path of $q_{i}$ from $\pi_{i}$ to $\tau_{i}$.

The third step of $\mathcal{C}^{i}_{k}$ calls algorithm
$\widehat{\mathcal{A}}_{k-1}$ on sub-network
$\mathcal{N}[\beta_{1},\beta_{2}]$. Similarly as for the first step, according
to Lemma 3 when algorithm $\widehat{\mathcal{A}}_{k-1}$ is applied on a sub-
network the computation follows every non-self-crossing path $Q$ such that $Q$
is at most $(k-2)$-chromatic. According to Definition 12, the sub-path of
$q_{i}$ from $\tau_{i}$ to $w_{i+1}$ is at most $(k-2)$-chromatic. Thus, the
computation of the third step of follows the sub-path of $q_{i}$ from
$\tau_{i}$ to $w_{i+1}$.

###  5.2 Algorithm $\mathcal{Z}_{k}$

In this section we outline the combinatorial structure of paths followed by
algorithm $\mathcal{Z}_{k}$.

######  Definition 15.

For a sub-network $\mathcal{N}[\beta_{1},\beta_{2}]$ and a non-self-crossing
path $Q$ in this sub-network we say that $Q$ is a $\Phi$-path if all runs
(chromatic and non-chromatic) of $Q$ are in $\Phi$.

Recall that when algorithm $\mathcal{Z}_{k}$ is applied to a sub-network
$\mathcal{N}[\beta_{1},\beta_{2}]$ the computation consists of three phases
(see algorithm 5). The first and third phase call algorithm $\mathcal{Z}_{k}$
recursively on $\mathcal{N}_{2}$ and $\mathcal{N}_{1}$, respectively. The
second phase, coordinates $\mathcal{N}_{1}$ and $\mathcal{N}_{2}$ and consists
of two steps. The first step calls algorithm
$\Delta(\mathcal{Y}_{1},\mathcal{Y}_{2},\ldots,\mathcal{Y}_{k-1})$. The second
step consists of $(k-2)$ iterations where each iteration performs two calls of
algorithm $\widehat{\mathcal{A}}_{k-1}$ to the sub-network
$\mathcal{N}[\beta_{1},\beta_{2}]$. Theorem 7 describes the specification of
algorithm $\mathcal{Z}_{k}$.

######  Theorem 7.

Assuming that Theorem 2 holds for $k-1$, when algorithm $\mathcal{Z}_{k}$ is
applied to a sub-network $\mathcal{N}[\beta_{1},\beta_{2}]$ the computation
follows every $\Phi$-path in this sub-network.

For a sub-network $\mathcal{N}[\beta_{1},\beta_{2}]$, let $Q$ be a $\Phi$-path
in the sub-network from a point $\pi$ to a point $\tau$. Consider the two sub-
networks $\mathcal{N}[\beta_{1},(\beta_{1}+\beta_{2})/2]$ and
$\mathcal{N}[(\beta_{1}+\beta_{2})/2,\beta_{2}]$, denoted by $\mathcal{N}_{1}$
and $\mathcal{N}_{2}$, respectively. Without loss of generality we assume that
$Q$ is $(k-1)$-chromatic and that is has points both in $\mathcal{N}_{1}$ and
$\mathcal{N}_{2}$. There are only two possible cases: Path $Q$ does not cross
from $\mathcal{N}_{2}$ to $\mathcal{N}_{1}$ or path $Q$ crosses at least once
from $\mathcal{N}_{2}$ to $\mathcal{N}_{1}$.

######  Lemma 6.

For a sub-network $\mathcal{N}[\beta_{1},\beta_{2}]$ and a $(k-1)$-chromatic
$\Phi$-path $Q$ in the sub-network, if path $Q$ has points both in
$\mathcal{N}_{1}$ and $\mathcal{N}_{2}$ but does not cross from
$\mathcal{N}_{2}$ to $\mathcal{N}_{1}$ then the starting point of $Q$ is in
$\mathcal{N}_{1}$ and the ending point of $Q$ is in $\mathcal{N}_{2}$.

###### Proof.

Let $\pi$ and $\tau$ be the starting and ending point of path $Q$. We claim
that if $Q$ has points both in $\mathcal{N}_{1}$ and $\mathcal{N}_{2}$ but
does not cross from $\mathcal{N}_{2}$ to $\mathcal{N}_{1}$ then $\pi$ must be
on $\mathcal{N}_{1}$ and $\tau$ must be on $\mathcal{N}_{2}$. Assume towards
contradiction that our claim is not true. If point $\pi$ is on
$\mathcal{N}_{2}$ and point $\tau$ is on $\mathcal{N}_{1}$ then $Q$
necessarily crosses from $\mathcal{N}_{2}$ to $\mathcal{N}_{1}$, which makes a
contradiction. Similarly, if both $\pi$ and $\tau$ are on $\mathcal{N}_{2}$
(resp. $\mathcal{N}_{1}$) and $Q$ has points both in $\mathcal{N}_{1}$ and
$\mathcal{N}_{2}$, then there is at least one point $x$ in $\mathcal{N}_{1}$
(resp. $\mathcal{N}_{2}$) between $\pi$ and $\tau$, which means that $Q$
crosses from $\mathcal{N}_{2}$ to $\mathcal{N}_{1}$. Again, this makes a
contradiction. We conclude that the start point $\pi$ of $Q$ must be in
$\mathcal{N}_{1}$ and the ending point $\tau$ of $Q$ must be in
$\mathcal{N}_{2}$. ∎

Recall that a $(k-1)$-chromatic path $Q$ is short $(k-1)$-chromatic if all
chromatic runs of colour $c_{1}$ appear before all chromatic runs of colour
$c_{k-1}$, or vice versa.

######  Lemma 7.

For a sub-network $\mathcal{N}[\beta_{1},\beta_{2}]$ and a $(k-1)$-chromatic
$\Phi$-path $Q$ in the sub-network, if path $Q$ has points both in
$\mathcal{N}_{1}$ and $\mathcal{N}_{2}$ but does not cross from
$\mathcal{N}_{2}$ to $\mathcal{N}_{1}$ then $Q$ is short $(k-1)$-chromatic.

###### Proof.

According to Lemma 6 the starting point $\pi$ of $Q$ must be in
$\mathcal{N}_{1}$ and the ending point $\tau$ of $Q$ must be in
$\mathcal{N}_{2}$. This implies that $Q$ has exactly one black edge
$(u,u^{\prime})$ which crosses from $\mathcal{N}_{1}$ to $\mathcal{N}_{2}$.
Let $l$ be the space point corresponding to the crossing point of edge
$(u,u^{\prime})$ with the boundary separating $\mathcal{N}_{1}$ and
$\mathcal{N}_{2}$ (shown with green in Figures 10(a) and 10(b)).

Since $Q$ is $(k-1)$-chromatic it must have at least one chromatic run of
colour $c_{1}$ and at least one chromatic run of colour $c_{k-1}$. Without
loss of generality, we assume that the first run of colour $c_{k-1}$ appears
before the first chromatic run $r^{\prime}$ of colour $c_{1}$. It is
sufficient to show that there is no chromatic run of colour $c_{k-1}$ after
$r^{\prime}$ in $Q$.

Among all chromatic runs of colour $c_{k-1}$ before $r^{\prime}$ let $r$ be
the last chromatic run of colour $c_{k-1}$. We first claim that run $r$ must
have all of its points in $\mathcal{N}_{1}$. Assume towards contradiction that
our claim is not true. This means that run $r$ has all of its points in
$\mathcal{N}_{2}$. Notice that $r$ can not have points both in
$\mathcal{N}_{2}$ and $\mathcal{N}_{1}$, since this implies that $Q$ crosses
from $\mathcal{N}_{2}$ to $\mathcal{N}_{1}$. If $r$ has all of its points in
$\mathcal{N}_{2}$ then edge $(u,u^{\prime})$ must appear before $r$. An
example is shown in Figure 10(a).

Let $p$ be the sub-path of $Q$ from point $u$ to the first point of run $r$.
Denote by $\phi$ the continuous segment (corresponding to path $p$) from the
space point $l$ to the first point of run $r$. Notice that $\phi$ must be
above the boundary separating $\mathcal{N}_{1}$ and $\mathcal{N}_{2}$.
Consider the subset $\widetilde{\Phi}$ of $\Phi\cap\mathcal{N}_{2}$ which is
described by the following two boundaries. The bottom boundary is the boundary
separating $\mathcal{N}_{1}$ and $\mathcal{N}_{2}$. The top boundary is the
continuous segment $\phi$.

Run $r$ appears before the first chromatic run $r^{\prime}$ of colour $c_{1}$
in $Q$ which means that $p$ does not have a chromatic run of colour $c_{1}$.
By definition, all non-chromatic runs in path $Q$ and subsequently in $p$ are
in $\Phi$. Therefore, there are no red edges of path $\mathcal{Y}_{1}$ in
$\widetilde{\Phi}$. Let $p^{\prime}$ be the sub-path of $Q$ from the last
point of run $r$ to the ending point $\tau$ of $Q$. Clearly, run $r^{\prime}$
must be in path $p^{\prime}$.

Path $p^{\prime}$ can not cross the boundary from $\mathcal{N}_{2}$ to
$\mathcal{N}_{1}$. This means that all runs (chromatic and non-chromatic) in
$p^{\prime}$ must be in $\Phi\cap\mathcal{N}_{2}$. Further, because $Q$ is
non-self-crossing, all chromatic runs in $p^{\prime}$ must be in
$\widetilde{\Phi}$. There are no red edges of path $\mathcal{Y}_{1}$ in
$\widetilde{\Phi}$ which means that $p^{\prime}$ can not have a chromatic run
of colour $c_{1}$. However, this makes a contradiction because the chromatic
run $r^{\prime}$ of colour $c_{1}$ must be in path $p^{\prime}$. We conclude
that $r$ has all of its points in $\mathcal{N}_{1}$.

We now claim that run $r^{\prime}$ must have all of its points in
$\mathcal{N}_{2}$. Assume towards contradiction that our claim is not true.
Similarly, as before, it must be that $r^{\prime}$ has all of its points in
$\mathcal{N}_{1}$, otherwise we obtain a contradiction333If run $r^{\prime}$
has point both in $\mathcal{N}_{2}$ and $\mathcal{N}_{1}$ this implies that
$Q$ crosses from $\mathcal{N}_{2}$ to $\mathcal{N}_{1}$.. This means that
$r^{\prime}$ (and subsequently $r$) appear before edge $(u,u^{\prime})$
crossing from $\mathcal{N}_{1}$ to $\mathcal{N}_{2}$. According to Definition
14 the path from the last point of $r$ to the first point of $r^{\prime}$ has
a covering path since there is a continuous segment $\phi$ which connects two
points on the left and right boundary of $\Phi$ (i.e. the last point of $r$ on
path $\mathcal{Y}_{k-1}$ and the first point of $r^{\prime}$ on path
$\mathcal{Y}_{1}$).

The continuous segment $\phi$ is below the boundary separating
$\mathcal{N}_{2}$ and $\mathcal{N}_{1}$, since $r$ and $r^{\prime}$ appear
before edge $(u,u^{\prime})$. An example is shown in Figure 10(b). All runs
(chromatic and non-chromatic) in $Q$ are in $\Phi$. Further, $Q$ is non-self-
crossing. Thus, all runs after run $r^{\prime}$ in $Q$ must be below $\phi$
and subsequently below the boundary separating $\mathcal{N}_{1}$ and
$\mathcal{N}_{2}$. However, this makes a contradiction since the ending point
$\tau$ of $Q$ is in $\mathcal{N}_{2}$. We conclude that $r^{\prime}$ must have
all of its points in $\mathcal{N}_{2}$.

We now show that $Q$ can not have a chromatic run of colour $c_{k-1}$ which
appears after the first chromatic run $r^{\prime}$ of colour $c_{1}$. Let $p$
be the sub-path of $Q$ from point $u$ to the first point of run $r^{\prime}$.
Notice that path $p$ can not have a chromatic run of colour $c_{k-1}$ because
run $r$ is the last chromatic run of colour $c_{k-1}$ before run $r^{\prime}$
and appears before edge $(u,u^{\prime})$. Let $\phi$ be the continuous segment
(corresponding to path $p$) from space point $l$ to the first point of run
$r^{\prime}$.

Consider the subset $\widetilde{\Phi}$ of $\Phi\cap\mathcal{N}_{2}$ which is
described by the following two boundaries. The bottom boundary is the boundary
separating $\mathcal{N}_{1}$ and $\mathcal{N}_{2}$. The top boundary is the
continuous segment $\phi$. Notice that there are not any red edges of path
$\mathcal{Y}_{k-1}$ in $\widetilde{\Phi}$ since path $p$ does not have a
chromatic run of colour $c_{k-1}$. Let $p^{\prime}$ be the sub-path of $Q$
from the last point of run $r^{\prime}$ to the ending point $\tau$.

Path $p^{\prime}$ can not cross the boundary from $\mathcal{N}_{2}$ to
$\mathcal{N}_{1}$. This means that all runs (chromatic and non-chromatic) in
$p^{\prime}$ must be in $\Phi\cap\mathcal{N}_{2}$. Further, because $Q$ is
non-self-crossing, all chromatic runs in $p^{\prime}$ must be in
$\widetilde{\Phi}$. However, there is no chromatic run of colour $c_{k-1}$ in
$\widetilde{\Phi}$ and subsequently $p^{\prime}$ can not have a chromatic run
of colour $c_{k-1}$. Thus, there can not be a chromatic run of colour
$c_{k-1}$ after run $r^{\prime}$, which means that $Q$ is short
$(k-1)$-chromatic. ∎

(a)

(b)

Figure 10: Figures 10(a),10(b): The schematic representation of the proof for
Lemma 7.

Lemma 7 specifies the combinatorial structure of a $(k-1)$-chromatic
$\Phi$-path $Q$ for the special case where $Q$ does not cross from
$\mathcal{N}_{2}$ to $\mathcal{N}_{1}$. If path $Q$ crosses at least once and
at most $m\leq k-1$ times from $\mathcal{N}_{2}$ to $\mathcal{N}_{1}$, we
provide the following definition which will allow us to decompose $Q$ with
respect to its crossings from $\mathcal{N}_{2}$ to $\mathcal{N}_{1}$.

######  Definition 16.

Define $w_{i}$ for $i=1,2,\ldots,m$ to be the last point in $\mathcal{N}_{2}$
before the $i^{th}$ crossing of $Q$ from $\mathcal{N}_{2}$ to
$\mathcal{N}_{1}$. Let $w^{\prime}_{i}$ be the successor point of $w_{i}$ in
$Q$.

Without loss of generality, we assume that $m=k-1$. Let $\pi$ and $\tau$ be
the starting and ending point of $Q$, respectively. We decompose path $Q$ into
the following parts
$(\pi,w^{\prime}_{1}),(w^{\prime}_{1},w^{\prime}_{2}),\ldots,(w^{\prime}_{k-2},w^{\prime}_{k-1}),(w^{\prime}_{k-1},\tau)$.

For $i=1,2,\ldots,k-2$ the sub-path of $Q$ from $w^{\prime}_{i}$ to $w_{i+1}$
does not cross from $\mathcal{N}_{2}$ to $\mathcal{N}_{1}$ since the red edge
$(w_{i+1},w^{\prime}_{i+1})$ denotes the next crossing of $Q$ from
$\mathcal{N}_{2}$ to $\mathcal{N}_{1}$. Further, point $w^{\prime}_{i}$ is in
$\mathcal{N}_{1}$ and point $w_{i+1}$ is in $\mathcal{N}_{2}$ which means that
the sub-path of $Q$ from $w^{\prime}_{i}$ to $w_{i+1}$ has at least one point
both in $\mathcal{N}_{1}$ and $\mathcal{N}_{2}$. Thus, according to Lemma 7 we
obtain the following corollary.

######  Corollary 5.

For $i=1,2,\ldots,k-2$ if the sub-path of $Q$ from $w^{\prime}_{i}$ to
$w_{i+1}$ is $(k-1)$-chromatic then it is short $(k-1)$-chromatic.

######  Lemma 8.

For $i=1,2,\ldots,k-2$ if the sub-path of $Q$ from $w^{\prime}_{i}$ to
$w^{\prime}_{i+1}$ is $(k-1)$-chromatic then it is short $(k-1)$-chromatic.

###### Proof.

For any $i\in[1,k-2]$ let $q_{i}$ be the sub-path of $Q$ from $w^{\prime}_{i}$
to $w^{\prime}_{i+1}$ and let
$q^{\prime}_{i}=q_{i}\setminus\\{(w_{i+1},w^{\prime}_{i+1}\\}$ be the sub-path
of $q_{i}$ without the last red edge $(w_{i+1},w^{\prime}_{i+1})$. According
to Corollary 5 if path $q^{\prime}_{i}$ is $(k-1)$-chromatic then it must be
short $(k-1)$-chromatic. Without loss of generality, we assume that all
chromatic runs of colour $c_{1}$ appear before all chromatic runs of colour
$c_{k-1}$ in $q^{\prime}_{i}$.

We show that if we construct $q_{i}$ from $q^{\prime}_{i}$ by adding the red
edge $(w_{i+1},w^{\prime}_{i+1})$, then the short $(k-1)$-chromatic condition
is preserved. That is, all chromatic runs of colour $c_{1}$ appear before all
chromatic runs of colour $c_{k-1}$ in $q_{i}$.

Let $c_{j}$ where $j\in[1,k-1]$ be the colour of the red edge
$(w_{i+1},w^{\prime}_{i+1})$. If $j\in[2,k-1]$ then clearly our claim is true.
That is, the red edge $(w_{i+1},w^{\prime}_{i+1})$ is not of colour $c_{1}$
and therefore all chromatic runs of colour $c_{1}$ appear before all chromatic
runs of colour $c_{k-1}$ in path $q_{i}$. Thus, it remains to show that $j\neq
1$. Assume towards contradiction that $j=1$.

Notice that since $w^{\prime}_{i}\in\mathcal{N}_{1}$ and
$w_{i+1}\in\mathcal{N}_{2}$, path $q^{\prime}_{i}$ must have exactly one black
edge $(u,u^{\prime})$ which crosses from $\mathcal{N}_{1}$ to
$\mathcal{N}_{2}$. Let $l$ be the space point corresponding to the crossing
point of edge $(u,u^{\prime})$ with the boundary separating $\mathcal{N}_{1}$
and $\mathcal{N}_{2}$. Let $r$ be the last chromatic run of colour $c_{1}$
before the first chromatic run $r^{\prime}$ of colour $c_{k-1}$ in
$q^{\prime}_{i}$. Following the same methodology as in Lemma 7, we can obtain
that edge $(u,u^{\prime})$ must appear between $r$ and $r^{\prime}$. This
means that $r$ has all of its points in $\mathcal{N}_{1}$ and run $r^{\prime}$
has all of its points in $\mathcal{N}_{2}$.

Let $p$ be the sub-path of $q^{\prime}_{i}$ from point $u$ to the first point
of run $r^{\prime}$ and let $\phi$ be the continuous segment (corresponding to
this path) from the space point $l$ to the first point of run $r^{\prime}$.
All points after $u$ in $q^{\prime}_{i}$ must be in $\mathcal{N}_{2}$ and
therefore the continuous segment $\phi$ is above the boundary separating
$\mathcal{N}_{1}$ from $\mathcal{N}_{2}$. Further, run $r$ is the last
chromatic run of colour $c_{1}$ before $r^{\prime}$ and $r$ appears before
edge $(u,u^{\prime})$. Thus, path $p$ does not have a chromatic run of colour
$c_{1}$.

Consider the subset $\widetilde{\Phi}$ of $\Phi\cap\mathcal{N}_{2}$ which is
described with the following two boundaries. The top boundary is the
continuous segment $\phi$. The bottom boundary is the boundary separating
$\mathcal{N}_{1}$ from $\mathcal{N}_{2}$. An example is shown in Figure 11(a).
There are not any red edges of path $\mathcal{Y}_{1}$ in $\widetilde{\Phi}$
since path $p$ does not traverse any chromatic run of colour $c_{1}$.

Therefore, if $j=1$, that is, the red edge $(w_{i+1},w^{\prime}_{i+1})$ is of
colour $c_{1}$, then point $w_{i+1}\in\mathcal{N}_{2}$ must be in the exterior
of $\widetilde{\Phi}$. Clearly, the last point of run $r^{\prime}$ is in
$\widetilde{\Phi}$. Let $p^{\prime}$ be the sub-path of $q^{\prime}_{i}$ from
the last point of run $r^{\prime}$ to point $w_{i+1}$. All runs (chromatic and
non-chromatic) in $p^{\prime}$ must be in $\Phi$. Path $p^{\prime}$ can not
cross the boundary separating $\mathcal{N}_{1}$ and $\mathcal{N}_{2}$. Thus,
all runs in $p^{\prime}$ must be in $\Phi\cap\mathcal{N}_{2}$.

Therefore, path $p^{\prime}$ must cross with the top boundary of
$\widetilde{\Phi}$ (i.e. the continuous segment $\phi$ corresponding to path
$p$) since $w_{i+1}$ is on the exterior of $\widetilde{\Phi}$ and the last
point of run $r^{\prime}$ is in $\widetilde{\Phi}$. This, implies that path
$p^{\prime}$ crosses with path $p$, which makes a contradiction. ∎

Figure 11(b) shows an example of a non-self-crossing $\Phi$-path $Q$ which
crosses from $\mathcal{N}_{2}$ to $\mathcal{N}_{1}$ exactly $(k-1)$ times for
$k=6$. Observe that the sub-path of $Q$ from $w^{\prime}_{i}$ to
$w^{\prime}_{i+1}$ for $i=1,2,\ldots,k-2$ is short $(k-1)$-chromatic.

(a)

(b)

Figure 11: Figure 11(a): The subset $\widetilde{\Phi}$ of
$\Phi\cap\mathcal{N}_{2}$ is shown with the shaded territory. Figure 11(b): An
example of a non-self-crossing $\Phi$-path $Q$ from a point $\pi$ to a point
$\tau$ which crosses exactly $(k-1)$ times from $\mathcal{N}_{2}$ to
$\mathcal{N}_{1}$ (for $k=6$).

###### Proof of Theorem 7.

For a sub-network $\mathcal{N}[\beta_{1},\beta_{2}]$ consider a $\Phi$-path
$Q$ in this sub-network. Without loss of generality, we assume that $Q$ is
$(k-1)$-chromatic and that $Q$ has points both in $\mathcal{N}_{1}$ and
$\mathcal{N}_{2}$. Recall that when algorithm $\mathcal{Z}_{k}$ is applied to
sub-network $\mathcal{N}[\beta_{1},\beta_{2}]$ the computation consists of
three phases.

The first and third phase call algorithm $\mathcal{Z}_{k}$ recursively on
$\mathcal{N}_{2}$ and $\mathcal{N}_{1}$, respectively. The second phase
consists of two steps. The first step calls algorithm
$\Delta(\mathcal{Y}_{1},\mathcal{Y}_{2},\ldots,\mathcal{Y}_{k-1})$. The second
step consists of $(k-2)$ iterations, where each iteration performs two calls
of algorithm $\widehat{\mathcal{A}}_{k-1}$ on sub-network
$\mathcal{N}[\beta_{1},\beta_{2}]$.

If $Q$ does not cross from $\mathcal{N}_{2}$ to $\mathcal{N}_{1}$, according
to Lemma 7 we have that $Q$ short $(k-1)$-chromatic. According to Lemma 4 when
algorithm $\widehat{\mathcal{A}}_{k-1}$ is applied twice to sub-network
$\mathcal{N}[\beta_{1},\beta_{2}]$ the computation follows every non-self-
crossing path which short $(k-1)$-chromatic. Algorithm $\mathcal{Z}_{k}$
includes at least two calls to algorithm $\widehat{\mathcal{A}}_{k-1}$ and
therefore the computation follows path $Q$.

If $Q$ crosses at least once and at most $m\leq k-1$ from $\mathcal{N}_{2}$ to
$\mathcal{N}_{1}$, recall that according to Definition 16, we define $w_{i}$
for $i=1,2,\ldots,m$ to be the last point in $Q$ before the $i^{th}$ crossing
from $\mathcal{N}_{2}$ to $\mathcal{N}_{1}$. We denote by $w^{\prime}_{i}$ the
successor of $w_{i}$ in $Q$. Consider the decomposition of $Q$ into the
following parts
$(\pi,w^{\prime}_{1}),(w^{\prime}_{1},w^{\prime}_{2}),\ldots,(w^{\prime}_{k-2},w^{\prime}_{k-1})(w^{\prime}_{k-1},\tau)$
where $\pi$ and $\tau$ is the starting and ending point of $Q$, respectively.

If the the sub-path of $Q$ from $\pi$ to $w_{1}$ is not empty then it can only
have points in $\mathcal{N}_{2}$. Similarly, if the the sub-path of $Q$ from
$w^{\prime}_{k-1}$ to $\tau$ is not empty then it can only have points in
$\mathcal{N}_{1}$. We now assume by induction that Theorem 7 holds for $k$ and
a sub-network of size less than $n$.

By the induction hypothesis, when algorithm $\mathcal{Z}_{k}$ is applied to
sub-network $\mathcal{N}_{2}$ the computation follows every $\Phi$-path that
has only points in $\mathcal{N}_{2}$. Thus, the computation of the first phase
(i.e. first recursive call) follows follows the sub-path of $Q$ from $\pi$ to
$w_{1}$.

The second phase consists of two steps. The first step calls algorithm
$\Delta(\mathcal{Y}_{1},\mathcal{Y}_{2},\ldots,\mathcal{Y}_{k-1})$ whose
computation follows the red edge $(w_{1},w^{\prime}_{1})$. We now claim that
for $i=1,2,\ldots,k-2$ the computation in the $i^{th}$ iteration of the second
step, follows the sub-path of $Q$ from $w^{\prime}_{i}$ to $w^{\prime}_{i+1}$.
According to Lemma 8, the sub-path of $Q$ from $w^{\prime}_{i}$ to
$w^{\prime}_{i+1}$ can be either at most $(k-2)$-chromatic or short
$(k-1)$-chromatic

In the former case, according to Lemma 3 when algorithm
$\widehat{\mathcal{A}}_{k-1}$ is applied to sub-network
$\mathcal{N}[\beta_{1},\beta_{2}]$ the computation follows every non-self-
crossing path which is at most $(k-2)$-chromatic. In the latter case,
according to Lemma 4 when algorithm $\widehat{\mathcal{A}}_{k-1}$ is applied
twice to sub-network $\mathcal{N}[\beta_{1},\beta_{2}]$ the computation
follows every non-self-crossing path which is short $(k-1)$-chromatic.

The $i^{th}$ iteration of the second step for $i=1,2,\ldots,k-2$ consists of
two applications of algorithm $\widehat{\mathcal{A}}_{k-1}$ to the sub-
network. We conclude that the computation in the $i^{th}$ iteration for
$i=1,2,\ldots,k-2$ follows the sub-path of $Q$ from $w^{\prime}_{i}$ to
$w^{\prime}_{i+1}$.

By the induction hypothesis, when algorithm $\mathcal{Z}_{k}$ is applied to
sub-network $\mathcal{N}_{1}$ the computation follows every $\Phi$-path that
has only points in $\mathcal{N}_{2}$. Thus, the computation in the third phase