Steiner Point Removal
— Distant Terminals Don’t (Really) Bother

arXiv:1703.08790v1 [cs.DS] 26 Mar 2017

Yun Kuen Cheung
Max Planck Institute for Informatics
Saarland Informatics Campus

Abstract
Given a weighted graph G = (V, E, w) with a set of k terminals T ⊂ V , the Steiner Point
Removal problem seeks for a minor of the graph with vertex set T , such that the distance between every pair of terminals is preserved within a small multiplicative distortion. Kamma,
Krauthgamer and Nguyen (SODA 2014, SICOMP 2015) used a ball-growing algorithm to show
that the distortion is at most O(log5 k) for general graphs.
In this paper, we improve the distortion bound to O(log2 k). The improvement is achieved
based on a known algorithm that constructs terminal-distance exact-preservation minor with
O(k 4 ) (which is independent of |V |) vertices, and also two tail bounds on the sum of independent
exponential random variables, which allow us to show that it is unlikely for a non-terminal being
contracted to a distant terminal.
Keywords. Steiner Point Removal, Graph Sparsification, Vertex Sparsification, Exponential
Random Variables

1

Introduction

Graph Compression/Sparsification generally describes a transformation of a large graph into a
smaller graph that preserves, either exactly or approximately, certain features (e.g., distance, cut,
flow) of the large graph. Its algorithmic value is clear, since the compressed graph can be computed
in a preprocessing step of an algorithm, so as to reduce subsequent running time and memory requirement. Some notable examples are graph spanners, low-stretch spanning tree, distance oracles
and cut/flow/spectral sparsifiers.
In this paper, we study a vertex sparsification problem called the Steiner Point Removal (SPR)
problem. Given a weighted graph G = (V, E, w) with a set of k terminals T ⊂ V , the SPR problem
seeks for a new graph G′ which is a minor of G, such that the vertex set of G′ is T (i.e., no
non-terminal in the minor) and the distance between every pair of terminals is preserved within a
multiplicative distortion κ:
∀ti , tj ∈ T,

distG (ti , tj ) ≤ distG′ (ti , tj ) ≤ κ · distG (ti , tj ).

The target is to minimize κ. The requirement that G′ is a minor of G is crucial since minor operations
preserve certain structural similarities, e.g., planarity, of the input graph G.
SPR problem was first initiated by Gupta [Gup01], where the input graphs are trees. He showed
that for tree graphs, the distortion is at most 8. A matching lower bound was shown by Chan
et al. [CXKR06]. Recently, Kamma, Krauthgamer and Nguyen1 [KKN15] used a randomized ballgrowing algorithm to show the interesting result that the distortion is at most O(log5 k) for general
graphs. It remains a big gap between their upper bound and the best known lower bound (which is
8); narrowing this gap is the motivation of the current work.
1

Since we will refer to this paper for multiple times, for brevity we will refer it as KKN.

1

In this paper, we improve the distortion bound to O(log2 k). Our algorithm starts with a preprocessing step, which uses an algorithm of Krauthgamer, Nguyen and Zondiner [KNZ14] to obtain
a minor of the input graph such that all terminal distances are preserved exactly, while the minor
contains only O(k4 ) vertices. Then we use the randomized ball-growing algorithm of KKN (with
a few adjustments on parameters) on the preprocessed graph. By working with the preprocessed
graph that contains only poly(k) vertices, we can define a class of poly(k) “bad events” such that
avoidances of all these bad events will lead to a minor with O(log2 k) distortion. Finally, we show
that the algorithm of KKN avoids all bad events with high probability.
In KKN’s analysis, they first proved the result for graphs with bounded diameters; for graphs with
any diameters, they needed to provide a separate argument to reduce to low-diameter scenarios. In
contrast, our analysis will work directly — we do not need any assumption on the graph diameters.
Also, our analysis bypasses KKN’s need for analyzing long active subpaths. Hence, our analysis is
more compact than KKN’s analysis.
We note that an important component of our analysis is two tail bounds on the sum of independent
exponential random variables. This allows us to show that it is unlikely for a non-terminal being
contracted to a distant terminal.
Further Related Work. Basu and Gupta [BG08] showed that for outer-planar graphs (planar
graphs with all terminals on the outermost face), SPR problem can be solved with distortion O(1).
When randomization is allowed, Englert et al. [EGK+ 14] showed that for graphs that exclude a fixed
minor, one can construct a randomized minor for SPR problem with O(1) expected distortion. It
remains open on whether similar guarantees can be obtained in the deterministic setting.
A natural generalization of SPR problem is to allow the minor keeping a small number of nonterminals. This generalization was initiated by Krauthgamer, Nguyen and Zondiner [KNZ14], in
which they focused on preserving terminal distances exactly for general graphs, trees, planar graphs
and graphs with bounded treewidth. Cheung, Gramoz and Henzinger [CGH16] extended to the
setting of preserving terminal distances approximately. They proved super-linear (in k) lower bounds
on the number of non-terminals required in the minor for achieving distortion less than 8. They also
extended the technique for proving the lower bounds to establish the following result related to SPR
problem: if the tight bound of SPR problem is super-constant (in k), then allowing the freedom of
keeping O(k) non-terminals in the minor would not improve the distortion bound to a constant.
In many other settings, problems that concern preserving features which involve only a small
number of terminals are becoming more popular. Terminal distance oracles were studied by Roditty,
Thorup and Zwick [RTZ05]. They showed that there exists oracle using only O(τ · |V | · k1/τ ) space
which answers the distance between a terminal and any other vertex with stretch at most (2τ − 1).
Elkin, Filtser and Neiman [EFN15a] improved the space requirement to O(τ · k1/τ + |V |), with a
slightly worse stretch of at most (4τ − 1). Recently, Elkin, Filtser and Neiman [EFN15b] considered
the problem of embedding a finite metric (e.g., graph metric) into normed metric while preserving
all distances from any terminal to all other vertices approximately. They showed that the distortion
depends only on k, but not on |V |. For cut/flow sparsifiers, we refer readers to [LM10, Moi09,
CLLM10, MM16, Chu12, KR13, AGK14] for more details.

