Improved Algorithms for Computing k-Sink on
Dynamic Path Networks

arXiv:1609.01373v1 [] 6 Sep 2016

Binay Bhattacharya1 , Mordecai J. Golin2 , Yuya Higashikawa3 ,
Tsunehiko Kameda4 , and Naoki Katoh5
1,4 School of Computing Science, Simon Fraser University, Vancouver, Canada
binay@sfu.ca, tikokameda@gmail.com
2
Dept. of Computer Science, Hong Kong Univ. of Science and Technology,
Hong Kong
golin@cse.ust.hk
3
Dept. of Information and System Engineering, Chuo University, Tokyo, Japan
higashikawa.874@g.chuo-u.ac.jp
5
School of Science and Technology, Kwansei Gakuin University, Hyogo, Japan
naoki.katoh@gmail.com

Abstract
We present a novel approach to finding the k-sink on dynamic path networks with general edge
capacities. Our first algorithm runs in O(n log n + k 2 log4 n) time, where n is the number of
vertices on the given path, and our second algorithm runs in O(n log3 n) time. Together, they
improve upon the previously most efficient O(kn log2 n) time algorithm due to Arumugam et
al. [1] for all values of k. In the case where all the edges have the same capacity, we again present
two algorithms that run in O(n + k 2 log2 n) time and O(n log n) time, respectively, and they
together improve upon the previously best O(kn) time algorithm due to Higashikawa et al. [10]
for all values of k.
1998 ACM Subject Classification F.2.2
Keywords and phrases Facility location, k-sink, parametric search, dynamic path network
Digital Object Identifier 10.4230/LIPIcs...

1

Introduction

Investigation of evacuation problems dates back many years [7, 11]. The k-sink problem
is to locate k sinks in such a way that every evacuee can evacuate to a sink as quickly as
possible, when disasters, such as earthquakes and tsunamis, strike. The problem can be
modeled by a network whose vertices represent the places where the evacuees are initially
located and the edges represent possible evacuation routes. Associated with each edge is the
transit time across it in either direction and its capacity in terms of the number of people
who can enter it per unit time [7]. Madama et al. [12] solved this problem for the dynamic
tree networks in O(n log2 n) time under the condition that only a vertex can be a sink. For
the 1-sink problem in the dynamic tree networks with uniform edge capacities, Higashikawa
et al. proposed an O(n log n) algorithm [9] with the condition that the sink can be either at
a vertex or on an edge.
On dynamic path networks with uniform edge capacities, it is straightforward to compute
the 1-sink in linear time [2]. The k-sink problem for dynamic path networks with general
and uniform edge capacities was solved in O(kn log2 n) time by Arumugam et al. [1] and in
O(kn) time by Higashikawa et al. [10], respectively.
© Binay Bhattacharya, Mordecai J. Golin, Yuya Higashikawa, Tsunehiko Kameda and Naoki Katoh;
licensed under Creative Commons License CC-BY
Leibniz International Proceedings in Informatics
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany

k-sink on dynamic path networks

2

In this paper we present two algorithms for the k-sink problem for the dynamic path
networks with general edge capacities. Together, they outperform all other known algorithms.
We also present two algorithms for the dynamic path networks with uniform edge capacities.
All our algorithms consists of two levels: feasibility tests at the lower level, and optimization
at the higher level, making use of feasibility tests. Our results presented in this paper are
the first algorithms that run in sub-quadratic time in n, regardless of the value of k, which
can grow with n.
This paper is organized as follows. In the next section, we define our model and the
terms that are used throughout the paper. In Sec. 3, we give an overview of our algorithm.
Sec. 4 introduces a data structure called the critical cluster tree, which plays a central role
in the rest of the paper. In Sec. 5, we identify two important tasks that form building blocks
of our algorithms. and also discuss feasibility test. Sec. 6 presents several algorithms for
uniform and general edge capacities. Finally, Sec. 7 concludes the paper.

2

Preliminaries

Let P = (V, E) be a path network, whose vertices v1 , v2 , . . . , vn are arranged from left to right
in this order. For i = 1, 2, . . . , n, vertex vi has an integral weight wi (> 0), representing the
number of evacuees, and each edge ei = (vi , vi+1 ) has a fixed non-negative length (distance)
li and capacity ci . We assume that all evacuees from a vertex evacuate to the same sink. We
also assume that a sink has infinite capacity, so that the evacuees coming from the left and
right of a sink do not interfere with each other. By x ∈ P , we mean that point x lies on
either an edge or a vertex of P . For a vertex v, v + (resp. v − ) denotes the point just to the
right (resp. left) of vertex v that is arbitrarily close to v. For a, b ∈ P , a ≺ b or b  a means
that a lies to the left of b. Let d(a, b) denote the distance between a and b. If a and/or b lies
on an edge, we use the prorated distance. The transit time for a unit distance is denoted
by τ , so that it takes d(a, b)τ time to travel from a to b. Let c(a, b) denote the minimum
capacity of the edges on the subpath of P between a and b. Let V [a, b] denote the set of
vertices on the path from a to b. The subpath from a to b, including a and b, is denoted by
P [a, b]. If a (resp. b) is excluded, we use P (a, b] (resp. P [a, b)). Define
X
W [vi , vj ] =
wl .
(1)
vl ∈V [vi ,vj ]

