Efficient Algorithms for Constructing Very Sparse Spanners and
Emulators∗

arXiv:1607.08337v2 [] 6 Feb 2017

Michael Elkin†1 and Ofer Neiman‡1
1

Department of Computer Science, Ben-Gurion University of the Negev, Beer-Sheva, Israel.
Email: {elkinm,neimano}@cs.bgu.ac.il

Abstract
Miller et al. [MPVX15] devised a distributed1 algorithm in the CONGEST model, that given
a parameter k = 1, 2, . . ., constructs an O(k)-spanner of an input unweighted n-vertex graph with
O(n1+1/k ) expected edges in O(k) rounds of communication. In this paper we improve the result of
[MPVX15], by showing a k-round distributed algorithm in the same model, that constructs a (2k − 1)spanner with O(n1+1/k /ǫ) edges, with probability 1 − ǫ, for any ǫ > 0. Moreover, when k = ω(log n),
our algorithm produces (still in k rounds) ultra-sparse spanners, i.e., spanners of size n(1 + o(1)), with
probability 1 − o(1). To our knowledge, this is the first distributed algorithm in the CONGEST or in
the PRAM models that constructs spanners or skeletons (i.e., connected spanning subgraphs) that sparse.
Our algorithm can also be implemented in linear time in the standard centralized model, and for large k, it
provides spanners that are sparser than any other spanner given by a known (near-)linear time algorithm.
We also devise improved bounds (and algorithms realizing these bounds) for (1 + ǫ, β)-spanners and
emulators. In particular, we show that for any unweighted n-vertex graph and any ǫ > 0, there exists a
n log log n
)
)-emulator with O(n) edges. All previous constructions of (1 + ǫ, β)-spanners
(1 + ǫ, ( log log
ǫ
and emulators employ a superlinear number of edges, for all choices of parameters.
Finally, we provide some applications of our results to approximate shortest paths’ computation in
unweighted graphs.

1 Introduction
1.1 Setting, Definitions
We consider unweighted undirected n-vertex graphs G = (V, E). For a parameter α ≥ 1, a subgraph
H = (V, E ′ ), E ′ ⊆ E, is called an α-spanner of G, if for every pair u, v ∈ V of vertices, we have
dH (u, v) ≤ α · dG (u, v). Here dG (u, v) (respectively, dH (u, v)) stands for the distance between u and v
in G (resp., in H). The parameter α is called the stretch of the spanner H. More generally, if for a pair of
parameters α ≥ 1, β ≥ 0, for every pair u, v ∈ V of vertices, it holds that dH (u, v) ≤ α · dG (u, v) + β,
then the subgraph H is said to be an (α, β)-spanner of G. Particularly important is the case α = 1 + ǫ, for
∗

A preliminary version [EN17] of this paper appeared in SODA’17.
This research was supported by the ISF grant No. (724/15).
‡
Supported in part by ISF grant No. (523/12) and by BSF grant No. 2015813.
1
They actually showed a PRAM algorithm. The distributed algorithm with these properties is implicit in [MPVX15].
†

1

some small ǫ > 0. Such spanners are called near-additive. If H = (V, E ′′ , ω), where ω : E ′′ → R+ , is
not a subgraph of G, but nevertheless satisfies that for every pair u, v ∈ V of original vertices, dG (u, v) ≤
dH (u, v) ≤ (1 + ǫ)dG (u, v) + β, then H is called a near-additive β-emulator of G, or a (1 + ǫ, β)-emulator
of G.
Graph spanners have been introduced in [Awe85, PS89, PU89a], and have been intensively studied ever
since [ADD+ 93, ABCP93, Coh99, ACIM99, DHZ00, BS03, Elk04, Elk07a, EZ06, TZ06, Woo06, Elk07b,
Pet09, DGPV08, Pet10, BW15, MPVX15, AB16]. They were found useful for computing approximately
shortest paths [ABCP93, Coh99, Elk04, EZ06], routing [PU89b], distance oracles and labeling schemes
[Pel99, TZ05, EP15], synchronization [Awe85], and in other applications.
The simplest and most basic algorithm for computing a multiplicative α-spanner, for a parameter α ≥ 1,
is the greedy algorithm [ADD+ 93]. The algorithm starts with an empty spanner, and examines the edges of
the input graph G = (V, E) one after another. It tests if there is a path in H of length at most α between
the endpoints u and v of e. If it is not the case, the edge is inserted into the spanner. Otherwise the edge is
dropped.
It is obvious that the algorithm produces an α-spanner H. Moreover, the spanner H has no cycles of
length α + 1 or less, i.e., the girth of H, denoted g(H), satisfies g(H) ≥ α + 2. Denote m = m(n, g) the
maximum number of edges that a girth-g n-vertex graph may contain. It follows that |H| ≤ m(n, α + 2).
1+ 2
The function m(n, g) is known to be at most n g−2 , when g ≤ 2 log2 n, and for larger g (i.e., for m ≤ 2n),
it is given by m(n, g) ≤ n(1 + (1 + o(1)) ln(p+1)
), where p = m − n, [AHL02, BR10]. These bounds are
g
called “Moore’s bounds for irregular graphs”, or shortly, (generalized) Moore’s bounds.
Any construction of multiplicative α-spanners for n-vertex graphs with at most m′ (n, α + 2) edges
implies an upper bound m(n, α + 2) ≤ m′ (n, α + 2) for the function m(n, g). (As running the construction
on the extremal girth-(α + 2) n-vertex graph can eliminate no edge.) Hence the greedy algorithm produces
multiplicative spanners with optimal tradeoff between stretch and number of edges. (See also [FS16].)
However, the greedy algorithm is problematic from algorithmic perspective. In the centralized model of
computation, the best-known implementation of it [RZ04] requires O(α · n2+1/α ) time. Moreover, the
greedy algorithm is inherently sequential, and as such, it is generally hard2 to implement it in distributed
and parallel models of computation.
In the distributed model [Pel00] we have processors residing in vertices of the graph. The processors
communicate with their graph neighbors in synchronous rounds. In each round, messages of bounded length
can be sent. (This is the assumption of the CONGEST model. In the LOCAL model, messages’ size is
arbitrary.) The running time of an algorithm is this model is the number of rounds that it runs. By ”parallel”
model we mean here PRAM EREW model [Rei93], and we are interested in algorithms with small running
time (aka depth) and work complexities. (The latter measures the overall number of operations performed
by all processors.)
Dubhashi et al. [DMP+ 03] devised a distributed implementation of the greedy algorithm in the LOCAL
model of distributed computation. Their algorithm runs in O(α · log2 n) rounds, i.e., suboptimal by a factor
of log2 n. Moreover, it collects graph topology to depth O(α), and conducts heavy local computations.
To our knowledge, there is no distributed-CONGEST or PRAM implementation of the greedy algorithm
known. There is also no known efficient3 centralized, distributed-CONGEST, or PRAM algorithm that
constructs ultra-sparse spanners, i.e., spanners with n + o(n) edges.
2

In the sequel we discuss a distributed setting, specifically, the LOCAL model, in which a relatively efficient implementation of
the greedy is known.
3
By “efficient” centralized algorithm in this paper we mean an algorithm with running time close to O(|E|). By efficient
distributed or parallel algorithm we mean an algorithm that runs in polylogarithmic, or nearly-polylogarithmic, time.

2

In the distributed and parallel settings it is often enough to compute a sparse skeleton H of the input
graph G, where a skeleton is a connected subgraph that spans all the vertices of G, i.e., the stretch requirement is dropped. Dubhashi et al. [DMP+ 03] devised a distributed-LOCAL algorithm that computes ultrasparse skeletons of size m(n, α) ≤ n + O(n · logα n ) in O(α) rounds. Like their algorithm for constructing
spanners, this algorithm also collects topologies to depth O(α), and involves heavy local computations. To
our knowledge, no efficient distributed-CONGEST or PRAM algorithm for computing ultra-sparse skeletons is currently known. In this paper we devise the first such algorithms.

1.2 Prior Work and Our Results
In the centralized model of computation the best-known efficient algorithm for constructing multiplicative
spanners (for unweighted graphs) is due to Halperin and Zwick [HZ96]. Their deterministic algorithm, for
an integer parameter k ≥ 1, computes a (2k − 1)-spanner with n1+1/k + n edges in O(|E|) time. (Their
result improved previous pioneering work by [PS89, Coh99].) Note that their bound on the number of edges
is always at least 2n, i.e., in the range k = Ω(log n) it is very far from Moore’s bound.
Our centralized randomized algorithm computes (with probability close to 1), a (2k − 1)-spanner with
n · (1 + O( logk n )) edges in O(|E|) time, whenever k = Ω(log n). Note that when k = ω(log n), the number
of edges is n(1 + o(1)), i.e., in this range the algorithm computes an ultra-sparse spanner in O(|E|) time.
Moreover, whenever k ≤ n1−ǫ , for any constant ǫ > 0, up to a constant factor in the lower-order term, our
bound matches Moore’s bound. In fact, our algorithm and its analysis can be viewed as an alternative proof
of (a slightly weaker version of) the generalized Moore’s bound. Note that it is not the case for the greedy
algorithm and its implementations [ADD+ 93, RZ04, DMP+ 03]: the analysis of these algorithms relies on
Moore’s bounds, but these algorithms cannot be used to derive them.
Another variant of our algorithm, which works for any k ≥ 2, computes with high probability a (2k−1)2 ln n
spanner with n1+1/k (1 + O( logk k )) edges, in Õ(k|E|) time.4 In particular, for the range k ≥ ln
ln n the
1+1/k
number of edges in our spanner is n
+ o(n), improving the result of [HZ96] (albeit with a somewhat
2 ln n
1+1/k ) edges.
worse running time for ln
ln n ≤ k ≤ log n). Note that for any k ≥ 2 we have O(n
1+1/k
Yet another variant of our algorithm computes a (2k − 1)-spanner with O(n
) edges, in expected
O(|E|) time.
In the distributed-CONGEST and PRAM models, efficient algorithms for computing linear-size spanners were given in [Pet09, MPVX15]. Specifically, [MPVX15] devised an O(k)-round distributed-CONGEST
randomized algorithm for constructing O(k)-spanner (with high probability) with expected O(n1+1/k )
edges. In the PRAM model their algorithm has depth O(k log∗ n) and work O(|E|). There are also
k-round distributed-CONGEST randomized algorithms for constructing (2k − 1)-spanner with expected
O(k · n1+1/k ) edges [BS07, Elk07a]. It is known that at least k rounds are required for this task, under
Erdős’ girth conjecture [Elk07a, DGPV08].
Our randomized algorithm uses k rounds in the distributed-CONGEST model, and with probability at
least 1 − ǫ it constructs a (2k − 1)-spanner with O(n1+1/k /ǫ) edges (for any desired, possibly sub-constant,
ǫ > 0). In the PRAM model the depth and work complexities of our algorithm are the same as in [MPVX15].
n
Furthermore, when k ≥ log n we can bound the number of edges by n · (1 + O( log
ǫ·k )), again matching
Moore’s bound up to a constant factor in the lower-order term.
This result improves the previous state-of-the-art in the entire range of parameters. In particular, it is
also the first efficient algorithm in the distributed-CONGEST or PRAM models that constructs an ultrasparse skeleton. Specifically, in Õ(log n) time it computes an Õ(log n)-spanner with n(1 + o(1)) edges,
4

As usual, Õ(f (n)) stands for O(f (n)polylogf (n)).

3

with probability 1 − o(1).
We also use our algorithm for unweighted graphs to devise an improved algorithm for weighted graphs
as well. Specifically, our algorithm computes (2k − 1)(1 + ǫ)-spanner with O(n1+1/k · (log k)/ǫ) edges,
within expected O(|E|) time. See Theorem 2, and the discussion that follows it, for further details.

1.3 Near-Additive Spanners and Emulators
It was shown in [EP04] that for any ǫ > 0 and κ = 1, 2, . . ., and any (unweighted) n-vertex graph G =
(V, E), there exists a (1 + ǫ, β)-spanner with O(β · n1+1/κ ) edges, where β = β(κ, ǫ) ≤ O( logǫ κ )log κ . Additional algorithms for constructing such spanners were later given in [Elk04, EZ06, TZ06, DGPV08, Pet09,
Pet10]. Abboud and Bodwin [AB16] showed that multiplicative error of 1 + ǫ in [EP04]’s theorem cannot
be eliminated, while still keeping a constant (i.e., independent of n) additive error β, and more recently
log κ−1

1
.
[ABP17] showed that any such (1 + ǫ, β)-spanner of size O(n1+1/κ−δ ), δ > 0, has β = Ω ǫ·log
κ
In the regime of constant κ, the bound of [EP04] remains the state-of-the-art. Pettie [Pet09] showed that
n log log n
)
.
one can construct a (1 + ǫ, β)-spanner with O(n log log(ǫ−1 log log n)) edges and β = O( log log
ǫ
This result of [Pet09] is not efficient in the sense considered in this paper, i.e., no distributed or parallel
implementations of it are known, and also no efficient (that is, roughly O(|E|)-time) centralized algorithm
computing it is known. Also, this result does not extend ([Pet16]) to a general tradeoff between β and the
number of edges.
Improving upon previous results by [Elk05, EZ06], Pettie [Pet10] also devised an efficient distributedCONGEST algorithm, that for a parameter ρ > 0, constructs in Õ(nρ ) rounds a (1 + ǫ, β)-spanner with

logφ κ+1/ρ
√
O(n1+1/κ (ǫ−1 log κ)φ ) edges and β = O log κ+1/ρ
, for φ = 1+2 5 being the golden ratio. 5
ǫ
Independently and simultaneously to our work, [ABP17] showed that there exist (1 + ǫ, β)-spanners with
log κ−2

κ
< 3/4. This
, where h = (3/4)κ−1−log
O((ǫ−1 log κ)h · log κ · n1+1/κ ) edges and β = O logǫ κ
κ
spanner has improved dependence on ǫ in the number of edges (at the cost of worse dependence on κ).
In this paper we improve all of the tradeoffs [EP04, Pet10] in the entire range of parameters. Specifically,
log n
for any ǫ > 0, ρ > 0 and κ = 1, 2, . . . , log(1/ǫ)+log
log log n , our distributed-CONGEST algorithm constructs
in Õ(nρ ) rounds a (1 + ǫ, β)-spanner with O(n1+1/κ ) edges and


log κ + 1/ρ log κ+1/ρ
β≤O
.
ǫ
Our algorithm also admits efficient implementations in the streaming and standard models of computation,
see Section 3. Our spanners are sparser and have polynomially smaller β than the previous best efficient constructions. They are even sparser than the state-of-the-art existential ones (with essentially the same β), with
the following exceptions: whenever ǫ < 1/ log3 log n our result and that of [ABP17] are incomparable,6 and
the spanner from [Pet09] that has O(n log(4) n) edges, while ours never gets sparser than O(n log log n)/ǫ.
In the complementary range, ǫ > 1/ log3 log n, our result is strictly stronger than that of [ABP17].
Moreover, a variant of our algorithm efficiently constructs very sparse (1+ǫ, β)-emulators. In particular,
n log log n
we can obtain a linear-size (1 + ǫ, ( log log
)
)-emulator. (We stress that the number of edges does not
ǫ
depend even on ǫ.) All previous constructions of (1 + ǫ, β)-spanners or emulators employ a superlinear
number of edges, for all choices of parameters.
In the range of κ = o( logloglogn n ), the result of [Pet10] is incomparable with [EP04], as spanners of [EP04] provide smaller β,
while spanners of [Pet10] are slightly sparser.
6
The i-iterated logarithm is defined by log(i+1) n = log(log(i) n), for all i ≥ 0, and log(0) n = n.
5

4

We use our new algorithms for constructing near-additive spanners and emulators to improve approximate shortest paths’ algorithms, in the centralized and streaming models of computation. One notable result
in this context is a streaming algorithm that for any constant ǫ > 0 and any subset S ⊆ V with |S| = nΩ(1) ,
computes (1+ǫ)-approximate shortest paths for S ×V within O(|S|) passes over the stream, using O(n1+ǫ )
space. See Section 4 for more details, and additional applications of our spanners.

1.4 Technical Overview
Linial and Saks [LS93] were the first to employ exponential random variables to build network decompositions, i.e., partitions of graphs into clusters of small diameter, which possess some useful properties. This
technique was found useful for constructing padded partitions, hierarchically-separated trees, low-stretch
spanning trees [Bar96, Bar98, Bar04, EEST05, ABN11, AN12] and spanners [Coh99, BS03, Elk07b]. In
[LS93] every vertex v tosses a random variable rv from an exponential distribution, and broadcasts to all
vertices within distance rv from v. Every vertex v joins the cluster of a vertex u with largest identity number,
whose broadcast u heard.
Blelloch et al. [BGK+ 14] introduced a variant of this technique in which, roughly speaking, every vertex
v starts to broadcast at time −rv , and broadcasts indefinitely. A vertex x joins the cluster centered at a vertex
v, whose broadcast reaches x first. They called the resulting partition “exponential start time clustering”,
and it was demonstrated in [BGK+ 14, MPX13, EN16a] that this approach leads to very efficient distributed
and parallel algorithms for constructing padded partitions and network decompositions.
Miller et al. [MPVX15] used this approach to devise an efficient parallel and distributed-CONGEST
O(k)-time algorithm for constructing O(k)-spanner with O(n1+1/k ) edges. Specifically, they build the
exponential time clustering, add the spanning trees of the clusters into the spanner, and then every vertex x
adds into the spanner one edge (x, y) connecting x to every adjacent cluster Cy , y ∈ Cy .
The main property of the partition exploited by [MPVX15] in the analysis of their algorithm is that any
unit-radius ball in the input graph G intersects just O(n2/k ) clusters, in expectation. Note also that their
algorithm is doomed to use at least n1+1/k + (n − 1) edges, because it starts with inserting the spanning
trees of all clusters (amounting to up to n − 1 edges), and then inserts the O(n1+2/k ) edges crossing between
different clusters into the spanner. To get O(n1+1/k ) edges, one rescales k′ = 2k.
In our algorithm we do not explicitly construct the exponential start time clustering. Rather we run the
procedure that builds it, but every vertex x connects not just to the neighbor y through which x received its
first broadcast message at time, say, ty , but also to all neighbors z whose broadcast x received witin time
interval [ty , ty + 1]. We show that, in expectation, x connects to n1/k neighbors altogether, and not just to
that many adjacent clusters. As a result we obtain both a sparser spanner, a smaller stretch, and a smaller
running time. The stretch and running time are smaller roughly by a factor of 2 than in [MPVX15], because
we do not need to consider unit balls, that have diameter 2. Rather we tackle individual edges (of length 1).
In the context of weighted graphs, [MPVX15] showed how their efficient algorithm for constructing
sparse (4k − 2)-spanners for unweighted graphs can be converted into an efficient algorithm that constructs
(16k − 8)-spanners with O(n1+1/k log k) edges for weighted graphs. By using their scheme naively on top
of our algorithm for unweighted graphs, one gets an efficient algorithm for computing (4k − 2)(1 + ǫ)spanners with O(n1+1/k · (log k)/ǫ) edges. Roughly speaking, the overhead of 2 in the stretch is because
in the analysis of [MPVX15], every vertex contributes expected O(n1/k ) edges to the spanner on each of
roughly O(n1/k ) phases of the algorithm in which it participates. By employing a more delicate probabilistic
argument, we argue that in fact, the expected total contribution of every vertex in all phases altogether is
O(n1/k ), rather than O(n2/k ). This enables us to eliminate another factor of 2 from the stretch bound. See
Section 2.3 for details.
5

Our constructions of (1 + ǫ, β)-spanners and emulators follow the [EP04] superclustering and interconnection approach. One starts with a base partition P0 . In [EP04] this was the partition of [Awe85, PS89,
AP92], obtained via region-growing technique. Then every cluster C ∈ P0 that has “many” unclustered
clusters of P0 “nearby”, creates a supercluster around it. The “many” and the “nearby” are determined
by degree threshold deg 0 and distance threshold δ0 , respectively. Once the superclustering phase is over,
the remaining unclustered clusters enter an interconnection phase, i.e., every pair of participating nearby
clusters gets interconnected by a shortest path in the spanner. This completes one iteration of the process.
The resulted superclustering P1 is the input for the next iteration of this process, which runs with different,
carefully chosen thresholds deg 1 and δ1 . Such iterations continue until only very few clusters survive. The
latter are interconnected without further superclustering.
One bottleneck in devising efficient distributed algorithm based on this approach is the base partition. Known algorithms for constructing a region-growing partition of [Awe85] require almost linear distributed time [DMZ06]. We demonstrate that one can bypass it completely, and start from the base partition
P0 = {{v} | v ∈ V }. This requires some modfication of the algorithm, and a more nuanced analysis. In
addition, we show that the superclustering and interconnection steps themselves can be implemented efficiently. This part of the algorithm is based on our recent work on hopsets [EN16b], where we showed that
[EP04] approach is extremely useful in that context as well, and that it can be made efficient.

1.5 Related Work
Efficient algorithms for constructing (1 + ǫ, β)-spanners were also devised in [Elk05, EZ06, TZ06, Pet09,
Pet10]. These algorithms are based, however, on different approaches than that of the current paper. The
latter is based on [EP04]. Specifically, the approach of [Elk05, EZ06] is based on [Coh99, Coh00] construction of pairwise covers and hopsets, i.e., the algorithm works top-down. It recurses in small clusters, and
eliminates large ones. The approach of [TZ06, Pet09, Pet10] is based on [TZ05] collection of trees, used
originally for distance oracles.
Streaming algorithms for constructing multiplicative spanners were given in [FKM+ 05, Elk07b, Bas08],
and near-additive spanners in [Elk05, EZ06]. Spanners and emulators with sublinear error were given
in [TZ06, Pet09]. Spanners with purely additive error and lower bounds concerning them were given in
[ACIM99, EP04, BCE05, BKMP10, Che13, Woo06, BW15, AB16].

1.6 Organization
In Section 2 we present our algorithm for constructing multiplicative spanners and its analysis. In Section
2.3 we use this algorithm to provide improved spanners for weighted graphs as well. Our near-additive
spanners and emulators are presented in Section 3.

2 Sparse Multiplicative Spanners and Skeletons
Let G = (V, E) be a graph on n vertices, and let k ≥ 1 be an integer. Let c > 3 be a parameter governing
the success probability, and set β = ln(cn)/k. Recall the exponential distribution with parameter β, denoted
EX P(β), which has density

β · e−βx
x≥0
f (x) =
0
otherwise.

6

Construction. Each vertex u ∈ V samples a value ru from EX P(β), and broadcasts it to all vertices
within distance k. Each vertex x that received a message originated at u, stores mu (x) = ru − dG (x, u),
and also a neighbor pu (x) that lies on a shortest path from x to u (this neighbor sent x the message from u,
breaking ties arbitrarily if there is more than one). Let m(x) = maxu∈V {mu (x)}, then for every x ∈ V we
add to the spanner H the set of edges
C(x) = {(x, pu (x)) : mu (x) ≥ m(x) − 1} .
The following lemma is implicit in [MPVX15]. We provide a proof for completeness.
Lemma 1 ([MPVX15]). Let d1 ≤ . . . ≤ dn be arbitrary values and let δ1 , . . . , δn be independent random
variables sampled from EX P(β). Define the random variables M = maxi {δi − di } and I = {i : δi − di ≥
M − 1}. Then for any 1 ≤ t ≤ n,
Pr[|I| ≥ t] = (1 − e−β )t−1 .
Proof. Denote by X (t) the random variable which is the t-th largest among {δi − di }. Then for any value
a ∈ R, if we condition on X (t) = a, then the event |I| ≥ t is exactly the event that all the remaining t − 1
values X (1) , . . . , X (t−1) are at least a and at most a + 1. Using the memoryless property of the exponential
distribution and the independence of the {δi }, we have that
Pr[|I| ≥ t | X (t) = a] = (1 − e−β )t−1 .
Since this bound does not depend on the value of a, applying the law of total probability we conclude that
Pr[|I| ≥ t] = (1 − e−β )t−1 .

Using this lemma, we can bound the expected size of the spanner.
Lemma 2. The expected size of H is at most (cn)1/k · n.
Proof. Fix any x ∈ V , and we analyze E[|C(x)|]. Note that the event |C(x)| ≥ t happens when there are at
least t shifted random variables ru − dG (u, x) that are within 1 of the maximum. By Lemma 1 this happens
with probability at most (1 − e−β )t−1 (we remark that if x did not hear at least t messages, then trivially
Pr[|C(x)| ≥ t] = 0). We conclude that
E[|C(x)|] =

n
X
t=1

Pr[|C(x)| ≥ t] ≤

∞
X
t=0

(1 − e−β )t = eβ = (cn)1/k ,

and the lemma follows by linearity of expectation.
We now argue about the stretch of the spanner.
Claim 3. With probability at least 1 − 1/c, it holds that ru < k for all u ∈ V .
Proof. For any u ∈ V , Pr[ru ≥ k] = e−βk = 1/(cn). By the union bound, Pr[∃u, ru ≥ k] ≤ 1/c.
Assume for now that the event of Claim 3 holds, i.e., that ru < k for all u ∈ V .
Corollary 4. For any x ∈ V , if u ∈ V is the vertex maximizing mu (x), then dG (u, x) < k.
7

Proof. First note that m(x) ≥ mx (x) ≥ 0, and using Claim 3 we have ru < k. So 0 ≤ m(x) = mu (x) =
ru − dG (u, x) < k − dG (u, x).
Claim 5. For any u, x ∈ V , if x adds an edge to pu (x), then there is a shortest path P between u and x
that is fully contained in the spanner H.
Proof. We prove by induction on dG (u, x). In the base case dG (x, u) = 1, then pu (x) = u, so (x, u) is
in the spanner. Assume that every vertex y ∈ V with dG (u, y) = t − 1 which added an edge to pu (y) has
a shortest path to u in H, and we prove for x that has dG (u, x) = t. We know that x added an edge to
y = pu (x), which lies on a shortest path to u, and thus satisfies dG (u, y) = t − 1. It remains to show that
this y added an edge to pu (y). First we claim that
m(y) ≤ m(x) + 1 .

(1)

Seeking contradiction, assume that (1) does not hold, and let v ∈ V be the vertex maximizing mv (y). By
Corollary 4 we have dG (v, y) < k, and thus dG (v, x) ≤ k. Hence x will hear the message of v. This means
that mv (x) ≥ mv (y) − 1 = m(y) − 1 > m(x), which is a contradiction. This establishes (1). Now, since x
added an edge to y = pu (x), by construction
mu (x) ≥ m(x) − 1 .
We conclude that

(2)
(1)

(2)

mu (y) = mu (x) + 1 ≥ m(x) − 1 + 1 ≥ m(y) − 1 ,
so y indeed adds an edge to pu (y), and by the induction hypothesis we are done.
Lemma 6. The spanner H has stretch at most 2k − 1.
Proof. Since H is a subgraph of G, it suffices to prove for any (x, y) ∈ E, that dH (x, y) ≤ 2k − 1. Let
u be the vertex maximizing m(x) = mu (x), and w.l.o.g assume m(x) ≥ m(y). By Corollary 4 we have
dG (u, x) ≤ k − 1, so dG (u, y) ≤ k, and y heard the message of u (which was sent to distance k). This
implies that mu (y) ≥ mu (x) − 1 = m(x) − 1 ≥ m(y) − 1, so y adds the edge (y, pu (y)) to the spanner. By
applying Claim 5 on x and y, we see that both have shortest paths to u that are fully contained in H. Since
dG (x, u) ≤ k − 1 and dG (y, u) ≤ k, these two paths provide stretch 2k − 1 between x, y.

2.1 Main Theorem
We now state our main theorem, from which we will derive several interesting corollaries in various settings.
Theorem 1. For any unweighted graph G = (V, E) on n vertices, any integer k ≥ 1, c > 3 and δ > 0,
there is a randomized algorithm that with probability at least (1 − 1/c) · δ/(1 + δ) computes a spanner with
stretch 2k − 1 and number of edges at most
(1 + δ) ·

(cn)1+1/k
− δ(n − 1) .
c−1

Proof. Let Z be the event that {∀u ∈ V, ru < k}. By Claim 3 we have Pr[Z] ≥ 1 − 1/c. Note that
conditioning on Z, by Lemma 6 the algorithm produces a spanner H = (V, E ′ ) with stretch 2k − 1. In
particular, it must have at least n − 1 edges. Let X be the random variable |E ′ | − (n − 1), which conditioned
on Z takes only nonnegative values. By Lemma 2 we have E[X] = (cn)1/k · n − (n − 1). We now argue
8

that conditioning on Z will not affect this expectation by much. Indeed, by the law of total probability, for
any t, Pr[X = t] ≥ Pr[X = t | Z] · Pr[Z]. Thus
E[X | Z] ≤
By Markov inequality,

h
i
E[X]
c
≤
· (cn)1/k · n − (n − 1) .
Pr[Z]
c−1

Pr [X ≥ (1 + δ)E[X | Z] | Z] ≤

(3)

1
.
1+δ

We conclude that

Pr [(X < (1 + δ)E[X | Z]) ∧ Z] = Pr [X < (1 + δ)E[X | Z] | Z] · Pr[Z] ≥



1
1−
c



·

δ
.
1+δ

If this indeed happens, then
|E ′ | = X + n − 1
h
i
(3)
c
≤ (1 + δ) ·
· (cn)1/k · n − (n − 1) + n − 1
c−1
(cn)1+1/k − (n − 1)
= (1 + δ) ·
− δ(n − 1) .
c−1

2.1.1

Implementation Details

Distributed Model. It is straightforward to implement the algorithm in the LOCAL model of computation,
it will take k rounds to execute it – in each round, every vertex sends to its neighbors all the messages it
received so far. We claim that the algorithm can be implemented even when bandwidth is limited, i.e., in the
CONGEST model. This will require a small variation: in each round, every vertex v ∈ V will send to all its
neighbors the message (ru , dG (u, v)) for the vertex u that currently maximizes mu (v) = ru − dG (u, v). We
note that omitting all the other messages will not affect the algorithm, since if one such message would cause
some neighbor of v to add an edge to v, then the message about u will suffice, as the latter has the largest
mu (v) value. (Also recall that all vertices start their broadcast simultaneously, and do so for k rounds, so
any omitted message could not have been sent to further distance than the message from u, which implies
dropping it will have no effects on farther vertices as well.)
PRAM Model. In the parallel model of computation, we can use a variant of the construction that appeared
in [MPX13, MPVX15]. Roughly speaking, vertex u will start its broadcast at time k − ⌈ru ⌉, and every
vertex x will send only the first message that arrives to it (which realizes m(x)). As argued in [MPVX15],
the algorithm can be implemented in O(k log∗ n) depth and O(|E|) work.
Standard Centralized Model. Note that in the standard centralized model of computation, the running
time is at most the work of the PRAM algorithm, which is O(m). By taking constant c and δ, and repeating
the algorithm until the first success (we can easily check the number of edges of the spanner and that all
ru < k), we get a spanner with stretch 2k − 1 and O(n1+1/k ) edges in expected time O(|E|).
9

2.2 Implications of Theorem 1
2.2.1

Standard Centralized Model and PRAM

The currently sparsest spanners which can be constructed in linear time are those of Halperin and Zwick
[HZ96]. They provide for any k ≥ 1, a deterministic algorithm running in O(m) time, that produces a
spanner with n1+1/k + n edges. We can improve their result for a wide range of k, albeit with a randomized
algorithm. First we show a near-linear time algorithm (which can be also executed in parallel), that provides
a spanner sparser than Halperin and Zwick in the range k ≥ 2 ln n/ ln ln n.7
Corollary 7. For any unweighted graph G = (V, E) on n vertices and m edges, and any integer k ≥ 2,
there is a randomized
algorithm,
that with high probability8 computes a spanner for G with stretch 2k − 1


k)
edges. The algorithm has O(k2 ln n ln∗ n) depth and the running time (or work)
and n1+1/k · 1 + O(ln
k

is Õ(k|E|).

Proof. Apply Theorem 1 with parameters c = k and δ = 1/k. So with probability at least
we obtain a spanner whose number of edges is at most


(kn)1+1/k
O(ln k)
1+1/k
(1 + 1/k) ·
≤n
· 1+
.
k−1
k

k−1
k

·

1
k+1

≥

1
3k

(4)

Run the algorithm C · k ln n times for some constant C. We noted in Section 2.1.1 that each run takes
O(k ln∗ n) depth and O(|E|) work, so the time bounds are as promised. Now, with probability at least
1 − (1 − 1/(3k))C·k ln n ≥ 1 − n−C/3 , we achieved a spanner with number of edges as in (4) in one of the
executions.
√
Remark 1. Whenever k ≥ 2 ln n/ ln ln n, we have n1/k ≤ ln n, so the number of edges in Corollary 7 is
n1+1/k + o(n), and the running time is Õ(k|E|).
2.2.2

Distributed Model

In a distributed setting we have the following result.
Corollary 8. For any unweighted graph G = (V, E) on n vertices, any k ≥ 1 and 0 < ǫ < 1, there is a
randomized distributed algorithm that with probability at least 1 − ǫ computes a spanner with stretch 2k − 1
and O(n/ǫ)1+1/k edges, within k rounds.
Proof. Apply Theorem 1 with c = 3/ǫ and δ = 2/ǫ, so the success probability is at least
(1 − ǫ/3) · (1 − ǫ/(ǫ + 2)) > 1 − ǫ .
With these parameters, by Theorem 1, the number of edges in spanner will be bounded by O(n/ǫ)1+1/k .
7
8

In fact, the factor 2 can be replaced by any 1 + ǫ for constant ǫ > 0.
By high probability we mean probability at least 1 − n−C , for any desired constant C.

10

2.2.3

Ultra-Sparse Spanners and Skeletons

We now show that in the regime k ≥ ln n, our algorithm (that succeeds with probability close to 1) provides
a spanner whose number of edges is very close to n (as a function of k and the success probability). This
will hold in all computational models we considered. We note that for the centralized and PRAM models,
Corollary 7 gives high probability with roughly the same sparsity, albeit with larger depth and work.
Corollary 9. For any unweighted graph G = (V, E) on n vertices, and any integer k ≥ ln n and parameter
2/k < ǫ < 1, there is a randomized
algorithm,
that with probability at least 1 − ǫ computes a spanner for G


O(ln n)
with stretch 2k − 1 and n · 1 + ǫ·k
edges. The number of rounds in distributed model is k, in PRAM
∗
it is O(k log n) depth and O(|E|) work, and in the centralized model it is O(|E|) time.
Proof. Apply Theorem 1 with parameters c = k and δ = 2/ǫ, so with probability at least

≥ 1−ǫ

e(2 ln n)/k

≤ 1 + O(ln n)/k, so



(kn)1+1/k
O(ln n)
(1 + 2/ǫ) ·
− 2(n − 1)/ǫ ≤ n · 1 +
.
k−1
ǫ·k

(5)

we obtain a (2k − 1)-spanner. In the regime k ≥ ln n we have
the number of edges is at most

(kn)1/k

2/ǫ
k−1
k · 2/ǫ+1

≤

Remark 2. The spanner of Corollary 9 can be used as a skeleton. E.g., one can take ǫ = o(1) and
k = Õ(log n), to obtain with probability 1 − o(1), a skeleton with n(1 + o(1)) edges, which is computed in
Õ(log n) rounds.

2.3 Weighted Graphs
Miller et al. [MPVX15] used their efficient algorithm for constructing O(k)-spanners with O(n1+1/k ) edges
for unweighted graphs, to provide an efficient algorithm for constructing O(k)-spanners with O(n1+1/k log k)
edges for weighted graphs. In this section we argue that their scheme can be used to convert our algorithm
for constructing (2k − 1)-spanners with O(n1+1/k ) edges for unweighted graphs (Theorem 1; see also Section 2.1.1) into an efficient algorithm for constructing (2k − 1)(1 + ǫ)-spanners with O(n1+1/k · logǫ k ) edges
for weighted graphs.
The scheme of [MPVX15] works in the following way. It partitions all edges of G = (V, E) into
⌈log1+ǫ ωmax ⌉ = λ categories Et = {e ∈ E | ω(e) ∈ [(1 + ǫ)t−1 , (1 + ǫ)t )}, t = 1, 2, . . . , λ. (We assume
that the minimum weight is 1, and the maximum weight is ωmax . The last category Eλ should also contain
edges of weight exactly ωmax .) Now one defines ℓ = ⌈log1+ǫ kc ⌉, for a sufficiently large constant c, graphs
S
Gj = (V, Êj ), j = 0, 1, . . . , ℓ − 1, Êj = {Et | t ≡ j( mod ℓ)}.
Observe that the edge weights in (each) Gj are well-separated, i.e., Êj is a disjoint union of at most
q = ⌈λ/ℓ⌉ edge sets E (1) , . . . , E (q) , such that the edge weights within each set are within a factor of 1 + ǫ
from one another. Moreover, if edge weights in E (i) , i = 1, 2, . . . , q, are in the range [w(i) , (1 + ǫ)w(i) ),
then we have w(i) = w(1) (kc )i−1 , for every i = 1, 2, . . . , q.
For each graph Gj , the scheme of [MPVX15] constructs an O(k)-spanner with O(n1+1/k ) edges. It
then takes a union of ℓ = O( logǫ k ) such spanners as the ultimate O(k)-spanner of the original graphs. (In
fact, [MPVX15] used specifically ǫ = 1.) We will next outline the way in which [MPVX15] construct O(k)spanner with O(n1+1/k ) edges for each Gj , and show how to modify it to provide a (2k − 1)(1 + ǫ)-spanner.
11

The scheme starts with running a routine of [MPVX15] that constructs an O(k)-spanner H (1) with
O(n1+1/k ) edges for the unweighted graph (V (1) , E (1) ), V (1) = V , and constructing the exponential start
time partition P (1) for it. It then contracts each of the clusters of P (1) (which have unweighted radii at most
k − 1) into single vertices of V (2) , and runs the unweighted spanner routine on (V (2) , E (2) ). As a result, it
constructs an O(k)-spanner H (2) and a partition PS(2) of V (2) , contracts all clusters of P (2) to get V (3) , etc.
The final spanner returned by the scheme is H = qi=1 H (i) .
The scheme guarantees stretch (1 + ǫ)(1 + O(k−(c−1) ))O(k), because the blackbox routine for unweighted graphs provides stretch O(k) for each category of weights, but the weights are uniform only up to
a factor of 1 + ǫ. Also, the factor of 1 + O(k−(c−1) ) appears, because one contracts clusters of unweighted
diameter O(k) of lower scales, on which all edge weights are a factor of roughly k−c smaller than the edge
weights on the current scale.
In the analysis of |H|, [MPVX15] show that every vertex u is active (i.e., non-isolated vertex which
is not yet contracted into a larger super-vertex) for expected O(n1/k ) phases, and when it is active, it contributes expected O(n1/k ) edges to the spanner of the current phase. Hence the overall size of the spanner
is O(n1+2/k ), and by rescaling k′ = 2k, they ultimately get their result. (See the proof of Theorem 3.3 in
[MPVX15] for full details of this proof. We have sketched it for the sake of completeness.)
While the stretch analysis of [MPVX15] is sufficiently precise for our purposes, this is not the case with
the size analysis. Indeed, even when one plugs in stretch 2k − 1 of our unweighted spanner routine instead
of stretch O(k) of their routine, still one obtains a (2k − 1)(1 + ǫ)2 (1 + k−(c−1) )-spanner with O(n1+2/k )
edges, i.e., a (4k − 2)(1 + O(ǫ))-spanner with O(n1+1/k ) edges (for each Gj ).
In what follows we refine their size analysis, and show that, in fact, every vertex u contributes expected
O(n1/k ) edges in all phases of the algorithm altogether (for a single graph Gj with well-separated edge
(i)
weights). Denote by ru the radius that u tosses from EX P(β) in the ith phase, i = 1, 2, . . . , q, assuming
that it is active on that phase. We say that a vertex v (which is active on phase i) is a candidate vertex
(i)
of phase i if its broadcast message reaches u no later than within one time unit after the time −ru , i.e.,
(i)
(i)
−ru + 1 ≥ −rv + d(v, u), where d(v, u) is the unweighted distance between v and u in the graph on
which the unweighted spanner routine is invoked on phase i.
Let X (i) denote the random variable counting the number of such candidate vertices on phase i, for
i = 1, 2, . . . , q. (Recall that these are the vertices which might cause u to add an edge to the spanner.) Let
j denote the random variable which is the phase in which u was contracted (and j = q if there is no such
(i)
phase). That is, j indicates the level in which the broadcast of some candidate vertex v has −rv +d(v, u) <
(i)
−ru . Denote also by X̂ (i) , i = 1, 2, . . . , q, the total number of candidates u sees between the beginning
(j)
of phase i, and up until phase j, where a candidate vertex v reaches u before time −ru . On that phase
j, X̂ (i) counts the number of candidates with index not larger than that of the candidate vertex v (assume
every vertex has an arbitrary distinct index in {1, . . . n}). Note that for i > j, by definition, X̂ (i) = 0. Also,
in particular, X̂ = X̂ (1) is at least the total contribution of edges u adds to the spanner, except for up to
expected O(n1/k ) edges that it might contribute on phase j (as shown in Lemma 2).
We next argue that for any t = 0, 1, 2, . . .,
Pr(X̂ > t) ≤ (1 − e−β )t .
This implies that
E(X̂) =

∞
X
t=0

Pr(X̂ > t) ≤

∞
X
t=0

(1 − e−β )t = eβ = O(n1/k ) .

12

(6)

First, note that
Pr(X̂ > t) =

∞
X

t(1) =0

Pr(X (1) = t(1) ) · Pr(X̂ > t | X (1) = t(1) ) .

For t(1) > t, we have
Pr(X̂ > t | X (1) = t(1) ) = (1 − e−β )t .
To justify this equation, note that the left-hand side is exactly the probability that on the first phase, all the
(1)
(1)
t first candidate vertices v have −rv + d(v, u) ≥ −ru , conditioned on them being candidates, i.e., on
(1)
−rv + d(v, u) ≤ −ru + 1. Since these are independent shifted exponential random variables, the equation
follows from the memoryless property of the exponential distribution.
For t(1) ≤ t, we have
Pr(X̂ > t | X (1) = t(1) )

=

(1)

(1 − e−β )t

(1)

= (1 − e−β )t

· Pr(X̂ (2) > t − t(1) | X (1) = t(1) , X̂ (1) ≥ t(1) )

· Pr(X̂ (2) > t − t(1) | X̂ (1) ≥ X (1) ) .

(1)

(Again, (1 − e−β )t is the probability that no candidate vertex of the first phase reached u before time
(1)
−ru , and so u was not contracted away at this phase.)
We conduct an induction on the phase, where the induction base is the last phase i = q. On the last
phase, for any h,
Pr(X̂ (q) > h | X̂ (1) ≥ X (1) , X̂ (2) ≥ X (2) , . . . , X̂ (q−1) ≥ X (q−1) ) ≤ (1 − e−β )h ,
(q)

(1)

because it is just the probability that none of the first h candidates (that have −rv + d(v, u) ≤ −ru + 1)
(q)
reaches u before time −ru . (If there are fewer candidates or u was contracted in a previous phase, then
this probability is 0.)
Hence by the inductive hypothesis,
(1)

Pr(X̂ (2) > t − t(1) | X̂ (1) ≥ X (1) ) ≤ (1 − e−β )t−t

,

and so
for any t(1) ≤ t as well. Hence

Pr(X̂ (1) > t | X (1) = t(1) ) ≤ (1 − e−β )t ,

Pr(X̂ > t) =
≤

∞
X

t(1) =0
∞
X

t(1) =0

Pr(X (1) = t(1) ) · Pr(X̂ > t | X (1) = t(1) )
Pr(X (1) = t(1) ) · (1 − e−β )t = (1 − e−β )t ,

as required.
Hence the expected contribution of every vertex is O(n1/k ), and the overall spanner size for each Gj
is, in expectation, O(n1+1/k ). The running time of the algorithm is expected to be O(|E|), following the
analysis of [MPVX15]. Moreover, as in [MPVX15], our algorithm can be implemented in PRAM model,
in O(log n · log∗ n · log Λ) depth, and O(|E|) work, where Λ is the aspect ratio of the input graph. We
summarize the result below.
13

Theorem 2. Given a weighted n-vertex graph G, and a pair of parameters k ≥ 1, 0 < ǫ < 1, our algorithm
computes a (2k − 1)(1 + ǫ)-spanner of G with O(n1+1/k · (log k)/ǫ) edges, in expected O(|E|) centralized
time, or in O(log n · log∗ n · log Λ) depth and O(|E|) work.
The result of Theorem 2 can be used in conjunction with the scheme of [ES16] to devise an algorithm
that computes (2k − 1)(1 + ǫ)-spanners of size O(n1+1/k (log k/ǫ)1/ǫ), with lightness (i.e., weight of the
spanner divided by the weight of the MST of the input graph) O(k · n1/k (1/ǫ)2+1/k ), in expected time
O(|E| + min{n log n, |E|α(n)}), where α(·) is an inverse-Ackermann function. This improves a result
of [ES16] that provides spanners with the same stretch and lightness, but with more edges (specifically,
O((k + (1/ǫ)2+1/k )n1+1/k ), and using O(k · |E| + min{n log n, |E|α(n)}) time. Recently, consequently to
our work, Alstrup et al. [ADF+ 17] further improved these bounds. We thus omit the details of our argument
that provides the aforementioned bounds.

3 An Efficient Centralized Construction of Nearly-Additive Spanners and
Emulators
3.1 A Basic Variant of the Algorithm
In this section we present an algorithm for constructing (1 + ǫ, β)-spanners, which can be efficiently implemented in various settings. We start with the centralized setting. In this setting we present two variants of
our construction. The first variant presented in this section is somewhat simpler, while the second variant
presented in the next section provides better bounds.
Let G = (V, E) be an unweighted graph on n vertices, and let k ≥ 1, ǫ > 0 and 0 < ρ < 1/2 be
parameters. Unlike the algorithm of [EP04], our algorithm does not employ sparse partitions of [AP92].
The algorithm initializes the spanner H as an empty set, and proceeds in phases. It starts with setting
P̂0 = {{v} | v ∈ V } to be the partition of V into singleton clusters. The partition P̂0 is the input of phase 0
of our algorithm. More generally, P̂i is the input of phase i, for every index i in a certain appropriate range,
which we will specify in the sequel.
Throughout the algorithm, all clusters C that we will construct will be centered at designated centers rC . In particular, each singleton cluster C = {v} ∈ P̂0 is centered at v. We define Rad (C) =
max{dG(C) (rC , v) | v ∈ C}, and Rad (P̂i ) = maxC∈P̂i {Rad (C)}.
All phases of our algorithm except for the last one consist of two steps. Specifically, these are the
superclustering and the interconnection steps. The last phase contains only the interconnection step, and
the superclustering step is skipped. We also partition the phases into two stages. The first stage consists of
phases 0, l
1, . . . m, i0 = ⌊log(κρ)⌋, and the second stage consists of all the other phases i0 + 1, . . . , i1 where
i1 = i0 + κ+1
κρ − 2, except for the last phase ℓ = i1 + 1. The last phase will be referred to as the concluding
phase.
Each phase i accepts as input two parameters, the distance threshold parameter δi , and the degree parameter deg i . The difference between stage 1 and 2 is that in stage 1 the degree parameter grows exponentially,
while in stage 2 it is fixed. The distance threshold parameter grows in the same steady rate (increases by a
factor of 1/ǫ) all through the algorithm.
Next we describe the first stage of the algorithm. We start with describing its superclustering step. We
i
set deg i = n2 /κ , for all i = 0, 1, . . . , i0 . Let R0 = 0, and δi = (1/ǫ)i + 4 · Ri , where Ri is determined by
the following recursion: Ri+1 = δi + Ri = (1/ǫ)i + 5 · Ri . We will show that the inequality Rad (P̂i ) ≤ Ri
will hold for all i.
14

On phase i, each cluster C ∈ P̂i is sampled i.a.r. with probability 1/deg i . Let Si denote
S the set of
sampled clusters. We now conduct a BFS exploration to depth δi in G rooted at the set Si = C∈Si {rC }.
As a result, a forest Fi is constructed, rooted at vertices of Si . For a cluster center r ′ = rC ′ of a cluster
C ′ ∈ P̂i \Si such that r ′ is spanned by Fi , let rC be the root of the forest tree of Fi to which r ′ belongs. (The
vertex rC is by itself a cluster center of a cluster C ∈ Si .) The cluster C ′ becomes now superclustered in a
cluster Ĉ centered around the cluster C. (We also say that C ′ is associated with C. We will view association
as a transitive relation, i.e., if C ′ is associated with C and C ′′ is associated with C ′ , we will think of C ′′ as
associated with C as well.)
The cluster center rC of C becomes the new cluster center of Ĉ, i.e., rĈ = rC . The vertex set of the
new supercluster Ĉ is the union of the vertex set of C with the vertex sets of all clusters C ′ which are
superclustered into Ĉ. The edge set TĈ of the new cluster Ĉ contains the BFS spanning trees of all these
clusters, and, in addition, it contains shortest paths from the forest Fi between rC and each rC ′ as above. Ŝi
is the set of superclusters created by this process. We set P̂i+1 = Ŝi . All edges that belong to the edgeset of
one of these superclusters are now added to the spanner H.
For each supercluster Ĉ, we write Rad (Ĉ) = Rad (TĈ , rĈ ). Observe that Rad (P̂0 ) ≤ R0 = 0, and
Rad (Ŝ0 ) = max{Rad (Ĉ) | Ĉ ∈ Ŝ0 } ≤ δ0 + R0 = R1 = 1. More generally we have
Rad (Ŝi ) = max{Rad (Ĉ) | Ĉ ∈ Ŝi } ≤ δi + Rad (P̂i ) ≤ δi + Ri ≤ (1/ǫ)i + 5Ri = Ri+1 .

(7)

Denote by Ûi the set of clusters of P̂i which were not superclustered into clusters of Ŝi . In the interconnection step for i ≥ 1, every cluster center rC of a cluster C ∈ Ûi initiates a BFS exploration to depth 21 δi ,
i.e., half the depth of the exploration which took place in the superclustering step. For each cluster center
rC ′ for C ′ ∈ P̂i which is discovered by the exploration initiated in rC , the shortest path between rC and rC ′
is inserted into the spanner H. The first phase i = 0 is slightly different: the exploration depth is set to be
1, and we add an edge from {v} ∈ Û0 to all neighbors that are in Û0 . This completes the description of the
interconnection step.
Lemma 10. For any vertex v ∈ V , the expected number of explorations that visit v at the interconnection
step of phase i is at most deg i .
Proof. For i ≥ 1, assume that there are l clusters of P̂i whose centers are within distance δi /2 from v. If
at least one of them is sampled to Si , then no exploration will visit v (since in the superclustering phase the
sampled center will explore to distance δi , and thus will supercluster all these centers). The probability that
none of them is sampled is (1 − 1/deg i )l , in which case we get that l explorations visit v, so the expectation
is l · (1 − 1/deg i )l ≤ deg i (which holds for any l).
For i = 0, we note that we add an edge touching v iff none of its neighbors were sampled at phase 0
(as otherwise it would be clustered and thus not in Û0 ). The expected number of edges added is once again
l · (1 − 1/deg i )l ≤ deg i (here l is the number of neighbors).
We also note the following lemma for future use, its proof follows from a simple Chernoff bound.
Lemma 11. For any constant c > 1, with probability at least 1 − 1/nc−1 , for every vertex v ∈ V , at least
one among the deg i · c · ln n closest cluster centers rC ′ with C ′ ∈ P̂i to v is sampled, i.e., satisfies C ′ ∈ Si .
Observe that no vertex v ∈ V is explored by more than c · ln n · deg i explorations, with probability at
least 1 − n−(c−1) . Indeed, otherwise when i ≥ 1 there would be more than c · ln n · deg i cluster centers
rC of unsampled clusters C ∈ P̂i at pairwise distance at most δi . Applying Lemma 11 to any of them we
15

conclude that that the particular cluster C was superclustered by a nearby sampled cluster, i.e., C 6∈ Ûi ,
contradiction. In the case i = 0, we would have that v has at least c · ln n · deg i unsampled neighbors,
which occurs with probability at most n−c . Hence, by union-bound, every vertex v is explored by at most
c · ln n · deg i explorations, with probability at least 1 − n−(c−1) .
Lemma 10 suggests that the interconnection step of phase i can be carried out in expected O(|E| · deg i )
time. Clearly, the superclustering step can be carried out in just O(|E|) time, and thus the running time of
the interconnection step dominates the running time of phase i. In order to control the running time, we
terminate stage 1 and move on to stage 2 when i0 = ⌊log(κρ)⌋, so that deg i0 ≤ nρ .
Observe also that the superclustering step inserts into the spanner at most O(n) edges (because we
insert a subset of edges of Fi , and Fi is a forest), and by Lemma 10 the interconnection step inserts in
expectation at most O(|P̂i | · deg i · ((1/ǫ)i + Ri )) = O(|P̂i | · deg i · (1/ǫ)i ) edges. (We will soon show that
Ri = O((1/ǫ)i−1 ).) A more detailed argument providing an upper bound on the number of edges inserted
by the interconnection step will be given below.
Lemma 12. For all i, 1 ≤ i ≤ ℓ, for every pair of clusters C ∈ Ûi , C ′ ∈ P̂i at distance at most 21 (1/ǫ)i
from one another, a shortest path between the cluster centers of C and C ′ was inserted into the spanner H.
Moreover, for any pair {v} ∈ Û0 , {v ′ } ∈ P̂0 , such that e = (v, v ′ ) ∈ E, the edge e belongs to H.
Proof. We start with proving the first assertion of the lemma. For some index i, 1 ≤ i ≤ ℓ, and a pair
C ∈ Ûi , C ′ ∈ P̂i of clusters, let rC , rC ′ be the respective cluster centers. Then we have
dG (rC , rC ′ ) ≤ Rad (C) + dG (C, C ′ ) + Rad (C ′ )
≤ dG (C, C ′ ) + 2 · Ri
1
1
≤
(1/ǫ)i + 2 · Ri = δi ,
2
2

and so a shortest path between rC and rC ′ was inserted into the spanner H.
The second assertion of the lemma is guaranteed by the interconnection step of phase 0.
Next we analyze the radii of clusters’ collections P̂i , for i = 1, 2, . . ..
Lemma 13. For i = 0.1, . . . , ℓ, the value of Ri is given by
i−1
X
(1/ǫ)j · 5i−1−j .
Ri =
j=0

Proof. The proof is by induction of the index i. The basis (i = 0) is immediate as R0 = 0. For the induction
hypothesis, note that
Ri+1 = δi + Ri = (1/ǫ)i + 5 · Ri


i−1
X
= (1/ǫ)i + 5 ·  (1/ǫ)j · 5i−1−j 
j=0

=

i
X
(1/ǫ)j · 5i−j ,
j=0

as required.
16

Observe that Lemma 13 implies that for ǫ < 1/10, we have Ri = 5i−1 ·

1/(5ǫ)i −1
1/(5ǫ)−1

≤

1
1−5ǫ

· (1/ǫ)i−1 ≤

2 · (1/ǫ)i−1 . Recall that P̂i = Ŝi−1 . Hence Rad (P̂i ) = Rad (Ŝi−1 ). By inequality (7), we have Rad (P̂i ) ≤
(1/ǫ)i−1 + 5 · Ri−1 = Ri , for all i = 0, 1, . . . , ℓ.
We analyze the number of clusters in collections P̂i in the following lemma.
Lemma 14. For i = 0, 1, . . . , i0 ,
|P̂i | ≤ 2 · n1−

with probability at least 1 − exp{−Ω(n

i
1− 2 κ−1

2i −1
κ

,

(8)

)}.

Proof. The probability that a vertex v ∈ V will be a center of a cluster in P̂i is
i

Thus the expected size of P̂i is n1−(2 −1)/κ , and by Chernoff bound,

Pr[|P̂i | ≥ 2E[|P̂i |]] ≤ exp{−Ω(E[|P̂i |])} = exp{−Ω(n1−

Since for ρ < 1/2 and i ≤ i0 = ⌊log(κρ)⌋, we have n1−

2i+1 −1
κ

i+1
1− 2 κ −1

Qi−1

2i −1
κ

j=0 1/deg j

i

= n−(2 −1)/κ .

)} .

≥ n1−2ρ = ω(log n), we conclude that

). Hence in particular, |P̂i0 +1 | = O(n1−ρ+1/κ ), whp.
whp for all 0 ≤ i ≤ i0 , |P̂i+1 | = |Ŝi | = O(n
The total expected running time of the first stage is at most
O(|E|)

i0
X
i=1

deg i = O(|E| · n

2i0
κ

) = O(|E| · nρ ) .

Since each superclustering step inserts at most O(n) edges into the spanner, the overall number of edges
inserted by the i0 superclustering steps of stage 1 is O(n · i0 ) = O(n · log(κρ)). The expected number of
edges added to the spanner by the interconnection step of phase i is at most
O(|P̂i | · deg i · (1/ǫ)i ) = O(n1−

2i −1
κ

2i

· (1/ǫ)log(κρ) · n κ ) = O(n1+1/κ · (1/ǫ)log(κρ) ) .

Next we describe stage 2 of the algorithm, i.e., phases i = i0 +1, i0 +2, . . . , i1 , where i1 = i0 +⌈ κ+1
κρ ⌉−2.
All these phases are executed with the same fixed degree parameter deg i = nρ . On the other hand, the
distance threshold keeps growing in the same steady rate as in stage 1, i.e., it is given by δi = (1/ǫ)i + 4Ri .
The sets P̂i0 +1 , P̂i0 +2 , . . . , P̂i1 on which phases i0 + 1, i0 + 2, . . . , i1 , respectively, operate are defined by
P̂i0 +i = Ŝi0 +i−1 , for 1 ≤ i ≤ i1 − i0 .
Lemma 13 keeps holding for these additional i1 − i0 phases, i.e.,
Rad (P̂i ) ≤ Ri ≤ 2 · (1/ǫ)i−1 .
(We assume all through that ǫ < 1/10.)
Also, for every pair of clusters C ∈ Ûi and C ′ ∈ P̂i which are at distance at most 12 (1/ǫ)i from one
another, their centers are interconnected in the spanner by a shortest path between them.
In addition, for every i ∈ [i0 , i1 ], the expected size of P̂i+1 is
E[|P̂i+1 |] = n ·

i
Y

j=0

1/deg j ≤ n1+1/κ−(i+1−i0 )ρ .
17

By Chernoff bound, for every such i, with probability at least 1 − exp{−Ω(nρ )}, we have
|P̂i+1 | = |Ŝi | ≤ 2 · n1+1/κ−ρ−(i−i0 )ρ .
Assuming that nρ = ω(1), we conclude that whp
|P̂i1 +1 | = |Ŝi1 | ≤ O(n1+1/κ−(i1 +1−i0 )ρ ) = O(n

⌉−1)ρ
1+1/κ−(⌈ κ+1
κρ

) = O(nρ ) .

(9)

log n
(For the assumption above to hold we will need to assume that ρ ≥ log
2 log n , say. We will show soon that
this assumption is valid in our setting.)
The time required to perform these ⌈ κ+1
κρ ⌉ − 2 ≤ 1/ρ additional phases is expected to be at most
ρ
O(|E| · deg i · (1/ρ)) = O(|E|n /ρ).
The final collection of clusters P̂i1 +1 is created by setting P̂i1 +1 = Ŝi1 .
We will next bound the expected number of edges inserted into the spanner during stage 2 of the algorithm. Each of the forests Fi , i ∈ [i0 + 1, i1 ], created during the superclustering steps contributes at
most n − 1 edges. The interconnection step of phase i + i0 contributes in expectation at most O(|P̂i+i0 | ·
deg i+i0 · (1/ǫ)i ) ≤ O(n1+1/κ−iρ · (1/ǫ)log(κρ)+i ) edges. Assuming that 1/ǫ < nρ /2, this becomes a
geometric progression, so the overall expected number of edges inserted into the spanner on stage 2 is
O(n1+1/κ · (1/ǫ)log(κρ) ). (We will show the validity of this assumption in the end of this section.)
Finally, we describe the concluding phase of the algorithm, i.e., phase ℓ = i1 + 1. In this phase we skip
the superclustering step (as the number of clusters is already sufficiently small), and proceed directly to the
interconnection step.
On this step each of the cluster centers rC for C ∈ P̂ℓ conducts a BFS exploration in G to depth
1
1
ℓ
δ
2 ℓ = 2 (1/ǫ) + 2Rℓ . (Essentially, we define Ûℓ = P̂ℓ , and perform the usual interconnection step of the
algorithm.) By (9), the number of edges inserted by this step into the spanner is whp only O(|P̂ℓ |2 ·(1/ǫ)ℓ ) =
O(|P̂i1 +1 |2 ·(1/ǫ)i1 +1 ) = O(n2ρ ·(1/ǫ)log(ρκ)+1/ρ ). Recall that we assume that ρ < 1/2. Hence this number
of edges is sublinear in n.
Hence the overall expected number of edges in the spanner is |H| = O(n1+1/κ · (1/ǫ)log(κρ) ). Observe
also that the running time of the last phase is O(|E| · nρ ). Hence the overall expected running time of the
ρ /ρ). It remains to analyze the stretch of the resulting spanner H.
algorithm is O(|E|n
Sℓ
Let Û = j=0 Ûj . Observe that every singleton cluster {v} ∈ P̂0 is associated with exactly one cluster
of Û , i.e., Û is a partition of V . Note that Rad (Û0 ) = 0, Rad (Û1 ) ≤ 1 = R1 , and for every j ∈ [ℓ], we have
Rad (Ûj ) ≤ Rad (P̂j ) ≤ Rj ≤ 2 · (1/ǫ)j−1 . Denote c = 2. Recall also (see Lemma 12) that for j ≥ 1, for
every pair of clusters C, C ′ ∈ Ûj at distance at most 21 (1/ǫ)j from one another, a shortest path between the
cluster centers of this pair of clusters in G was added to the spanner H. Moreover, neighboring clusters of
Û0 are also interconnected by a spanner edge.

Lemma 15. Consider a pair of indices 0 ≤ j < i ≤ ℓ, and a pair of neighboring (in G) clusters C ′ ∈ Ûj ,
C ∈ Ûi , and a vertex w′ ∈ C ′ and the center r of C. Then the spanner H contains a path of length at most
3Rad (Ûj ) + 1 + Rad (Ûi ) between w′ and r.
Proof. Let (z ′ , z) ∈ E ∩ (C ′ × C) be an edge connecting this pair of clusters. There exists a subcluster
C ′′ ⊆ C, C ′′ ∈ P̂j such that z ∈ C ′′ . Hence the interconnection step of phase j inserted a shortest path
π(r ′ , r ′′ ) in G between the cluster centers r ′ of C ′ and r ′′ of C ′′ into the spanner H. Note that the distance
between r ′ , r ′′ is at most 1 + 2Rad (P̂j ) ≤ 1 + 4(1/ǫ)j−1 < 1/2 · (1/ǫ)j , since we assume ǫ < 1/10.
Hence a path between w′ and r in H can be built by concatenating a path π(w′ , r ′ ) between w′ and r ′ in

18

the spanning tree T (C ′ ) of C ′ with the path π(r ′ , r ′′ ) in H, and with the path π(r ′′ , r) in the spanning tree
T (C) of C. (Note that both r ′′ and r belong to C.) Its length is at most
|π(w′ , r ′ )| + |π(r ′ , r ′′ )| + |π(r ′′ , r)| ≤ Rad (C ′ ) + (Rad (C ′ ) + 1 + Rad (C ′′ )) + Rad (C)
≤ 3Rad (Ûj ) + 1 + Rad (Ûi ) .

Now we are ready to analyze the stretch of our spanner.
Lemma 16. Suppose ǫ ≤ 1/10. Consider a pair of vertices u, v ∈ V . Fix a shortest path π(u, v) between
them in G, and suppose
that for some index i ∈ [0, ℓ], all vertices of π(u, v) are clustered in the set Û (i)
Si
(i)
defined by Û = j=0 Ûj . Then
dH (u, v) ≤ (1 + 16c · ǫ · i)dG (u, v) + 4

i
X
j=1

Rj · 2i−j .

Proof. The proof is by induction on i. For the induction basis i = 0, observe that all vertices of π(u, v) are
clustered in Û0 , and thus all edges of π(u, v) are inserted into the spanner on phase 0. Hence dH (u, v) =
dG (u, v).
For the induction step, consider first a pair of vertices x, y such that |π(x, y)| ≤ 21 (1/ǫ)i , and V (π(x, y)) ⊆
Û (i) . Let z1 and z2 be the leftmost and the rightmost Ûi -clustered vertices in π(x, y), if exist. (The case
when both these vertices exist is the one where the largest stretch is incurred; cf. [EP04].) Let C1 , C2 ∈ Ûi
be their respective clusters, i.e., z1 ∈ C1 , z2 ∈ C2 . Let w1 (respectively, w2 ) be the neighbor of z1 (resp.,
z2 ) on the subpath π(x, z1 ) (resp., π(z2 , y)) of π(x, y), and denote by C1′ and C2′ the respective clusters of
w1 and w2 . Observe that C1′ , C2′ ∈ Û (i−1) .
Denote r1 and r2 the cluster centers of C1 and C2 , respectively. The spanner H contains a path of length
at most dG (r1 , r2 ) between these cluster centers. Also, by Lemma 15, since C1′ and C1 are neighboring
clusters, the spanner H contains a path of length at most 3Rj + 1 + Ri ≤ 2Ri + 1 between w1 and r1 , and
a path of at most this length between r2 and w2 . (For ǫ < 1/10, 3Rj ≤ Ri , for all j < i.) Observe also
that the subpaths π(x, w1 ) and π(w2 , y) of π(x, y) have all their vertices clustered in Û (i−1) , and thus the
induction hypothesis is applicable to these subpaths.
Hence
dH (x, y) ≤ dH (x, w1 ) + dH (w1 , r1 ) + dH (r1 , r2 ) + dH (r2 , w2 ) + dH (w2 , y)
i−1
X
Rj · 2i−1−j + 2Ri + 1 + (dG (C1 , C2 ) + 2Ri )
≤ (1 + 16c · ǫ(i − 1))dG (x, w1 ) + 4
j=1

+2Ri + 1 + (1 + 16c · ǫ(i − 1)) · dG (w2 , y) + 4

i−1
X
j=1

Rj · 2i−1−j

= (1 + 16c · ǫ(i − 1)) · (dG (x, w1 ) + dG (w2 , y)) + dG (C1 , C2 ) + 4Ri + 2 + 8

i−1
X
j=1

Rj · 2i−1−j .

Note also that
dG (x, y) = dG (x, w1 ) + 1 + dG (z1 , z2 ) + 1 + dG (w2 , y) ≥ dG (x, w1 ) + dG (C1 , C2 ) + 2 + dG (w2 , y).
19

Hence
i−1
X

dH (x, y) ≤ (1 + 16c · ǫ(i − 1))dG (x, y) + 4Ri + 8
= (1 + 16c · ǫ(i − 1))dG (x, y) + 4

i
X
j=1

j=1

Rj · 2i−1−j

Rj · 2i−j .

Now consider a pair of vertices u, v such that all vertices of π(u, v) are clustered in Û (i) , without any
restriction on |π(u, v)|. We partition π(u, v) into segments π(x, y) of length exactly ⌊ 21 (1/ǫ)i ⌋, except
maybe one segment of possibly smaller length. Inequality (10) applies to all these segments. Hence
dH (u, v) ≤ (1 + 16c · ǫ(i − 1))dG (u, v) + 4
≤

1 + 16c · ǫ(i − 1) +
8

Pi

4

Pi

i
X
j=1

i
X
dG (u, v)
Rj · 2i−j
⌋
+
4
i
2 (1/ǫ) − 1
j=1

Rj · 2i−j ⌊ 1

i−j
j=1 Rj · 2
1
i
2 (1/ǫ) − 1

!

dG (u, v) + 4

i
X
j=1

Rj · 2i−j .

Rj 2i−j

j=1
≤ 16c · ǫ. Recall that for every j, we have Rj ≤ c · (1/ǫ)j−1 . Since
It remains to argue that (1/ǫ)
i −2
1/ǫ ≥ 10, the left-hand-side is at most

10c · ǫ

i

i
X

j−1

(1/ǫ)

j=1

i−j

·2

i−1
i
X
X
i−j
(2ǫ)h ≤ 16c · ǫ .
(2ǫ)
= 10c · ǫ
= 10c · ǫ
j=1

h=0

Observe that (as ǫ ≤ 1/10), we have
i
X
j=1

i−j

Rj · 2


i 
i
X
X
1 j−1
j−1
i−j
i−1
(1/ǫ)
·2
= c·2
·
≤ c
2ǫ
j=1

j=1

= c · 2i−1
= c·ǫ·

1
2

i−1 
X
j=0

1
2ǫ

j

(1/2ǫ)i − 1
(1/2ǫ) − 1
 i−1 !
1
= O
.
ǫ

= c · 2i−1

· (1/ǫ)i − 2i−1
1
2 −ǫ

Note also that the condition of the last lemma holds with i = ℓ for every pair u, v ∈ V of vertices. Hence
Corollary 17. For every pair u, v ∈ V ,
dH (u, v) ≤ (1 + 16c · ℓ · ǫ)dG (u, v) + O((1/ǫ)ℓ−1 ) .
Recall that the spanner H contains, whp, |H| = O(n1+1/κ ·log n·(1/ǫ)log(κρ) +n·log n·(1/ǫ)log(κρ)+1/ρ )
ρ
edges, and the expected running time required to construct it is O(|E|
also that ℓ = i
1+1 ≤
 · n /ρ). Recall
log κ+1/ρ

log
κ+1/ρ
. The
log(κρ) + 1/ρ + 1. Set now ǫ′ = 16c · ℓ · ǫ. We obtain stretch 1 + ǫ′ , O
ǫ′

condition ǫ < 1/10 translates now to ǫ′ ≤ 1.6c(log(κρ) + 1/ρ). We will replace it by a simpler stronger
condition ǫ ≤ 1.
20

Corollary 18. For any parameters 0 < ǫ ≤ 1, κ ≥ 2, and ρ > 0, and any n-vertex unweighted graph
log κ

·
G = (V, E), our algorithm computes a (1+ǫ, β)-spanner with expected number of edges O log κ+1/ρ
ǫ
n1+1/κ , in expected time O(|E| · nρ /ρ), where


O(log κ + 1/ρ) log κ+1/ρ
β=
.
ǫ

A particularly useful setting of parameters is ρ = 1/ log κ. Then we get a spanner with expected


log κ
2 log κ
1
O logǫ κ
· n1+1/κ edges, in time O(|E| · n log κ · log κ), and β = O logǫ κ
.
We remark that it makes no sense to set ρ < 1/κ, as the resulting parameters will be strictly worse than
when ρ = 1/κ. Also our assumptions that ρ > log log n/(2 log n) and 16c · ℓ/ǫ < nρ /2 are justified, as
otherwise we get β ≥ n, so a trivial spanner will do.

3.2 An Improved Variant of the Algorithm
In this section we show that the leading coefficient O((log κ + 1/ρ)/ǫ)log κ of n1+1/κ in the size of the
spanner can be almost completely eliminated at essentially no price. We also devise here yet sparser constructions of emulators.
For i = 0, 1, . . . , ℓ, denote by Ni = |P̂i | the expected number of clusters which take part in phase i.
 ′ i
Recall also that the interconnection step of the ith phase contributes Ni · deg i · cǫℓ edges in expectation,

where ℓ is the total number of steps, and c′ is a universal constant. Note that the contribution of the interconnection step dominates the contribution of the superclustering step in the current variant of the algorithm,
and it will still be the case after the modification that we will now introduce. Hence we will now focus on
decreasing the number of edges contributed by the interconnection steps.
We keep the structure of the algorithm intact, and have the values of distance thresholds δi unchanged.
The only change is in the degree sequence deg 0 , deg 1 , . . . of degree parameters used in phases 0, 1, . . .,
respectively. Next, we describe our new setting of these parameters for stage 1 of the algorithm (i.e., phases
i, 1 ≤ i ≤ i0 ). In the case that κ ≥ 16 let a = log log κ, otherwise, when κ < 16, let a = 2. Define
i
i0 = min{⌊log(aκρ)⌋, ⌊κρ⌋}, and for i = 0, 1, . . . , i0 let deg i = n(2 −1)/(aκ)+1/κ . We now have that for
i ≤ i0 + 1,
i−1
Y
2i −1−i
i
1/deg j = n1− aκ − κ ,
Ni = n
j=0

aκρ−1−(i0 +1)

i0 +1

− κ
aκ
and in particular, when i0 = ⌊log(aκρ)⌋ we have Ni0 +1 ≤ n1−
≤ n1−ρ (since a ≥ 2 and
i0 +1
i0 ≥ 1). Whenever i0 = ⌊κρ⌋ we also have Ni0 +1 ≤ n1− κ ≤ n1−ρ . Additionally, we always have

Ni · deg i = n1−

2i −1−i
− κi
aκ

·n

We restrict ourselves to the case that

2i −1
+ κ1
aκ

i

= n1+ aκ −

i−1
κ

.

1
c′ ℓ
(10)
≤ n 2κ /2 ,
ǫ
c0 ·log n
, for a sufficiently small constant c0 . Now the expected number of edges
which holds whenever κ ≤ log(ℓ/ǫ)
inserted at phase i ≤ i0 is at most
!i
 ′ i
1/(2κ)
i−1
i
1
cℓ
n
≤ n1+ 2κ − κ ·
Ni · deg i ·
= n1+ κ /2i .
(11)
ǫ
2

21

Thus the total expected number of edges inserted in the first stage is O(n1+1/κ ). The second stage proceeds
by setting deg i0 +1 = nρ/2 , and in all subsequent phases i0 + i, with i = 2, 3, . . . , i1 − i0 , we have deg i = nρ
as before. The ”price” for reducing the degree in the first phase of stage two is that the number of phases i1
may increase by an additive 1. It follows that Ni0 +1 · deg i0 +1 ≤ n1−ρ/2 . For i ≥ 2, at phase i0 + i we have
Ni0 +i ≤ n1−3ρ/2−(i−2)ρ . We set i1 = ⌊1/ρ⌋, so that Ni1 +1 ≤ nρ/2 , and whp we have that Ni1 +1 ≤ 2nρ/2 .
We calculate
Ni0 +i · deg i0 +i ≤ n1−ρ/2−(i−2)ρ .
Note that i0 /(2κ) ≤ ρ/2, which holds since i0 ≤ ⌊κρ⌋. Hence the condition (10) implies that
i0
≤ n 2κ ≤ nρ/2 . The total expected number of edges inserted at phase i0 + 1 is at most

(c′ ℓ/ǫ)i0

Ni0 +1 · deg i0 +1 ·



c′ ℓ
ǫ

i0 +1

≤ n1−ρ/2 · nρ/2 ·

c′ ℓ
≤ n1+1/κ .
ǫ

The expected contribution of phase i0 + i for i ≥ 2 is at most
Ni0 +i · deg i0 +i ·



c′ ℓ
ǫ

i0 +i

≤ n1−ρ/2−(i−2)ρ · nρ/2 · ni/(2κ) /2i ≤ n1+1/κ /2i ,

(12)

where the last inequality uses that ρ ≥ 1/κ (which we may assume w.l.o.g). This implies that the expected
number of edges in all these ⌊1/ρ⌋ phases is O(n1+1/κ ).
Ω(log n)
c0 ·log n
≥
The upper bound on κ under which this analysis was carried out is log(ℓ/ǫ)
.9
log(1/ǫ)+log(1/ρ)+log (3) n
We summarize this discussion with the following theorem.
c·log n
log(1/ǫ)+log(1/ρ)+log (3) n
= O( 1ǫ (log κ +

Theorem 3. For any unweighted graph G = (V, E) with n vertices , 0 < ǫ < 1/10, 2 ≤ κ ≤

for a constant c, and 1/κ ≤ ρ < 1/2, our algorithm computes a (1 + ǫ, β)-spanner with β
(3)
1/ρ))log κ+1/ρ+max{1,log κ} and expected number of edges O(n1+1/κ ). The expected running time is
O(|E| · nρ /ρ).

Note that the sparsest this spanner can be is O(n log log n), and at this level of sparsity its β =
O(log log n + 1/ρ)log log n+1/ρ . (To get this bound we set ǫ > 0 to be an arbitrary small constant, and
n
κ = c0 log
.)
log(3) n
This is sparser than the state-of-the-art efficiently-computable
sparsest (1+ ǫ, β)-spanner due to [Pet10],
√
1+ 5
φ
which has O(n(log log n) ) edges, where φ = 2 is the golden ratio. Moreover, this spanner has a
smaller β than the one of [Pet10] in its sparsest level. Denoting the latter as βP et , it holds that βP et ≈
O(log κ)1.44 log κ+1/ρ , i.e., for every setting of the time parameter ρ, the exponent of our β is smaller than
that of βP et .
3.2.1

Sparse Emulator

Finally, we note that if one allows an emulator instead of spanner, then we can decrease the size all the
way to O(n) when κ = log n. To achieve this, we insert single ”virtual” edges instead of every path (of
length (c′ ℓ/ǫ)i ) between every pair of cluster centers that we choose to interconnect on phase i, for every
i. Analogously, in the superclustering step we also form a supercluster around a center rC of a cluster C
by adding virtual edges (rC , rC ′ ) for each cluster C ′ associated with C. The weight of each such edge is
9

We denote log(k) n as the iterated logarithm function, e.g. log(3) n = log log log n.

22

defined by ω(rC , rC ′ ) = dG (rC , rC ′ ). The condition (10) was required to obtain converging sequences at
(11) and (12), but without the (c′ ℓ/ǫ)i terms, the number of edges already forms a converging sequence at
each stage.
Moreover, one can also use for emulators a shorter degree sequence than the one we used for spanners,
and as a result to save the additive term of log(3) κ in the exponent of β. Specifically, one can set deg i =
i
Q
2i
i
1− 2 κ−1
·
n κ /22 −1 , for each i = 0, 1, . . . , i0 = ⌊log(κρ)⌋. As a result we get Ni = n · i−1
j=0 1/deg j = n
i

22 −1−i , and thus the expected number of edges inserted at phase i ≤ i0 is at most
Ni · deg i = n1+1/κ /2i .

As before, when the first stage concludes, we run one phase with deg i0 +1 = nρ/2 , and all subsequent phases
with deg i = nρ . To bound the expected number of edges added at phase i0 + 1 we need to note that
i +1
22 0 ≤ 22κρ ≤ nρ/2 as long as κ ≤ (log n)/4. (The latter can be assumed without affecting any of the
2i0 +1 −1

i +1

parameters by more than a constant factor). It follows that Ni0 +1 · deg i0 +1 = n1− κ · 22 0 −1−(i0 +1) ·
nρ/2 ≤ n1+1/κ . In the remaining phases Ni0 +i ≤ n1+1/κ−(i−1)ρ for i ≥ 2, and the contribution of these
phases is a converging sequence. We conclude the discussion with the following theorem.

Theorem 4. For any unweighted graph G = (V, E) with n vertices, and for any parameters 0 < ǫ ≤
1, 2 ≤ κ ≤ (log n)/4, 1/κ ≤ ρ < 1/2, our algorithm computes a (1 + ǫ, β)-emulator with β =
log κ+1/ρ

and expected number of edges O(n1+1/κ ). The expected running time is O(|E| ·
O log κ+1/ρ
ǫ
nρ /ρ).
log log n+1/ρ

In particular, the algorithm produces a linear-size (1+ǫ, β)-emulator with β = O log logǫn+1/ρ
within this running time.

3.3 Distributed and Streaming Implementations
In this section we provide efficient distributed and streaming algorithms for constructing sparse (1 + ǫ, β)spanners. The distributed algorithm works in the CONGEST model.
To implement phase 0, each vertex selects itself into S0 with probability n−1/κ , i.a.r.. In distributed
model vertices of S0 send messages to their neighbors. Each vertex u that receives at least one message,
picks an origin v ∈ S0 of one of these messages, and joins the cluster centered at v. It also sends negative
acknowledgements to all its other neighbors from S0 . All unclustered vertices z insert all edges incident on
them into the spanner.
It is also straightforward to implement this in O(1) passes in the streaming model.
Each consecutive phase is now also implemented in a straightforward manner, i.e., BFS explorations
to depth δi in the superclustering steps are implemented via broadcasts and convergecasts in the distributed
model, and by δi passes in the streaming model. In the interconnection steps, however, we need to implement
many BFS explorations which may explore the same vertices. However, by Lemma 11 every vertex is
explored on phase i by up to O(degi · log n) explorations
P whp, it follows that in distributed setting this step
requires, whp, O(deg i · log n · δi ) time. Also note that i δi = O(β).
In the streaming model we have two possible tradeoffs. The first uses expected O(n · deg i ) space to
maintain for each vertex v the BFS parents and distance estimates, and requires just δi passes. To see that
such space suffices, recall that the expected number of explorations which visit any vertex v is at most deg i ,
by Lemma 10. Whp, the space is O(n · deg i · log n) = O(n1+ρ · log n).
23

The second option in the streaming algorithm is to divide the interconnection step of phase i to c ·
deg i · log n subphases, for a sufficiently large constant c. On each subphase each exploration source, which
was not sampled on previous subphases, samples itself i.a.r. with probability 1/deg i . Then the sampled
exploration sources conduct BFS explorations to depth δi /2. For every vertex v, the expected number of
explorations that traverse it on each subphase is O(log n). Moreover, by Chernoff’s inequality, whp, no
vertex v is ever traversed by more than O(log n) explorations. (Here we take a union-bound on all vertices,
all phases, and all subphases. The bad events are that some vertex is traversed by more than twice its
expectation explorations on some subphase.) Hence each subphase requires O(δi ) passes, and whp, the
space requirement is O(n log n), plus the size of the spanner. After c · deg i · log n subphases, whp, each
exploration source is sampled on at least one of the subphases, and so the algorithm performs all the required
explorations.
Finally, the stretch analysis of distributed and streaming variants of our algorithm remains the same as
in the centralized case.
Hence we obtain the following distributed and streaming analogues of Theorem 3.
Theorem 5. For any unweighted graph G = (V, E) with n vertices , 0 < ǫ < 1/10, 2 ≤ κ ≤

c·log n
log(1/ǫ)+log(1/ρ)+log (3) n

for a constant c, and 1/κ ≤ ρ < 1/2, our distributed algorithm (CONGEST model) computes a (1 + ǫ, β)(3)
spanner with β = O( 1ǫ (log κ + 1/ρ))log κ+1/ρ+max{1,log κ} and expected number of edges O(n1+1/κ ).
The required number of rounds is whp O(nρ /ρ · β · log n).
Our streaming algorithm computes a spanner with the above properties, in either: O(n log n + n1+1/κ )
expected space and O(nρ /ρ · log n · β) passes, or using O(n1+ρ · log n) space, whp, and O(β) passes.
The streaming algorithm described above can also be modified to provide a (1 + ǫ, β)-emulator as in
Theorem 4, within the same pass and space complexities.

4 Applications
In this section we describe applications of our improved constructions of spanners and emulators to computing approximate shortest paths for a set S × V of vertex pairs, for a subset S ⊆ V of designated sources.

4.1 Centralized Setting
We start with the centralized setting. Here our input graph G = (V, E) is unweighted, and we construct a
(1 + ǫ, β)-emulator H of G with O(n1+1/κ ) edges, in expected time O(|E| · nρ /ρ), where
β=O



log κ + 1/ρ
ǫ

log κ+1/ρ

.

(13)

Observe that all edge weights in H are integers in the range [1, β]. We round all edge weights up to the
closest power of 1 + ǫ. Let H ′ be the resulting emulator. Note that for any pair u, v of vertices, we have
dG (u, v) ≤ dH (u, v) ≤ dH ′ (u, v) ≤ (1 + ǫ)dH (u, v)
≤ (1 + ǫ)2 dG (u, v) + (1 + ǫ)β .

For a sufficiently small ǫ, (1 + ǫ)2 ≤ 3ǫ, and we rescale ǫ′ = 3ǫ. As a result the constant factor hidden by the
O-notation in the basis of β’s exponent grows, but other than that H ′ has all the properties of the emulator
24

H. Also, it employs only




log β
(log 1/ǫ + log(log κ + 1/ρ)) · (log κ + 1/ρ)
t=O
=O
ǫ
ǫ
different edge weights. Hence a single-source shortest path computation in H can be performed in O(|H| +
n log t) = O(n1+1/κ + n(log(1/ǫ) + log(log κ + 1/ρ))) time [OMSW10]. (See also [KMP11], Section 5.)
Hence computing S × V (1 + ǫ, β)-approximate shortest distances requires O(|E| · nρ /ρ + |S|(n1+1/κ +
n(log(1/ǫ) + log(log κ + 1/ρ)))) time.
Theorem 6. For any n, and for any parameters 0 < ǫ ≤ 1, 2 ≤ κ ≤ (log n)/4, 1/κ ≤ ρ ≤ 1/2, and any
n-vertex unweighted graph G = (V, E) with a set S ⊆ V , our algorithm computes (1 + ǫ, β)-approximate
S × V shortest distances in the centralized model in expected O(|E| · nρ /ρ + |S|(n1+1/κ + n(log(1/ǫ) +
log(log κ + 1/ρ)))) time, where β is given by (13).
If one is interested in actual paths rather than just in distances, then one can use our (1 + ǫ, β)-spanner
with
(3)


log κ + 1/ρ log κ+1/ρ+max{1,log κ}
β=O
,
(14)
ǫ
O(log n)
and O(n1+1/κ ) edges, but restricting κ ≤ log(1/ǫ)+log(1/ρ)+log
(3) . After computing the spanner H with
n
these properties, we conduct BFS explorations on H originated at each vertex of S. The overall running
time becomes O(|E| · nρ /ρ + |S| · n1+1/κ ).

Corollary 19. For any n, and for any parameters 0 < ǫ ≤ 1, κ ≤

O(log n)
,
log(1/ǫ)+log(1/ρ)+log (3) n

1/κ ≤ ρ ≤ 1/2,

and any n-vertex unweighted graph G = (V, E), our algorithm computes (1 + ǫ, β)-approximate S × V
shortest paths in the centralized model in expected O(|E| · nρ /ρ + |S| · n1+1/κ ) time, with β given by (14).
A useful setting of parameters is ρ = log1 κ . Then the running time of our algorithms from Theorem 6
and Corollary 19 become respectively O(|E| · n1/ log κ · log κ + |S|(n1+1/κ + n(log 1/ǫ + log log κ))) and
O(|E| · n1/ log κ · log κ + |S| · n1+1/κ ) (we note that the former has smaller β given by (13), while the latter
has slightly larger β given by (14)).
The algorithm of Corollary 19 always outperforms the algorithm which can be derived by using the
spanner of [Pet10] within the same scheme. Specifically, the running time of that algorithm is at least
Õ(|E|nρ ) + O(|S| · (n1+1/κ + n( logǫ κ )φ )), and the additive error βP et there is given by
βP et = O



log κ + 1/ρ
ǫ

√

logφ κ+1/ρ

,

where φ = 1+2 5 is the golden ratio. So βP et is typically polynomially larger than the additive error β in
our algorithm, e.g., for ρ = 1/ log κ we have βP et ≈ β 1.22 . (Setting ρ to be smaller than 1/ log κ makes less
sense, because then the additive errors β and βP et deteriorate. At any rate, as ρ tends to 0, the two estimates
approach each other.) Also, in the bound of [Pet10] there is a term of |S| · n · ( logǫ κ )φ )), which does not
occur in our construction.

25

4.2 Streaming Setting
In this section we show how efficient constructions of spanners and emulators for an unweighted graph G
in the streaming setting can be used for efficient computation of approximate shortest paths.
First, one can use O(nρ /ρ · log n · β) passes and expected space O(n1+1/κ + n · log n) to construct an
(1 + ǫ, β)-emulator H with β = (O(log κ + 1/ρ)/ǫ)log κ+1/ρ . One can now compute V × V (1 + ǫ, β)approximate shortest distances in G by computing exact V ×V shortest distances in H, using the same space
and without additional passes. (Observe that we do not store the output, as its size is larger than the size of
H.) In particular, one can use here space of O(n · log n), and have β = (O(log log n + 1/ρ)/ǫ)log log n+1/ρ .
O(

log n

)

1
log log n passes, β = O( log log n )2 log log n .
It is also possible to set here ρ = log log
n , and obtain 2
ǫ
Another option is to use space O(n1+ρ ·log n), whp, and O(β) passes for constructing the same emulator
H. Again given the emulator we can compute V × V approximate shortest distances in G by computing
shortest distances in H offline.

Corollary 20. For any n and any parameters 0 < ǫ ≤ 1, 2 ≤ κ ≤ (log n)/4, 1/κ ≤ ρ ≤ 1/2, and any
n-vertex unweighted graph G, our streaming algorithm computes (1 + ǫ, β)-approximate shortest distances
for V × V with β given by (13). It uses in expectation either O(nρ /ρ · log n · β) passes and expected space
O(n1+1/κ + n · log n) or O(β) passes and space O(n1+ρ · log n), whp.
If the actual paths rather than just distances are needed, then we compute a (1 + ǫ, β)-spanner H with
β given by (14) and with expected O(n1+1/κ ) edges (with the restriction on κ as above). Then we compute
V × V (1 + ǫ, β)-approximate shortest paths in H offline, using space O(H|).
Corollary 21. For any n, κ, ǫ, ρ and G as in Corollary 19, a variant of our streaming algorithm computes
(1 + ǫ, β)-approximate shortest paths for V × V with β given by (14). It uses either O(nρ /ρ · log n · β)
passes and expected space O(n1+1/κ + n · log n) or O(β) passes and space O(n1+ρ · log n), whp.
If one is interested only in S × V paths or distances, then it is possible to eliminate the additive term of
β by using O(|S| · β/ǫ) additional passes. These passes are used to compute exactly distances between pairs
(s, v) ∈ S × V , with dG (s, v) ≤ β/ǫ. The overall number of passes becomes O(|S| · β/ǫ + nρ /ρ · log n · β),
|S|
log log n
and space O(n1+1/κ + n · log n). Whenever |S| ≥ n1/κ log n, we can set ρ = log
log n − log n , and obtain
the following corollary.
Corollary 22. For any n, ǫ, ρ, κ and G as in Corollary 20, and any set S ⊆ V of size at least |S| ≥
n1/κ log n, a variant of our streaming algorithm computes (1 + ǫ)-approximate shortest distances for S × V
in expected
log n
 
log κ+
log |S|−log log n
1
|S|
log n
(15)
·O
log κ +
ǫ
ǫ
log |S|−log log n
passes, and space O(n1+1/κ + n · log n). To compute actual paths we have similar complexities10 , but one
needs to restrict κ as in Corollary 19.

Observe that for a constant ǫ > 0 and |S| = nΩ(1) , we can take a constant κ, so the number of passes
is O(|S|). One can also get for |S| = 2Ω(log n/ log log n) , a streaming algorithm for computing (1 + ǫ)approximate shortest paths for S × V by setting κ = c log n/ log log log n, and obtaining O(|S|/ǫ) ·
n 2 log log n
O( log log
)
passes and space O(n log n).
ǫ
10

Though there is an additional additive term of log(3) κ in the exponent in (15).

26

References
[AB16]

Amir Abboud and Greg Bodwin. The 4/3 additive spanner exponent is tight. In Proceedings of
the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge,
MA, USA, June 18-21, 2016, pages 351–361, 2016.

[ABCP93] Baruch Awerbuch, Bonnie Berger, Lenore Cowen, and David Peleg. Near-linear cost sequential
and distribured constructions of sparse neighborhood covers. In 34th Annual Symposium on
Foundations of Computer Science, Palo Alto, California, USA, 3-5 November 1993, pages
638–647, 1993.
[ABN11]

Ittai Abraham, Yair Bartal, and Ofer Neiman. Advances in metric embedding theory. Advances
in Mathematics, 228(6):3026 – 3126, 2011.

[ABP17]

Amir Abboud, Greg Bodwin, and Seth Pettie. A hierarchy of lower bounds for sublinear
additive spanners. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on
Discrete Algorithms, pages 568–576, 2017.

[ACIM99]

Donald Aingworth, Chandra Chekuri, Piotr Indyk, and Rajeev Motwani. Fast estimation of
diameter and shortest paths (without matrix multiplication). SIAM J. Comput., 28(4):1167–
1181, 1999.

[ADD+ 93] I. Althöfer, G. Das, D. Dobkin, D. Joseph, and J. Soares. On sparse spanners of weighted
graphs. Discrete Comput. Geom., 9:81–100, 1993.
[ADF+ 17] Stephen Alstrup, Soren Dahlgaard, Arnold Filtser, Morten Stockel, and Christian Wulff-Nilsen.
Personal communication, 2017.
[AHL02]

Noga Alon, Shlomo Hoory, and Nathan Linial. The moore bound for irregular graphs. Graphs
and Combinatorics, 18(1):53–57, 2002.

[AN12]

Ittai Abraham and Ofer Neiman. Using petal-decompositions to build a low stretch spanning
tree. In STOC, pages 395–406, 2012.

[AP92]

B. Awerbuch and D. Peleg. Routing with polynomial communication-space tradeoff. SIAM J.
Discrete Mathematics, 5:151–162, 1992.

[Awe85]

B. Awerbuch. Complexity of network synchronization. J. ACM, 4:804–823, 1985.

[Bar96]

Yair Bartal. Probabilistic approximations of metric spaces and its algorithmic applications. In
FOCS, pages 184–193, 1996.

[Bar98]

Yair Bartal. On approximating arbitrary metrices by tree metrics. In Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, STOC ’98, pages 161–168, New York,
NY, USA, 1998. ACM.

[Bar04]

Yair Bartal. Graph decomposition lemmas and their role in metric embedding methods. In
Algorithms - ESA 2004, 12th Annual European Symposium, Bergen, Norway, September 1417, 2004, Proceedings, pages 89–97, 2004.

27

[Bas08]

S. Baswana. Streaming algorithm for graph spanners - single pass and constant processing
time per edge. Inf. Process. Lett., 106(3):110–114, 2008.

[BCE05]

Béla Bollobás, Don Coppersmith, and Michael Elkin. Sparse distance preservers and additive
spanners. SIAM J. Discrete Math., 19(4):1029–1055, 2005.

[BGK+ 14] Guy E. Blelloch, Anupam Gupta, Ioannis Koutis, Gary L. Miller, Richard Peng, and Kanat
Tangwongsan. Nearly-linear work parallel SDD solvers, low-diameter decomposition, and
low-stretch subgraphs. Theor. Comp. Sys., 55(3):521–554, October 2014.
[BKMP10] Surender Baswana, Telikepalli Kavitha, Kurt Mehlhorn, and Seth Pettie. Additive spanners
and (alpha, beta)-spanners. ACM Transactions on Algorithms, 7(1):5, 2010.
[BR10]

Ajesh Babu and Jaikumar Radhakrishnan. An entropy based proof of the moore bound for
irregular graphs. CoRR, abs/1011.1058, 2010.

[BS03]

S. Baswana and S. Sen. A simple linear time algorithm for computing a (2k − 1)-spanner
of O(n1+1/k ) size in weighted graphs. In Proceedings of the 30th International Colloquium
on Automata, Languages and Programming, volume 2719 of LNCS, pages 384–396. Springer,
2003.

[BS07]

Surender Baswana and Sandeep Sen. A simple and linear time randomized algorithm for
computing sparse spanners in weighted graphs. Random Struct. Algorithms, 30(4):532–563,
2007.

[BW15]

Gregory Bodwin and Virginia Vassilevska Williams. Very sparse additive spanners and emulators. In Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science,
ITCS 2015, Rehovot, Israel, January 11-13, 2015, pages 377–382, 2015.

[Che13]

Shiri Chechik. New additive spanners. In Proceedings of the Twenty-Fourth Annual ACMSIAM Symposium on Discrete Algorithms, SODA ’13, pages 498–512, Philadelphia, PA, USA,
2013. Society for Industrial and Applied Mathematics.

[Coh99]

E. Cohen. Fast algorithms for t-spanners and stretch-t paths. SIAM J. Comput., 28:210–236,
1999.

[Coh00]

Edith Cohen. Polylog-time and near-linear work approximation scheme for undirected shortest
paths. J. ACM, 47(1):132–166, 2000.

[DGPV08] Bilel Derbel, Cyril Gavoille, David Peleg, and Laurent Viennot. On the locality of distributed
sparse spanner construction. In Proceedings of the Twenty-Seventh Annual ACM Symposium
on Principles of Distributed Computing, PODC 2008, Toronto, Canada, August 18-21, 2008,
pages 273–282, 2008.
[DHZ00]

D. Dor, S. Halperin, and U. Zwick. All-pairs almost shortest paths. SIAM J. Comput., 29:1740–
1759, 2000.

[DMP+ 03] D. Dubhashi, A. Mei, A. Panconesi, J. Radhakrishnan, and A. Srinivisan. Fast distributed
algorithm for (weakly) connected dominating sets and linear-size skeletons, 2003.

28

[DMZ06]

Bilel Derbel, Mohamed Mosbah, and Akka Zemmari. Fast distributed graph partition and
application. In 20th International Parallel and Distributed Processing Symposium (IPDPS
2006), Proceedings, 25-29 April 2006, Rhodes Island, Greece, 2006.

[EEST05]

Michael Elkin, Yuval Emek, Daniel A. Spielman, and Shang-Hua Teng. Lower-stretch spanning trees. In STOC, pages 494–503, 2005.

[Elk04]

M. Elkin. An unconditional lower bound on the time-approximation tradeoff of the minimum
spanning tree problem. In Proc. of the 36th ACM Symp. on Theory of Comput. (STOC 2004),
pages 331–340, 2004.

[Elk05]

Michael Elkin. Computing almost shortest paths. ACM Trans. Algorithms, 1(2):283–323,
2005.

[Elk07a]

Michael Elkin. A near-optimal distributed fully dynamic algorithm for maintaining sparse
spanners. In Proceedings of the Twenty-Sixth Annual ACM Symposium on Principles of Distributed Computing, PODC 2007, Portland, Oregon, USA, August 12-15, 2007, pages 185–194,
2007.

[Elk07b]

Michael Elkin. Streaming and fully dynamic centralized algorithms for constructing and maintaining sparse spanners. In Automata, Languages and Programming, 34th International Colloquium, ICALP 2007, Wroclaw, Poland, July 9-13, 2007, Proceedings, pages 716–727, 2007.

[EN16a]

Michael Elkin and Ofer Neiman. Distributed strong diameter network decomposition. In
Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC
2016, Chicago, IL, USA, July 25-28, 2016, pages 211–216, 2016.

[EN16b]

Michael Elkin and Ofer Neiman. Hopsets with constant hopbound, and applications to approximate shortest paths. In IEEE 57th Annual Symposium on Foundations of Computer Science,
FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, pages
128–137, 2016.

[EN17]

Michael Elkin and Ofer Neiman. Efficient algorithms for constructing very sparse spanners and
emulators. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete
Algorithms, pages 652–669, 2017.

[EP04]

Michael Elkin and David Peleg. (1+epsilon, beta)-spanner constructions for general graphs.
SIAM J. Comput., 33(3):608–631, 2004.

[EP15]

Michael Elkin and Seth Pettie. A linear-size logarithmic stretch path-reporting distance oracle
for general graphs. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on
Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 805–821,
2015.

[ES16]

Michael Elkin and Shay Solomon. Fast constructions of lightweight spanners for general
graphs. ACM Trans. Algorithms, 12(3):29:1–29:21, 2016.

[EZ06]

Michael Elkin and Jian Zhang. Efficient algorithms for constructing (1+epsilon, beta)-spanners
in the distributed and streaming models. Distributed Computing, 18(5):375–385, 2006.

29

[FKM+ 05] J. Feigenbaum, S. Kannan, A. McGregor, S. Suri, and J. Zhang. Graph distances in the streaming model: The value of space. In Proc. of the ACM-SIAM Symp. on Discrete Algorithms,
pages 745–754, 2005.
[FS16]

Arnold Filtser and Shay Solomon. The greedy spanner is existentially optimal. In Proceedings
of the 2016 ACM Symposium on Principles of Distributed Computing, PODC 2016, Chicago,
IL, USA, July 25-28, 2016, pages 9–17, 2016.

[HZ96]

S. Halperin and U. Zwick. Linear time deterministic algorithm for computing spanners for
unweighted graphs, 1996. manuscript.

[KMP11]

Ioannis Koutis, Gary L. Miller, and Richard Peng. A nearly-m log n time solver for sdd
linear systems. In Proceedings of the 2011 IEEE 52Nd Annual Symposium on Foundations of
Computer Science, FOCS ’11, pages 590–598, Washington, DC, USA, 2011. IEEE Computer
Society.

[LS93]

N. Linial and M. Saks. Decomposing graphs into regions of small diameter. Combinatorica,
13:441–454, 1993.

[MPVX15] Gary L. Miller, Richard Peng, Adrian Vladu, and Shen Chen Xu. Improved parallel algorithms for spanners and hopsets. In Proceedings of the 27th ACM Symposium on Parallelism in
Algorithms and Architectures, SPAA ’15, pages 192–201, New York, NY, USA, 2015. ACM.
[MPX13]

Gary L. Miller, Richard Peng, and Shen Chen Xu. Parallel graph decompositions using random
shifts. In 25th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA ’13,
Montreal, QC, Canada - July 23 - 25, 2013, pages 196–203, 2013.

[OMSW10] James B. Orlin, Kamesh Madduri, K. Subramani, and M. Williamson. A faster algorithm
for the single source shortest path problem with few distinct positive lengths. J. of Discrete
Algorithms, 8:189–198, June 2010.
[Pel99]

David Peleg. Proximity-preserving labeling schemes and their applications. In GraphTheoretic Concepts in Computer Science, 25th International Workshop, WG ’99, Ascona,
Switzerland, June 17-19, 1999, Proceedings, pages 30–41, 1999.

[Pel00]

David Peleg. Distributed Computing: A Locality-sensitive Approach. Society for Industrial
and Applied Mathematics, Philadelphia, PA, USA, 2000.

[Pet09]

Seth Pettie. Low distortion spanners. ACM Transactions on Algorithms, 6(1), 2009.

[Pet10]

Seth Pettie. Distributed algorithms for ultrasparse spanners and linear size skeletons. Distributed Computing, 22(3):147–166, 2010.

[Pet16]

Seth Pettie. Personal communication, 2016.

[PS89]

D. Peleg and A. Schäffer. Graph spanners. J. Graph Theory, 13:99–116, 1989.

[PU89a]

D. Peleg and J. D. Ullman. An optimal synchronizer for the hypercube. SIAM J. on Comput.,
18:740–747, 1989.

30

[PU89b]

D. Peleg and E. Upfal. A tradeoff between size and efficiency for routing tables. J. of the ACM,
36:510–530, 1989.

[Rei93]

John H. Reif. Synthesis of Parallel Algorithms. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1st edition, 1993.

[RZ04]

Liam Roditty and Uri Zwick. On dynamic shortest paths problems. In Algorithms - ESA 2004,
12th Annual European Symposium, Bergen, Norway, September 14-17, 2004, Proceedings,
pages 580–591, 2004.

[TZ05]

Mikkel Thorup and Uri Zwick. Approximate distance oracles. J. ACM, 52(1):1–24, 2005.

[TZ06]

M. Thorup and U. Zwick. Spanners and emulators with sublinear distance errors. In Proc. of
Symp. on Discr. Algorithms, pages 802–809, 2006.

[Woo06]

David P. Woodruff. Lower bounds for additive spanners, emulators, and more. In Proceedings
of the 47th Annual IEEE Symposium on Foundations of Computer Science, FOCS ’06, pages
389–398, Washington, DC, USA, 2006. IEEE Computer Society.

31