2

Main Theorem and Preliminary

For any graph G, G′ is a minor of G if G′ can be attained from G by a sequence of edge contractions,
edge deletions and vertex deletions.
Given a weighted connected graph G = (V, E, w) with a set of k terminals T = {t1 , t2 , · · · , tk } ⊂
V , the Steiner Point Removal (SPR) problem seeks to construct a minor G′ = (T, E ′ , w′ ) of the graph
G, such that for any ti , tj ∈ T , distG (ti , tj ) ≤ distG′ (ti , tj ) ≤ κ · distG (ti , tj ) with the minimum
possible distortion κ. Our main result is that for general graphs, the distortion is at most O(log2 k):

2

Theorem 1. For any weighted graph with k terminals, the Steiner Point Removal problem can be
solved with distortion at most O(log2 k). More precisely, when k is sufficiently large, the distortion
is at most (2 × 108 ) · log2 k.
We note that our analysis is rather loose on the constant factor, so there should be plenty of room
for reducing the constant 2 × 108 . But we have not yet done so for a cleaner analysis.
Notations. By using a consistent tie-breaking rule (e.g., edge weight perturbation), we can assume
that there is a unique shortest path between any two vertices in G. We let SP(vi , vj ) denote the
unique directed shortest path in G from vertex vi to vertex vj .
For any V ′ ⊂ V , let G[V ′ ] be the subgraph of G induced by V ′ . If t ∈ V ′ , let BG[V ′ ] (t, R) := {v ∈
V | distG[V ′ ] (t, v) ≤ R}.
′

Terminal-centered Minors. As KKN showed, SPR problem is equivalent to finding the terminaldist (t ,t )
centered minor of V that minimizes the quantity maxti ,tj ∈T distGG′(tii,tjj) . A terminal-centered minor of
G = (V, E, w) is specified by a terminal-centered partition of V into exactly k sets, which satisfies (a)
each set contains exactly one of the terminals, and thus the set containing tj can be naturally denoted
by Vj ≡ Vtj ; (b) for each j ∈ [k], the induced graph G[Vj ] is connected. Then the terminal centered
minor G′ = (T, E ′ , w′ ) is formed by contracting the vertices in each Vj into a single vertex, which is
identified with tj . For any ti , tj ∈ T , (ti , tj ) ∈ E ′ if and only if there exists an edge (u, v) ∈ E such
that one of its endpoints belongs to Vi and the other endpoint belongs to Vj . For each (ti , tj ) ∈ E ′ ,
its weight w′ ((ti , tj )) := distG (ti , tj ).
Exponential Random Variables. An exponential random variable (ERV) with mean µ is the
probability distribution with density function f (x) = µ−1 · e−x/µ on x ≥ 0, and f (x) = 0 on x < 0.
We denote the distribution by Exp(µ). ERV enjoys two important properties: (a) closeness under
scaling: the random variable Exp(µ) follows the same distribution as the random variable µ · Exp(1),
and (b) memoryless property: for any a, b ≥ 0, P [ Exp(µ) > a + b | Exp(µ) > a ] = P [ Exp(µ) > b ].
We will also use the following inequality: for any κ ≥ 0, P [ Exp(µ) ≤ κµ ] ≤ κ.

3

Algorithm and Technical Overview