Clearly W [vi , vj ] can be computed in constant time once we construct the array {W [v1 , vj ] |
j = 1, 2, . . . , n} in O(n) time.
Given a subpath P [vi , vj ] of a dynamic path network P and a sink s ∈ P [vi , vj ], let
Θ(s, [vi , vj ]) denote the evacuation time to s for the evacuees on P [vi , vj ]. We also define the
L-cost (resp. R-cost) of vertex vh ∈ V [vi , vj ] in P [vi , vj ], as seen from s  vj (resp. s ≺ vi )
to be the least evacuation time to s for all the evacuees on the vertices on P [vi , vh ] (resp.
P [vh , vj ]), assuming that they all arrive at s as continuously as possible. For any vertex
vh ∈ V [vi , vj ], its L-cost and R-cost are thus
θL (s, [vi , vh ])
θR (s, [vh , vj ])

W [vi , vh ]
for x  vj ,
c(vh , s)
W [vh , vj ]
= d(s, vh )τ +
for x ≺ vi .
c(s, vh )

= d(vh , s)τ +

Note that each of these functions is linear in the distance to s.

(2)
(3)

B. Bhattacharya et al.

3

I Lemma 1. [1, 8] Given a subpath P [vi , vj ] of a dynamic path network P and a sink
s ∈ P [vi , vj ], Θ(s, [vi , vj ]) is represented by the following formula:


Θ(s, [vi , vj ]) = max
max θL (s, [vi , vh ]), max θR (s, [vh , vj ]) .
(4)
vh ∈V [vi ,s]

vh ∈V [s,vj ]

A problem instance is said to be (t, k)-feasible if exist k sinks such that every evacuee can
reach a sink within time t. In our algorithms proposed in this paper, we perform preprocessing
to construct a useful data structure, which makes (t, k)-feasibility test efficient.

3

Overall strategy of our algorithm

To carry out (t, k)-feasibility test, we repeatedly solve the following problems:
L-test(P [vi , vj ], t): It returns yes if every evacuee on a subpath P [vi , vj ] can reach a sink
vj+ within time t. Otherwise it returns no.
R-test(P [vi , vj ], s, t): It returns yes if every evacuee on a subpath P [vi , vj ] can reach a sink
s within time t where s is located on (vi−1 , vi ]. Otherwise it returns no.
As will be seen in Sec. 4, each of L-test(P [vi , vj ], t) and R-test(P [vi , vj ], s, t) can be done
in O(log2 n) time after constructing the data structure (called critical cluster tree). The
critical cluster tree is a balanced binary search tree with height O(log n).

3.1

Feasibility test

The (t, k)-feasibility can be tested as follows: We first compute
l1 = max{j | 1 ≤ j ≤ n, L-test(P [v1 , vj ], t) is "yes"}.

(5)

and find a sink s1 ∈ (vl1 , vl1 +1 ]. We then compute
r1 = max{j | l1 + 1 ≤ j ≤ n, R-test(P [vl1 +1 , vj ], s1 , t) is "yes"}.

(6)

Repeating this procedure, if we eventually obtain rk = n, (t, k)-feasibility test succeeds. If
rk < n, it fails. In fact, as will be seen in Sec. 5.2, (t, k)-feasibility test can be done in
O(k log3 n) time.
Using (t, k)-feasibility test as a subroutine, we can find a minimum value t∗ such that
∗
(t , k)-feasibility test succeeds, which gives us an optimal evacuation time. This can be done
by executing (t, k)-feasibility tests in binary search fashion.

3.2

Machineries in the data structure

The key idea is to use the balanced binary search tree T with appropriate information
stored at each node of the tree which enables us to execute each of L-test(P [vi , vj ], t) and
R-test(P [vi , vj ], s, t) in O(log2 n) time.
For L-test(P [vi , vj ], t), we need to compute
ΘL (vi , vj ) =

max

vh ∈V [vi ,vj ]

θL (vj+ , [vi , vh ]).

(7)

Also for R-test(P [vi , vj ], s, t), we need to compute
ΘR (vi , vj , s) =

max

vh ∈V [vi ,vj ]

θR (s, [vh , vj ]).

(8)

k-sink on dynamic path networks

4

L-test(P [vi , vj ], t) succeeds if and only if ΘL (vi , vj ) ≤ t and R-test(P [vi , vj ], s, t) succeeds if
and only if ΘR (vi , vj , s) ≤ t.
For leaf nodes l(vi ) and l(vj ) in T which correspond to vi and vj , respectively, let u be the
least common ancestor of T . Then in the subtree T (u) with the root u in T , we can identify
a set of vertex-disjoint subpaths which covers vertices of P [vi , vj ] such that the number of
such subpaths is O(log n), and every subpath corresponds to the set of leaves that a subtree
T (u0 ) spans for some node u0 in T (u). Let P[vi , vj ] denote the set of such subpaths.
In the rest of this section, we only show how to compute ΘL (vi , vj ) since ΘR (vi , vj , s) is
symmetric, so can be similarly computed. The computation of (7) reduces to


ΘL (vi , vj ) =
max
max θL (vj+ , [vi , vh ]) .
(9)
P [vl ,vr ]∈P[vi ,vj ]

vh ∈V [vl ,vr ]

To evaluate (9), we need to compute
max

vh ∈V [vl ,vr ]

θL (vj+ , [vi , vh ]) =


max

vh ∈V [vl ,vr ]

d(vh , vj+ )τ +

W [vi , vh ]
c(vh , vj+1 )


(10)

for every subpath P [vl , vr ] ∈ P[vi , vj ]. Since vi ≤ vl ≤ vr ≤ vj , the right side of (10) is
rewritten as


W [vi , vl−1 ] + W [vl , vh ]
+
max
d(vh , vr )τ + d(vr , vj )τ +
.
(11)
min{c(vh , vr ), c(vr , vj+1 )}
vh ∈V [vl ,vr ]
Suppose that u0 is a node of T spanning P [vl , vr ]. Then, to facilitate the computation of
(11) for general case, we will prepare at node u0 the following machinery that allows us to
compute


W + W [vl , vh ]
L
costu0 (W, C) = max
d(vh , vr )τ +
(12)
min{c(vh , vr ), C}
vh ∈V [vl ,vr ]
in O(log n) time once W and C are given. Here W and C are unknown parameters. This
part will be explained in more detail in Sec. 4.

4

Data structures for the edge-capacitated case

We want to perform (t, k)-feasibility tests for many different values of completion time t.
Therefore, it will be useful to spend some time during preprocessing to construct data
structures which facilitate those tests. Let us consider an arbitrary subpath P [vi , vj ],
where i ≤ j. The vertex vk ∈ V [vi , vj ] that maximizes θL (x, [vi , vk ]) at x  vj (resp.
θR (vi−1 , [vk , vj ]) at x ≺ vi ) is called the L-critical vertex (resp. R-critical vertex) of P [vi , vj ]
w.r.t. x, and the corresponding subpath P [vi , vk ] (resp. P [vk , vj ]) is called the L-critical
cluster (resp. R-critical cluster) of P [vi , vj ] w.r.t. x. It is easy to show the following
proposition.
I Proposition 1. The L-critical (resp. R-critical) vertex/cluster w.r.t. x is the same for all
points x on an edge, excluding its left (resp. right) end vertex.
J
Therefore, we can talk about a critical vertex/cluster w.r.t. an edge. The L-critical vertex of
P [vi , vj ] w.r.t. edge (vj , vj+1 ) (resp. R-critical vertex of P [vi , vj ] w.r.t. edge (vi−1 , vi )) is
[i,j]
[i,j]
denoted by cL (resp. cR ), and L-critical cluster of P [vi , vj ] w.r.t. edge (vj , vj+1 ) (resp.
[i,j]
[i,j]
R-critical cluster of P [vi , vj ] w.r.t. edge (vi−1 , vi )) is denoted by CL (resp. CR ). We
[i,j]
[i,j]
[i,j]
[i,j]
thus have CL = P [vi , cL ] and CR = P [cR , vj ].

B. Bhattacharya et al.

4.1

5

Critical cluster tree

We first construct the critical cluster tree (or CC-tree for short), T , with root ρ, whose
leaves are the vertices of P , arranged from left to right. It is a balanced tree with height
O(log n). In balancing, the vertex weights are not considered. See Fig. 1, where π(vi , ρ)
denotes the path from vi to root ρ. For a node1 u of T , let T (u) denote the subtree rooted
ρ
u2

π(vi, ρ)

u3

u1
v1

vi

π(vj , ρ)

vL(u2)

vR (u2)