Algorithm 1: The Ball-Growing Algorithm that produces a terminal-centered partition.
INPUT: A weighted graph G = (V, E, w), and a set of terminals T = {t1 , · · · , tk } ⊂ V .
OUTPUT: A terminal-centered partition {V1 , · · · , Vk } of V .
1 Set r ← 1 + δ/ log k, where δ = 1/2.
δ
2 Set D ← 100 log k · minv∈V \T Dv .
3 For each j ∈ [k], set Vj ← {tj }, and set Rj ← 0.
// Rj ≡ Rtj .


4

5

6

Set V⊥ ← V \ ∪kj=1 Vj .

// V⊥ keeps track of the set of unassigned vertices.

Set ℓ ← 0.


k
while ∪j=1 Vj 6= V do

//We call this round by Round-(D · r ℓ );
forall j ∈ [k] do
Choose independently at random qjℓ ∼ Exp(D · r ℓ ).
Set Rj ← Rj + qjℓ .
Set Vj ← Vj ∪ BG[V⊥ ∪Vj ] (tj , Rj ).


Set V⊥ ← V \ ∪kj=1 Vj .

7

Set ℓ ← ℓ + 1.
return {V1 , · · · , Vk }.

3

3.1

Algorithm

Our first step is to use an algorithm of Krauthgamer et al. [KNZ14, Theorem 2.1] to obtain a minor
of G, denoted by G∗ , such that all terminal distances are preserved exactly, and G∗ contains only
O(k4 ) non-terminals — note that this number does not depend on |V | and is in poly(k). In the rest
of this paper, we identify G∗ as G.
Next, we use the randomized ball-growing algorithm of KKN (with a few adjustments on parameters, see Algorithm 1) on the graph G to construct a terminal-centered partition. In the course of
the algorithm, a vertex v is assigned to terminal j if v ∈ Vj ; we say a vertex v is assigned if it is
assigned to some terminal, and we say v is unassigned otherwise. As already noted in Algorithm 1,
we always refer to a round by Round-µ, where µ is the mean of the ERV generated in that round.
We abuse notation a bit: for any positive real number z, by Round-z we refers to the first Round-µ
in the algorithm such that µ ≥ z; note that µ ≤ 23 z.

3.2

Families of Bad Events

We define the following poly(k) “bad events” (C1 > 1 and C2 are constants to be determined):
(A) For each non-terminal v in G, let its distance to the its nearest terminal be Dv , and let t be a
far denote the “bad event”
terminal which is far from v; precisely, distG (v, t) ≥ C1 · Dv . Let Ev,t
that v is assigned to t.
(B) For each non-terminal v in G, let Evearly denote the “bad event” that v is assigned before the
end of Round-(C2 Dv δ/ log k).
We will define another family of “bad events”, but before doing so, we need the following setups,
which are modified from KKN.2
For each pair of terminals ti , tj , let the vertices on SP(ti , tj ), when listed in the direction from ti
to tj , be v0 = ti , v1 , v2 , · · · , vL−1 , vL = tj . The vertices v1 , · · · , vL−1 are partitioned into sets, while
each set contains consecutive vertices of SP(ti , tj ). For each such set Q = {va , va+1 , · · · , vb }, we say
its internal length is the distance between va and vb , while its external length is the distance between
va−1 and vb+1 . (It is possible to have va = vb ; in this case, the internal length is 0.)
We require each Q in the partition satisfies the following requirement: Q contains a non-terminal
v such that the internal length of Q is at most C2 Dv δ/(5 log k) but the external length of Q is at least
C2 Dv δ/(5 log k). Such partition can be obtained by a simple greedy sweeping along the directed path
SP(ti , tj ), where we always take v ≡ v(Q) to be the first vertex of each set Q. The algorithm that
constructs G∗ guarantees that there are at most O(k2 ) vertices on SP(ti , tj ), and thus the cardinality
of the partition is bounded by the same number. We denote the partition by Q(ti , tj ).

For each Q = {va , va+1 , · · · , vb } ∈ Q(ti , tj ), before the execution of the algorithm, all vertices in
Q are active. We will then iteratively determine how these vertices are turned to inactive. On the
course of the algorithm, we say that a terminal t reaches Q at a moment when some active vertex
in Q is assigned to Vt ; when this happens, we let
qmin := min {q | vq is active just before t reaches Q, and it is assigned to t after t reaches Q} ;

we define qmax analogously. Then all vertices { vq | q ∈ [qmin , qmax ] } are turned to inactive. Also, we
let Term-Detour(qmin , qmax ) := SP(vqmin , t) + SP(t, vqmax ) + (vqmax , vqmax +1 ) to be the terminal-detour
created by this t’s reaching on Q. To avoid confusion, we make the following remark: when a vertex
is assigned, it must be inactive, but it is possible for a vertex to be inactive but remains unassigned.
Now we are ready to define the last family of “bad events”: (C3 is a constant to be determined)
many
(C) Let EQ
denote the “bad event” that at least C3 log k distinct terminals reach Q.
2