vj vj+1

vn

Figure 1 CC-tree T .

at u, let ul (resp. ur ) be its left (resp. right) child node, and let vL (u) (resp. vR (u))
denote the leftmost (resp. rightmost) vertex on P that belongs to T (u). We say that T (u)
spans subpath P [vL (u), vR (u)] and also u spans P [vL (u), vR (u)]. At node u, we store two
sorted lists of capacities c(vh , vR (u)) for vh ∈ V [vL (u), vR (u)] \ {vR (u)} and c(vL (u), vh ) for
vh ∈ V [vL (u), vR (u)] \ {vL (u)}. The list of c(vh , vR (u)) can be computed in the decreasing
order in h in O(|T (u)|) time. Symmetrically, the list of c(vL (u), vh ) can be also computed in
O(|T (u)|) time.
For L-test(P [vi , vj ], t) and R-test(P [vi , vj ], s, t) mentioned in Sec. 3, we need to determine
[i,j]
[i,j]
cL and cR , respectively. To do this, for every highest node u of T spanning a subpath of
P [vi , vj ] we will prepare a machinery at each node u of T that allows us to compute

W + W [vL (u), vh ]
d(vh , vR (u))τ +
,
min{c(vh , vR (u)), C}
vh ∈V [vL (u),vR (u)]


W [vh , vR (u)] + W
costR
(W,
C)
=
max
d(v
(u),
v
)τ
+
.
L
h
u
min{C, c(vL (u), vh )}
vh ∈V [vL (u),vR (u)]

costL
u (W, C) =



max

(13)
(14)

in O(log n) for arbitrary W and C.
Suppose that we have such a machinery at each node u. Once P [vi , vj ] is given, for a
node u spanning a subpath of P [vi , vj ], W and C are given as W [vi , vl−1 ] (where vl = vL (u))
and c(vR (u), vj ) in (13), respectively. Let us call a vertex which achieves the maximum value
in (13) w.r.t. u, W = W [vi , vl−1 ] and C = c(vR (u), vj ) an L-critical candidate of P [vi , vj ].
[i,j]
Then one of L-critical candidates of P [vi , vj ] must be cL , which implies that we can do an
2
L-test(P [vi , vj ], t) in O(log n) time since there are O(log n) nodes spanning vertex-disjoint
subpaths of P [vi , vj ]. Similarly, an R-critical candidate of P [vi , vj ] is defined, and one of
[i,j]
R-critical candidates of P [vi , vj ] is cR , thus R-test(P [vi , vj ], s, t) can be done in O(log2 n)
time.
To compute costL
u (W, C), one idea is to prepare a two-dimensional table at node u which
returns the L-critical vertex of P [vi , vj ] for queries of W and C, but it takes much time and
space in total. Instead of this, we actually store at node u two linear tables of vertices in

1

We use the term “node” here to distinguish it from the vertices on the path. A vertex, being a leaf of T ,
is considered a node, but an interior node of T is not a vertex.

k-sink on dynamic path networks

6

V [vL (u), vR (u)]: one returns a vertex vu1 (W ) for a query of W which achieves


W + W [vL (u), vh ]
max
d(vh , vR (u))τ +
,
c(vh , vR (u))
vh ∈V [vL (u),vR (u)]
and the other one returns a vertex vu2 (C) for a query of C which achieves


W [vL (u), vh ]
max
d(vh , vR (u))τ +
.
C
vh ∈V [vL (u),vR (u)]

(15)

(16)

We call the first table the left weight table of u and the other the left capacity table of u. Also,
to compute costR
u (W, C), we store similar two tables at node u, called the right weight table
of u and the right capacity table of u. Note that for each leaf node u = vi (which is a vertex
of P ), tables always return vi itself for any W and C. In Sec. 5.1, we will show how to use
these tables to compute (13) and (14).

4.2

CC-tree construction

In this section, we show how to construct the left weight table and the left capacity table
at a node u of T . Note that in the construction of CC-tree, we can construct tables of u
without using any information stored at children ul and ur .
(a) Weight table: For a vertex vh ∈ V [vL (u), vR (u)], let fh1 (W ) denote a function of W
such that
fh1 (W ) = αh1 W + βh1 ,

(17)

where αh1 = 1/c(vh , vR (u)) and βh1 = d(vh , vR (u))τ + W [vL (u), vh ]/c(vh , vR (u)). Then the
equation (15) can be rewritten as
max

vh ∈V [vL (u),vR (u)]

fh1 (W ).

(18)