Some of our terminologies are same as those used by KKN, but they have slightly different definitions/meanings.

4

For the convenience of forthcoming discussion, whenever there are two consecutive terminaldetours Term-Detour(q1 , q2 ) and Term-Detour(q2 + 1, q3 ) which involve the same terminal t, then the
two terminal-detours are merged into a new one, which is SP(vq1 , t) + SP(t, vq3 ) + (vq3 , vq3 +1 ). By
repeating this merging process until no consecutive terminal-detours involve the same terminal, we
are sure that for any two consecutive terminal-detours Term-Detour(q1 , q2 ) and Term-Detour(q2 +
1, q3 ), the two vertices vq2 , vq2 +1 are assigned to two different terminals, and the two terminals are
adjacent in the graph G′ (due to the edge (vq2 , vq2 +1 ) ∈ E).

3.3

Key Lemmas and Proof of Theorem 1

By suitably choosing the constants C1 , C2 , C3 , we can show that the above poly(k) bad events each
occurs with probability at most O(1/kβ ) for some sufficiently large β. Then by a simple union
bound, we can show that with probability 1 − O(1/k), all these bad events are avoided. As we will
show in the proof of Theorem 1, the distortion of any terminal-centered minor that avoids all bad
events is at most 1 + 40C3C(C21 +1) log2 k = O(log2 k).
 far 
Lemma 2. Set C1 = 5400. Then P Ev,t
≤ 3/k6 .
i
h
≤ 2/k5 .
Lemma 3. Set C2 = 1/27. Then P Evearly
h
i
Lemma 4. Set C3 = 30. Then P EPmany | ∀v, Evearly does not occur
≤ 1/k5 .

The proofs of the above three lemmas will be provided in Section 4. We follow KKN’s method
closely to prove Lemma 4. To prove Lamma 2 and Lemma 3, we use the following two lemmas about
the tail bounds of sum of independent ERV; their proofs will be presented in Section 5. We note that
sum of independent ERV with general distinct means follows hypoexponential distribution, for which
complicated tail bounds are known, but none of them is simple enough for us to use directly. Thus,
we derive simpler tail bounds ourselves. This is done by a proper translation to finding tail bound
of sum of independent ERV with equal means, which is known to follow an Erlang distribution and
admits a simpler tail bound.

Lemma 5. For any positive integer m, let E1 , E2 , E3 , · · · , Em be m independent exponential random
variables, each has mean at least A > 0 (the means can be distinct). Then for any κ ≤ 1/4,
#
" m
X
4
· (3κ)m ≤ (3κ)m .
Ei ≤ κ · Am
≤ √
P
3 2πm
i=1

Lemma 6. Let R1 , R2 , R3 , · · · be a sequence of independent exponential random variables with means
A, A/r, A/r 2 , · · · , where A > 0, and r = 1 + δ/ log k with δ ≤ 1/2 and k ≥ 3. For any sufficiently
large k, and for any constant M ≥ 18,
#
" ∞
X
2
A log k
≤ M/(12δ)+3 .
Ri ≥ M ·
P
δ
k
i=1
P
2A log k
Ar
. In other words, the
Note that in Lemma 6, the expected value of ∞
i=1 Ri is r−1 ≤
δ
lemma states that the probability for the sum exceeding M times of its expected value is at most
k−Θδ (M ) .
The intuition behind proof of Lemma 2 is: when t is far away from v but there are some other
terminals near v, it looks highly likely that v is assigned (to the one of the near terminals) well
before t grows its ball radius large enough to come close to v. We will verify this natural intuition
rigorously. Formally, we design a random variable to track how v is being approached by the sets in
the terminal-centered partition; the random variable has initial value zero, and its value is at least
Dv when v is assigned. By showing that the random variable dominates some sum of independent
ERV, we prove that with high probability, v is assigned early enough (using Lemma 5) while Rt is
still below C1 · Dv (using Lemma 6).
Lemma 3 is almost a direct corollary of Lemma 6.
5

3.4

Proof of Theorem 1

We finish this technical overview by proving Theorem 1 using Lemmas 2—4.
Let the terminals be t1 , · · · , tk and let V1 , · · · , Vk be a terminal-centered partition which avoids
all the above bad events — such parition exists for any sufficiently large k, since by Lemmas 2—4,
the probability that any of the bad events occur is at most
 
 
3
k
1
2
1
5
4
2
O(k ) · 6 + O(k ) · 5 +
· O(k ) · 5 = O
≪ 1.
2
k
k
k
k
For each pair of terminals ti , tj , the length of SP(ti , tj ) is bounded below by half of the external
lengths of all sets in Q(ti , tj ) (since some of the edges on SP(ti , tj ) are double counted, we need the
factor of half), i.e.,
X C2 Dv(Q) δ
1
.
distG (ti , tj ) ≥
2
5 log k
Q∈Q(ti ,tj )