Note that once we compute the upper envelope of fh1 (W ) for all vh ∈ V [vL (u), vR (u)], it can
return a vertex vu1 (W ) for a query of W which achieves (18), which is equivalent to the left
weight table of u. Here fh1 (W ) is a linear function in W and αh1 is decreasing in h. Using the
concept of duality of lines and points in 2-D, it is known that computing the upper envelope
of lines is equivalent to computing the lower convex hull of points [3, 14]. As noted in [14],
it is known that if points are sorted in x-coordinates, the convex hull can be computed in
linear time by using the Graham scan algorithm [6]. Summarizing these facts, we can obtain
the left weight table of u in O(|T (u)|) time,
(b) Capacity table: For a vertex vh ∈ V [vL (u), vR (u)], let fh2 (1/C) denote a function of
1/C such that
fh2 (1/C) = αh2 · (1/C) + βh2 ,

(19)

where αh2 = W [vL (u), vh ] and βh2 = d(vh , vR (u))τ . Then the equation (16) can be rewritten
as
max

vh ∈V [vL (u),vR (u)]

fh2 (1/C).

(20)

Here fh2 (1/C) is a linear function in 1/C and αh2 is increasing in h, we thus can compute the
upper envelope of fh2 (1/C) for all vh ∈ V [vL (u), vR (u)] in O(|T (u)|) time, which is equivalent
to the left capacity table of u (similarly to (a)).

B. Bhattacharya et al.

7

I Lemma 2. Given a dynamic path network with n vertices and general edge capacities, we
can construct its CC-tree, T , in O(n log n) time.
Proof. We construct two sorted lists of capacities, two weight tables and two capacity tables
at every node u one by one (which does not need to be performed bottom up). As mentioned
above, these all can be constructed in O(|T (u)|) time. For a non-negative integer d, let
U (d) denote a set of nodes of T such that each node u ∈ U (d) is located at depth d from
root ρ (see Fig. 1). Therefore, letting h be the height of T , the total time required to
Ph P
construct T can be represented as d=0 u∈U (d) O(|T (u)|). We here have h = O(log n) and
P
u∈U (d) O(|T (u)|) = O(n) since for a fixed d, T (u) for all u ∈ U (d) are vertex-disjoint, thus
the total time is O(n log n).
J

5

Two main tasks

There are two useful tasks that we can call upon repeatedly. Task 1 is to find a maximal
subpath P [va , vd ], given the starting vertex va , such that we can place a 1-sink on it to
enable all the evacuees to evacuate to it within time t. Task 2 is to find a 1-sink on a given
subpath P [vi , vj ]. We want to construct an algorithm for each of these tasks.
In the two algorithms, given a subpath P [vi , vj ] and a node u of T spanning a subpath
P [vl , vr ] (i.e., vl = vL (u) and vr = vR (u)) of P [vi , vj ], we need to compute (13) with
W = W [vi , vl−1 ] and C = c(vr , vj ), and (14) with W = W [vr+1 , vj ] and C = c(vi , vl ). We
first show the following lemma.
I Lemma 3. Assume that the CC-tree, T , is available. Then, given a subpath P [vi , vj ]
and a node u of T spanning a subpath P [vl , vr ] of P [vi , vj ], the L-critical candidate and the
R-critical candidate of P [vi , vj ] belonging to P [vl , vr ] can be computed in O(log n) time.
Proof. We only prove the case of the L-critical candidate, letting W = W [vi , vl−1 ] and
C = c(vr , vj ) (the proof for the R-critical candidate is symmetric).
Suppose that there exists an integer h∗ satisfying l ≤ h∗ ≤ r − 2 such that c(vh∗ , vr ) ≤ C
and c(vh∗ +1 , vr ) > C (if does not exist, c(vh , vr ) ≤ C for every h satisfying l ≤ h ≤ r − 1 or
c(vh , vr ) > C for every h satisfying l ≤ h ≤ r − 1). Note that such h∗ uniquely exists since
c(vh , vr ) is increasing in h. We first separate P [vl , vr ] to two subpaths P1 = P [vl , vh∗ ] and
P2 = P [vh∗ +1 , vr ], which can be done in O(log n) time by binary search over the sorted list
of capacities stored at u. Letting V1 = V [vl , vh∗ ] and V2 = V [vh∗ +1 , vr ], we then consider


W + W [vl , vh ]
costL
(W,
C,
P
)
=
max
d(v
,
v
)τ
+
h r
1
u
vh ∈V1
min{c(vh , vr ), C}


W + W [vl , vh ]
= max d(vh , vr )τ +
,
(21)
vh ∈V1
c(vh , vr )
and
costL
u (W, C, P2 )



=
=
=

W + W [vl , vh ]
max d(vh , vr )τ +
vh ∈V2
min{c(vh , vr ), C}


W + W [vl , vh ]
max d(vh , vr )τ +
vh ∈V2
C