Recall that the vertices on SP(ti , tj ), when listed in the direction from ti to tj , are
v0 = ti , v1 , v2 , · · · , vL−1 , vL = tj . For each Q = {va , va+1 , · · · , vb } ∈ Q(ti , tj ), note that conditioning
many
on the avoidance of EQ
, there is a directed path from va to vb+1 in G which is composed of at
most C3 log k terminal-detours; we denote this directed path by PQ .
Concatenating (ti , v1 ) with all PQ , where Q runs over Q(ti , tj ), forms a directed path from ti to
tj in G, denoted by Detour(ti , tj ).3 Due to the terminal-detour-merging process described at the
end of Section 3.2, every two consecutive terminal-detours involve two different terminals, and the
two terminals are adjacent in G′ . Thus Detour(ti , tj ), when contracted according to the underlying
terminal-center partition, forms a path from ti to tj in G′ . This path in G′ has length bounded above
by the length of Detour(ti , tj ) in G, due to the definition of w′ in G′ = (T, E ′ , w′ ). Conditioned on
the avoidances of all the bad events, the length of Detour(ti , tj ) is upper bounded by
X 

2(C1 + 1) · Dv(Q) · (C3 log k),
distG (ti , tj ) +
Q∈Q(ti ,tj )

and hence the distortion is bounded above by


P
40C3 (C1 + 1)
Q∈Q(ti ,tj ) 2(C1 + 1) · Dv(Q) · (C3 log k)
log2 k,
≤
1
+
1+
P
C
D
δ
2 v(Q)
1
C2
2

Q∈Q(ti ,tj )

5 log k

which is at most (2 × 108 ) · log2 k.

4
4.1

Analysis
Proof of Lemma 2

Setup. Let t∗ denote the nearest terminal to v in graph G, and let P denote the directed shortest
path from t∗ to v. By definition, the length of P is Dv . We use the variable u∗ to track the vertex
in P which is assigned and furthest away from t∗ . At the beginning, the only assigned vertex in P
is t∗ , thus u∗ = t∗ ; when u∗ = v, v is assigned.
Let tq be the variable tracking the terminal which u∗ is assigned to. Let dq denote the distance
between tq and u∗ in G[Vq ], then consider the following random variable:
d∗ := distG (t∗ , u∗ ) + Rq − dq .
3
Note that this directed path may not be simple, i.e., it may traverse a terminal or an edge for multiple times. This
does not matter for us, since the purpose for introducing this path is to give an over-estimate of distG′ (ti , tj ).

6

Note that d∗ never decreases, and d∗ ≥ Dv if and only if v is assigned.
Step 1. In this step, we show that after Round-T , where T = 200Dv δ/ log k, d∗ ≥ Dv occurs with
probability at least 1 − 1/k6 .

There are two scenarios in which d∗ increases: (a) when Rq increases, while u∗ might remain
unchanged or not; or (b) when some vertex on P which is further away from t∗ than u∗ is assigned
to some terminal tq′ , where q ′ 6= q.
In scenario (a), d∗ increases by exactly the amount of the ERV that raises Rq .

In scenario (b), since u∗ is changed, to avoid confusion, we use uold
to denote the value of u∗
∗
′
old
before the change. Let u denote the vertex on the directed path SP(u∗ , v) which is newly assigned
to tq′ and nearest to tq′ in G[Vq′ ]. Due to the memoryless property of ERV, the increment of d∗ is
′
the distance between uold
∗ and u , plus a random variable that follows an exponential distribution
with the same mean as the ERV that raises Rq′ .
On the other hand, observe that in each round, at least one of the two scenarios occurs (and for
(b), it might occur multiple times in one round). Combined with the last paragraph,
,
Pmafter Round-T
i−1
the value of d∗ is lower bounded by the sum of independent ERV of the form i=1 Exp(T /r ),
where m = ⌈(log k)/δ⌉. Note that the mean of T /r m−1 ≥ T /3 = 200Dv δ/(3 log k). Thus, by Lemma
5,
#
" m


X
9 log k/δ
200D
δ
1
3
v
i−1
·
·m
≤
≤ 6.
Exp(T /r ) <
P [ d∗ < Dv ] ≤ P
200 3 log k
200
k
i=1