W [vl , vh ]
W
max d(vh , vr )τ +
+
.
vh ∈V2
C
C



(22)

L
L
Note that costL
u (W, C) = max{costu (W, C, P1 ), costu (W, C, P2 )}. By binary search over
the left weight table of u, we can identify a vertex v1∗ maximizing {d(vh , vr )τ + (W +

k-sink on dynamic path networks

8

W [vl , vh ])/c(vh , vr )} for vh ∈ V1 ∪ V2 in O(log n) time. Similarly, using the left capacity table
of u, we can identify a vertex v2∗ maximizing {d(vh , vr )τ + W [vl , vh ]/C} for vh ∈ V1 ∪ V2 in
O(log n) time. Note that if v1∗ ∈ V2 ,
costL
u (W, C, P1 ) ≤
<

W + W [vl , vh ]
c(v1∗ , vr )
W + W [vl , vh ]
d(v1∗ , vr )τ +
≤ costL
u (W, C, P2 ).
C
d(v1∗ , vr )τ +

and if v2∗ ∈ V1 ,
costL
u (W, C, P2 ) ≤
≤

W + W [vl , vh ]
C
W
+
W
[vl , vh ]
d(v1∗ , vr )τ +
≤ costL
u (W, C, P1 ),
c(v2∗ , vr )
d(v2∗ , vr )τ +

which implies that v1∗ ∈ V2 and v2∗ ∈ V1 never occur simultaneously. Therefore, if v1∗ ∈ V2 ,
L
∗
v2∗ ∈ V2 and costL
u (W, C, P1 ) < costu (W, C, P2 ), thus v2 is the L-critical candidate of P [vi , vj ].
L
∗
∗
If v2∗ ∈ V1 , costL
u (W, C, P1 ) ≥ costu (W, C, P2 ) and v1 ∈ V1 holds, thus v1 is the L-critical
∗
∗
∗
candidate of P [vi , vj ]. Otherwise v1 ∈ V1 and v2 ∈ V2 , then v1 achieves costL
u (W, C, P1 ) and
v2∗ also achieves costL
(W,
C,
P
),
respectively.
We
then
compare
these
two
costs
and choose
2
u
one whose cost is larger.
J

5.1

Basic algorithms

Let us first design an algorithm for Task 1, referring to Fig. 2, which shows a part of the
CC-tree T . Here is an informal description of the algorithm.
ρ

ρ

u
ul

u
ur

ul

u0

ur

u0
P
vb s

va
Evacuate to s

P

s vc

vd
Evacuate to s

Figure 2 Left: Looking for rightmost vb such that the evacuees from P [va , vb ] can evacuate to
sink s within time t; Right: Looking for rightmost vd whose evacuees can evacuate to sink s within
time t.

I Algorithm 1. Isolate-subpath(t, va )
1. Start at leaf u = va of T ,2 and move up towards its root ρ. At each node u visited,
do L-test(P [va , vR (u)], t), i.e., compute the cost of the L-critical vertex of subpath
P [va , vR (u)] w.r.t. vR (u)+ , say ΘL (va , vR (u)). If L-test(P [va , vR (u)], t) returns "yes", i.e.,
ΘL (va , vR (u)) ≤ t, then move to its parent node p and set u = p. If L-test(P [va , vR (u)], t)
returns "no", then move to the right child node ur and set u = ur . Start moving down
towards a leaf.
2. At each node visited during moving down, do L-test(P [va , vR (u)], t). If "yes", then move
to its parent’s right child node pr and set u = pr . If "no", then move to the left child

2

See the left figure in Fig. 2.

B. Bhattacharya et al.

9

node ul and set u = ul . If u comes to a leaf, say vb , locate the 1-sink s ∈ (vb , vb+1 ] to the
left as much as possible.
3. Start from the vertex vc that lies immediately to the right of s.3 Performing an up-down
search similar to above 1 and 2 so that R-test(P [vc , vR (u)], s, t) is done at each visited
node u, determine the rightmost vertex vd whose evacuees can reach sink s within time t.
I Lemma 4. Assume that the CC-tree, T , is available. Then Isolate-subpath(t, va ) runs
in O(log3 n) time.
Proof. At each node u, Isolate-subpath(t, va ) carries out L-test(P [vc , vR (u)], t) or Rtest(P [vc , vR (u)], s, t). Each of them needs to find the critical vertex by comparing O(log n)
critical candidates. A critical candidate can be computed in O(log n) time by Lemma 3.
Since Isolate-subpath(t, va ) visits O(log n) nodes, the total time is O(log3 n).
J
I Algorithm 2. Find-1sink(vi , vj )
1. Let u be the node where the two paths π(vi , ρ) and π(vj , ρ) meet.
2. If the L-critical vertex of P [vi , vR (ul )] and the R-critical vertex of P [vL (ur ), vj ] have the
same cost4 at some point x on the edge (vR (ul ), vL (ur )), then return x as the 1-sink.
3. If the L-critical vertex has a higher (resp. lower) cost than the R-critical vertex at every
point on edge (vR (ul ), vL (ur )), then let u = ul (resp. u = ur ) and repeat Step 2, using
the new ul and ur .
Using the arguments similar to those in the proof of Lemma 4, we can prove the following
lemma.
I Lemma 5. Assume that the CC-tree, T , is available. Then Find-1sink(vi , vj ) finds the
1-sink on a given subpath P [vi , vj ] in O(log3 n) time.