far to occur, a
Step 2. Conditioned on the highly probable event analyzed in Step 1, for the event Ev,t
necessary (but not sufficient) condition is: the radius Rt grows beyond C1 Dv = 5400Dv by the end
of Round-T . By Lemma 6, for sufficiently large k, this occurs with probability at most
#
" ∞


X
3T  i
2
300Dv δ log k
≤ 6.
Exp
·
P
r
≥ 18 ·
2
log k
δ
k
i=0

 far 
Thus, we can conclude that P Ev,t
≤ 1/k 6 + 2/k6 = 3/k 6 .

4.2

Proof of Lemma 3

Lemma 3 can be proved almost directly from Lemma 6. For the event Evearly to occur, a necessary
(but not sufficient) condition is: there exists a terminal t with radius Rt grows beyond Dv by the
end of Round-(C2 Dv δ/ log k). By Lemma 6, this occurs with probability at most
#
" ∞


X
X
3C2 Dv δ  i
r
≥ Dv
Exp
P
2 log k
i=0
t∈T
" ∞
#


X
3C2 Dv δ  i
2
3C2 Dv δ log k
2
2
Exp
= k · P
≤ k · 6 = 5.
·
·
r
≥
2 log k
3C2 2 log k
δ
k
k
i=0

4.3

Proof of Lemma 4

The idea behind the proof of Lemma 4 follows closely from [KKN15, Sections 3.1.1 and 3.1.2], but
there are some small differences in the details. For completeness, we provide a self-contained proof.
Let Q = {va , va+1 , · · · , vb }. On the course of the algorithm, a maximal active subset of Q is a
subset Q′ = {vq , vq+1 , · · · , vr } ⊂ Q such that (a) all vertices in Q′ are active; (b) vq−1 is inactive or
q = a; and (c) vr+1 is inactive or r = b. We let ZQ count the number of maximal active subsets of Q
on the course of the algorithm. At the beginning, the only maximal active subset of Q is Q itself, so
7

ZQ = 1. Whenever ZQ = 0, we obtain a collection of terminal-detours which are later used to form
PQ , which we have defined in the proof of Theorem 1.
For each ℓ ∈ N, let tℓ denote the ℓ-th terminal that reaches Q, then let Yℓ denote the indicator
random variable that upon the reach of tℓ on Q, ZQ strictly decreases. We note that when Yℓ = 0,
by inspecting the process of how vertices are turned inactive (see Section 3.2), it is not hard to see
that ZQ increases by at most 1, and furthermore, it must be the case that some but not all vertices
in one maximal active subset get assigned to tℓ .4
Note that for any vertex v ∈ Q, Dv ≥ Dv(Q) · (1 − C2 δ/5 log k) ≥ 99Dv(Q) /100. Conditioned on
the avoidances of all Evearly , a vertex in Q can be assigned only after Round-(99C2 Dv(Q) δ/(100 log k)).
Also, note that the internal length of each maximal active subset is at most the internal length of
Q, which is at most C2 Dv(Q) δ/(5 log k). Hence, by the memoryless property of ERV, we have
P [ Yℓ = 0 ] ≤ P



Exp



99C2 Du(Q) δ
100 log k



C2 Du(Q) δ
≤
5 log k



≤

20
.
99

PN
Next, for an integer N to be determined, let Y N :=
that when Y N > N/2,
ℓ=1 Yℓ . Note 
then ZQ = 0. Thus, P [ ZQ ≥ 1 after Q being reached for N times ] ≤ P Y N ≤ N/2 , which is
bounded above by P [ Binom(N, 79/99) ≤ N/2 ].5 By the Hoeffding’s inequality,




N
79
2
≤
≤ e−2(79/99−1/2) N .
P Binom N,
99
2
By choosing N = 30 log k, the RHS of the above inequality is at most 1/k5 .

5

Tail Bounds of Sum of Exponential Random Variables

In this section, we provide proofs of Lemma 5 and Lemma 6.
Proof of Lemma 5: First, since ERV enjoys the property of closeness under scaling, it suffices to
prove the lemma for A = 1.
It is well-known that sum of independent ERV with equal means follows an Erlang distribution.
Thus,
" m
#
" m
#
X
X
γ(m, κm)
P
Ei ≤ κm
≤ P
Exp(1) ≤ κm
= P [ Erlang(m, 1) ≤ κm ] =
,
(m − 1)!
i=1

i=1

where γ(·, ·) is the lower incomplete Gamma function, which admits a power series expansion given
below [Par]. Together with the assumption κ ≤ 1/4, it yields
∞
(κm)ℓ
e−κm (κm)m X
γ(m, κm)
=
·
(m − 1)!
(m − 1)!
m(m + 1) · · · (m + ℓ)
ℓ=0


−κm
m
1
1
4e−κm (κm)m
e
(κm)
· 1+ +
+ ··· =
.
≤
m!
4 16
3 · m!
4