5.2

(t, k)-feasibility test

Our approach is to find the maximal subpath from the left end of P for which a 1-sink can
achieve completion time t.
I Lemma 6. Given a dynamic path network with n vertices, assume that its CC-tree, T , is
available. Then we can test its (t, k)-feasibility in O(k log3 n) time.
Proof. Starting at the leftmost vertex v1 of P , invoke Isolate-subpath(t), which isolates
the first subpath in O(log3 n) time, and remove it from P . We repeat this at most k − 1
more times on the remaining subpath, spending O(k log3 n) time. The problem instance is
(t, k)-feasible if and only if the rightmost vertex vn belongs to the last isolated subpath. J

5.3

Uniform edge capacity case

The problem is much simplified if the edges have the same capacity. In particular, we
can compute the critical vertex of a subpath resulting from concatenating two subpaths in
constant time. At each node u of T bottom up, we compute and record the L- and R-critical
vertices of P [vL (u), vR (u)] w.r.t. vR (u)+ and their costs, based on the following lemma.

3
4

See the right figure in Fig. 2.
These costs can be computed in O(log3 n) time as we saw above.

k-sink on dynamic path networks

10

I Lemma 7. [10] For a node u of CC-tree T , let vL (ul ) = vh , vR (ul ) = vj , vL (ur ) = vj+1 ,
[h,j]
[h,j]
[j+1,l]
[j+1,l]
and vR (ur ) = vl , and assume that the critical vertices, cL , cR , cL
, and cR
have
already been computed.
[h,l]
[h,j]
[j+1,l]
(a) The L-critical vertex cL is either cL or cL
.
[h,l]
[h,j]
[j+1,l]
(b) The R-critical vertex cR is either cR or cR
.
[h,j]

For example, to the cost of the L-critical cluster CL of P [vh , vj ], we add the distance
[j+1,l]
cost d(vj , vl )τ , and to the cost of the L-critical cluster CL
of P [vj+1 , vl ] we just add
W [vh , vj ]/c to compute its new cost. The L-critical cluster of the combined path P [vh , vl ] is
whichever is larger.
I Lemma 8. Given a dynamic path network with n vertices and uniform edge capacities, we
can construct search tree T in O(n) time and O(n) space.
Thanks to Lemma 8, Algorithm Isolate-subpath(t, va ) runs in O(log n) time. We thus
have
I Lemma 9. Given a dynamic path network with n vertices and uniform edge capacities,
assume that its search tree, T , is available. Then we can test its (t, k)-feasibility in O(k log n)
time.
Algorithm Find-1sink(vi , vj ) also runs in O(log n) time, which implies
I Lemma 10. Given a dynamic path network with n vertices and uniform edge capacities,
assume that its search tree, T , is available. Then we can find the 1-sink on subpath P [vi , vj ]
in O(log n) time.

6

Optimization

I Lemma 11. [1] If (t, k)-feasibility can be tested in T (t, k) time, then the k-sink can be
found in O(T (t, k) · k log n) time, excluding the preprocessing time.
By Lemma 2 it takes O(n log n) time to construct T with weight and capacity data, and
T (t, k) = O(k log3 n) by Lemma 6. We thus have
I Theorem 12. Given a dynamic path network with n vertices, we can find an optimal
k-sink in O(n log n + k 2 log4 n) time.
Based on Lemmas 8 and 9, Megiddo’s theorem in [13] implies (it also follows Lemma 11)
I Theorem 13. Given a dynamic path network with n vertices and uniform edge capacities,
we can find an optimal k-sink in O(n + k 2 log2 n) time.

6.1

Sorted matrix approach

Let OP T (l, r) denote the evacuation time for the optimal 1-sink on subpath P [vl , vr ]. Define
an n × n matrix A whose entry (i, j) entry is given by

OPT (n − i + 1, j)
if n − i + 1 ≤ j
A[i, j] =
(23)
0
otherwise.
It is clear that matrix A includes OPT (l, r) for every pair of integers l and r such that
1 ≤ l ≤ r ≤ n. There exists a pair of integers l and r such that OPT (l, r) is the evacuation

B. Bhattacharya et al.

11

time for the optimal k-sink on the whole path. Then k-sink location problem can be written
as: “Find the smallest A[i, j] such that the given problem instance is A[i, j]-feasible.”
A matrix is called a sorted matrix if each row and column of it is sorted in the nondecreasing
order. In [4, 5], Frederickson et al. show how to search for such a minimum in a sorted
matrix. The following lemma is implicit in their papers.
I Lemma 14. Suppose that A[i, j] can be computed in f (n) time, and feasibility can be tested
in g(n) time. Then we can solve the k-sink problem in O(nf (n) + g(n) log n) time.
We have f (n) = O(log3 n) by Lemma 5, and g(n) can be O(n log2 n) by scanning path P
from left to right. Lemma 14 thus implies
I Theorem 15. Given a dynamic path network with n vertices and general edge capacities,
we can find an optimal k-sink in O(n log3 n) time.
In the uniform capacity case, we can show that f (n) = O(log n), and g(n) can be O(n)
by scanning the path from left to right. Lemma 14 thus implies
I Theorem 16. Given a dynamic path network with n vertices and uniform edge capacities,
we can find the k-sink in O(n log n) time.

7

Conclusion and discussion

We have shown that on dynamic path networks with n vertices, the k-sink can be found
in O(min{n + k 2 log4 n, n log3 n}) time, which is sub-quadratic. If the edges have the same
capacity, we can solve the k-sink problem in O(min{n + k 2 log2 n, n log n}) time. These
results improve upon the previously best algorithms [1, 10] for all values of k.
References
1

2

3
4
5
6
7

8

Guru Prakash Arumugam, John Augustine, Mordecai J. Golin, Yuya Higashikawa, Naoki
Katoh, and Prashanth Srikanthan. Optimal evacuation flows on dynamic paths with general
edge capacities. arXiv:1606.07208v1, 2016.
Siu-Wing Cheng, Yuya Higashikawa, Naoki Katoh, Guanqun Ni, Bing Su, and Yinfeng Xu.
Minimax regret 1-sink location problem in dynamic path networks. In Proc. Annual Conf.
on Theory and Applications of Models of Computation (T-H.H. Chan, L.C. Lau, and L.
Trevisan, Eds.), Springer-Verlag, volume LNCS 7876, pages 121–132, 2013.
Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars. Computational
Geometry: Algorithms and Applications, Third Edition. Springer Verlag, 2008.
G.N. Frederickson. Optimal algorithms for tree partitioning. In Proc. 2nd ACM-SIAM
Symp. Discrete Algorithms, pages 168–177, 1991.
G.N. Frederickson and D.B. Johnson. Finding kth paths and p-centers by generating and
searching good data structures. J. Algorithms, 4:61–80, 1983.
Ronald L. Graham. An efficient algorithm for determining the convex hull of a finite planar
set. Information processing letters, 1(4):132–133, 1972.
H.W. Hamacher and S.A. Tjandra. Mathematical modelling of evacuation problems: a
state of the art. in: Pedestrian and Evacuation Dynamics, Springer Verlag,, pages 227–
266, 2002.
Yuya Higashikawa. Studies on the space exploration and the sink location under incomplete
information towards applications to evacuation planning. PhD thesis, Kyoto University,
Japan, 2014.

12

k-sink on dynamic path networks

9

Yuya Higashikawa, Mordecai J. Golin, and Naoki Katoh. Minimax regret sink location
problem in dynamic tree networks with uniform capacity. J. of Graph Algorithms and
Applications, 18.4:539–555, 2014.
Yuya Higashikawa, Mordecai J. Golin, and Naoki Katoh. Multiple sink location problems
in dynamic path networks. Theoretical Computer Science, 607:2–15, 2015.
S. Mamada, K. Makino, and S. Fujishige. Optimal sink location problem for dynamic flows
in a tree network. IEICE Trans. Fundamentals, E85-A:1020–1025, 2002.
Satoko Mamada, Takeaki Uno, Kazuhisa Makino, and Satoru Fujishige. An O(n log2 n)
algorithm for a sink location problem in dynamic tree networks. Discrete Applied Mathematics, 154:2387–2401, 2006.
N. Megiddo. Combinatorial optimization with rational objective functions. Math. Oper.
Res., 4:414–424, 1979.
Franco P Preparata and Michael Shamos. Computational geometry: an introduction.
Springer Science & Business Media, 2012.

10
11
12

13
14