An elaborative explaination: (1) If vqmin and vqmax belong two different maximal active subsets (denoted as S1 , S2 ),
then all maximal active subsets strictly between S1 , S2 are turned to inactive, while S1 , S2 might shrink to a smaller
maximal active subset or be turned to fully inactive. When either S1 , S2 is turned to fully inactive, ZQ must drop by
at least 1. Thus, whenever ZQ does not strictly decrease, some vertices in either S1 , S2 remain unassigned. (2) If vqmin
and vqmax belong to the same maximal active subset S1 , then it’s clear that ZQ can increase by at most 1, and when
ZQ strictly increases, some vertices in S1 remain unassigned.
P
5
Binom(N, p) is the Binomial distribution followed by N
ℓ=1 Xℓ , where each Xℓ is an independent random variable
that takes value 1 with probability p, and it takes value 0 otherwise.

8

By the Stirling’s approximation, m! ≥

√
2πm · (m/e)m , thus we can complete the proof:

4e−κm (κm)m
4
4
≤ √
· [e1−κ κ]m ≤ √
· (3κ)m .
3 · m!
3 2πm
3 2πm

To prove Lemma 6, we need the following intermediate lemma.
Lemma 7. Let E1 , E2 , E3 , · · · , Em be m independent exponential random variables, each has mean
at most A > 0. Then for any sufficiently large m, and for any C ≥ 6,
#
" m
X
1
1
2
√
· Cm/2 ≤ Cm/2 .
Ei ≥ C · Am
≤
P
e
(C − 1) · 2πm e
i=1
Proof: Again, it suffices to prove the lemma for A = 1. Note that
#
#
" m
" m
X
X
Γ(m, Cm)
Exp(1) ≥ Cm
= P [ Erlang(m, 1) ≥ Cm ] =
Ei ≥ Cm
≤ P
P
,
(m − 1)!
i=1

i=1

where Γ(·, ·) is the upper incomplete Gamma function. Tricomi [Tri50] (see also [Gau98]) showed
that for any constant C ≥ 6,
Γ(m, Cm) =
By the Stirling’s approximation, m! ≥

e−Cm (Cm)m
· (1 + om (1)).
Cm − m + 1

√
2πm · (m/e)m . Thus, for any sufficiently large m,

Γ(m, Cm)
2e−Cm (Cm)m
2
√
≤
≤
· [e1−C C]m .
(m − 1)!
(C − 1) · m!
(C − 1) · 2πm
When C ≥ 6, e1−C C ≤ e−C/2 , and we are done.
Proof of Lemma 6:
For j ∈ N, let

Again, it suffices to prove the lemma for A = 1. Let m := ⌊(log k)/δ⌋ ≥

Ej denote the following event:
Due to the equality
hold. Hence,

P∞

j
j=1 (1 + j)/2

P

"

∞
X
i=1

jm
X

r=(j−1)m+1

= 3, if

P∞

i=1 Ri

M log k
Ri ≥
δ

Rr ≥
≥

#

≤

1
2j−1

M log k
,
δ
∞
X
j=1

·



1 j
+
2 2



·

M log k
.
3δ

then at least one of E1 , E2 , · · · must

P [ Ej ] .



Next, observe that E R(j−1)m+1 ≤ (1 + 1/m)−(j−1)m ≤ 1/2j−1 . Hence, by Lemma 7,
P [ Ej ] ≤ 1



exp



1 j
+
2 2



·

M log k 1
·
3δ
2



1



= k−(1+j)M/(12δ) ≤

1
1
·
,
kM/(12δ) k3j

and thus
P

"

∞
X
i=1

M log k
Ri ≥
δ

#

≤

kM/(12δ)+3

9

log k
2δ .

1
1
1 + 3 + 6 + ···
k
k



≤

2
kM/(12δ)+3

.

6

Discussion

If we are allowed to use only one brief sentence to summarize how the O(log2 k) distortion is arrived,
it is: the vertices in a short segment of length ℓ = Θ(Dv / log k) might be assigned to at most Θ(log k)
distinct terminals, each is of distance of at most Θ(ℓ log k) = Θ(Dv ) away from the segment.
In our (failed) attempts to shave further log, one idea is to grow the ball radius more aggressively
by setting r = 1 + Θ(1) instead of r = 1 + Θ(log−1 k). To motivate this idea, see in the proof of
Lemma 2 and by Lemma 3, a vertex v is assigned in Round-[Θ(Dv / log k)]. This forced us to set ℓ
to
be of the same magnitude for establishing Lemma 4. By setting r = 1 + Θ(1), if the sum of ERV
P∞
i
i=1 Exp(Θ(Dv )/r ) were well concentrated around its mean, we could hope that v is assigned in
Round Θ(Dv ) and then we could set ℓ = Θ(Dv ). Unfortunately, such sum of ERV is actually not
sufficiently well concentrated.
Another idea is to replace the exponential random variables, which have unbounded support,
with some other random variables, say those with bounded supports. Then Chernoff-like tail bounds
might be plausible. However, memoryless property is lost. While I have my personal intuition that
this approach might provide better results, the loss of memoryless property makes devising a rigorous
proof seem technically challenging.
This draws a parallel with the early development of queueing theory. Its fundamental results
mostly apply to models in which the involved random variables are ERV — the reason is not because ERV is the most appropriate probability distribution that captures the reality, but because
the memoryless property of ERV makes analyses more admissible. After more than a century of development, rich analytical insights and tools have been developed to handle more general queueing
models; it might be interesting to investigate whether such insights and tools can help us to “grow
balls for the better”.

References
[AGK14]

Alexandr Andoni, Anupam Gupta, and Robert Krauthgamer.
approximate flow sparsifiers. In SODA 2014, pages 279–293, 2014.

Towards (1 + ǫ)-

[BG08]

Amitabh Basu and Anupam Gupta. Steiner point removal in graph metrics. 2008.
http://www.ams.jhu.edu/∼abasu9/papers/SPR.pdf.

[CGH16]

Yun Kuen Cheung, Gramoz Goranci, and Monika Henzinger. Graph minors for preserving
terminal distances approximately - lower and upper bounds. In ICALP 2016, pages 131:1–
131:14, 2016.

[Chu12]

Julia Chuzhoy. On vertex sparsifiers with steiner nodes. In STOC 2012, pages 673–688,
2012.

[CLLM10] Moses Charikar, Tom Leighton, Shi Li, and Ankur Moitra. Vertex sparsifiers and abstract
rounding algorithms. In FOCS 2010, pages 265–274, 2010.
[CXKR06] Hubert T.-H. Chan, Donglin Xia, Goran Konjevod, and Andréa W. Richa. A tight lower
bound for the steiner point removal problem on trees. In APPROX 2006, pages 70–81,
2006.
[EFN15a] Michael Elkin, Arnold Filtser, and Ofer Neiman. Prioritized metric structures and embedding. In STOC 2015, pages 489–498, 2015.
[EFN15b] Michael Elkin, Arnold Filtser, and Ofer Neiman. Terminal embeddings. In APPROX
2015, pages 242–264, 2015.

10

[EGK+ 14] Matthias Englert, Anupam Gupta, Robert Krauthgamer, Harald Räcke, Inbal TalgamCohen, and Kunal Talwar. Vertex sparsifiers: New results from old techniques. SIAM J.
Computing, 43(4):1239–1262, 2014.
[Gau98]

Walter Gautschi. The incomplete gamma functions since Tricomi. In Tricomi’s Ideas
and Contemporary Applied Mathematics, Atti dei Convegni Lincei, n. 147, Accademia
Nazionale dei Lincei, pages 203–237, 1998.

[Gup01]

Anupam Gupta. Steiner points in tree metrics don’t (really) help. In SODA 2001, pages
220–227, 2001.

[KKN15]

Lior Kamma, Robert Krauthgamer, and Huy L. Nguyen. Cutting corners cheaply, or
how to remove steiner points. SIAM J. Computing, 44(4):975–995, 2015.

[KNZ14]

Robert Krauthgamer, Huy L. Nguyen, and Tamar Zondiner. Preserving terminal distances using minors. SIAM J. Discrete Math., 28(1):127–141, 2014.

[KR13]

Robert Krauthgamer and Inbal Rika. Mimicking networks and succinct representations
of terminal cuts. In SODA 2013, pages 1789–1799, 2013.

[LM10]

Tom Leighton and Ankur Moitra. Some results on greedy embeddings in metric spaces.
Discrete & Computational Geometry, 44(3):686–705, 2010.

[MM16]

Konstantin Makarychev and Yury Makarychev. Metric extension operators, vertex sparsifiers and lipschitz extendability. Israel Journal of Mathematics, 212(2):913–959, 2016.

[Moi09]

Ankur Moitra. Approximation algorithms for multicommodity-type problems with guarantees independent of the graph size. In FOCS 2009, pages 3–12, 2009.

[Par]

Richard B. Paris. Incomplete gamma and related functions. http://dlmf.nist.gov/8.

[RTZ05]

Liam Roditty, Mikkel Thorup, and Uri Zwick. Deterministic constructions of approximate
distance oracles and spanners. In ICALP 2005, pages 261–272, 2005.

[Tri50]

F. Tricomi. Asymptotische eigenschaften der unvollständigen gammafunktion. Mathematische Zeitschrift, 53:136–148, 1950.

11

