Thorup-Zwick Emulators are Universally Optimal Hopsets∗
Shang-En Huang
University of Michigan

Seth Pettie
University of Michigan

arXiv:1705.00327v1 [] 30 Apr 2017

May 2, 2017

Abstract
A (β, )-hopset is, informally, a weighted edge set that, when added to a graph, allows one to get
from point a to point b using a path with at most β edges (“hops”) and length (1 + ) dist(a, b). In this
paper we observe that Thorup and Zwick’s sublinear additive emulators are also actually (O(k/)k , )hopsets for every  > 0, and that with a small change to the Thorup-Zwick construction, the size of
1+

1

the hopset can be made O(n 2k+1 −1 ). As corollaries, we also shave “k” factors off the size of Thorup
and Zwick’s [20] sublinear additive emulators and the sparsest known (1 + , O(k/)k−1 )-spanners, due
to Abboud, Bodwin, and Pettie [1].

1

Introduction
(β)

Let G = (V, E, w) be a weighted undirected graph. Define distG (u, v) to be the length of the shortest path
(∞)
(β)
from u to v in G that uses at most β edges, or “hops.” Whereas distG = distG is a metric, distG is not in

V
general. A set H ⊂ 2 of weighted edges is called a (β, )-hopset if for every u, v ∈ V ,
(β)

distG (u, v) ≤ distG∪H (u, v) ≤ (1 + ) distG (u, v).
Background. Cohen [7] formally defined the notion of a hopset, but the idea was latent in earlier work [21,
14, 6, 18]. Cohen’s (β, )-hopset had size O(n1+1/κ log n) and β = (−1 log n)O(log κ) . Elkin and Neiman [9]
showed that a constant hopbound β suffices (when κ,  are constants). In particular, their hopset has
size O(n1+1/κ log n log κ) and β = O(−1 log κ)log κ . Abboud, Bodwin, and Pettie [1] recently proved that
1+

1

−δ

the tradeoffs of [9] are essentially optimal: for any integer k, any hopset of size n 2k+1 −1
must have
β = Ω(ck /k+1 ), where ck is a constant depending only on k.1 There are other constructions of hopsets [5,
11, 12, 16] that are designed for parallel or dynamic environments; their tradeoffs (between hopset size and
hopbound) are worse than [7, 9] and the ones presented here. See Table 1.
Hopsets, Emulators, and Spanners. Recall that G is an undirected graph, possibly weighted. A spanner
is a subgraph of G such that distH (u, v) ≤ f (distG (u, v)) for some nondecreasing stretch function f . An emulator of an unweighted graph G is a weighted edge set H such that distH (u, v) ∈ [distG (u, v), f (distG (u, v))].
Syntactically, the definition of hopsets is closely related to emulators. The difference is that hopsets have a
hopbound constraint but are allowed to use original edges in G whereas emulators must use only H. The
purpose of emulators is to compress the graph metric distG : ideally |H|  |E(G)|. Historically, the literature
on hopset constructions [7, 9] has been noticeably more complex than those of spanners and emulators, many
∗ Supported

by NSF Grants CCF-1514383 and CCF-1637546.
that setting κ = 2k+1 − 1 in the Elkin-Neiman construction gives β = O(k/)k , where log κ = blog κc = k. Thus,
saving any δ in the exponent of the hopset increases β significantly. In general, the statement of [9] obscures the nature of the
tradeoff: there are not distinct tradeoffs for each κ ∈ {1, 2, 3, . . .}, but only for κ ∈ {1, 3, 7, . . . , 2k+1 − 1, . . .}.
1 Note

1

Authors

Size

Klein and Subramanian [14]

O(n)

Thorup and Zwick [19]
Cohen [7]

1+1/κ

O(κn
O(n

Elkin and Neiman [9]
Abboud, Bodwin, and Pettie [1]

O(n

1
1+ κ
1
1+ κ

log n log κ)

n

O n

1+

1
2k+1 −1



Stretch

2

2κ − 1

O(log κ)

· log n)

1
−δ
1+ k+1
2
−1



New

)

Hopbound
√
O( n log n)

1

((log n)/)

1+

O((log κ)/)log κ

1+

k+1

1+

−→ Ω(ck /

)

O(k/)k

1+

Table 1: Tradeoffs between size and hopbound of previous hopsets. Fix the parameter κ = 2k+1 − 1 to
compare [7, 9] against the lower bound [1] and the new result.
of which [3, 2, 8, 20, 4, 15, 1] are quite elegant. Our goal in this work is to demonstrate that there is nothing
intrinsically complex about hopsets, and that a very simple construction improves on all prior constructions
and matches the Abboud-Bodwin-Pettie lower bound.
New Results.

Thorup and Zwick [20] designed their emulator for unweighted graphs, and proved that
1+

1

it has size O(kn 2k+1 −1 ) and a sublinear additive stretch function f (d) = d + O(kd1−1/k ). In this paper
we show that the Thorup-Zwick emulator, when applied to a weighted graph, produces a (β, )-hopset that
achieves every point on the Abboud-Bodwin-Pettie [1] lower bound tradeoff curve. Moreover, with two
1+

1

subtle modifications to the construction, we can reduce the size to O(n 2k+1 −1 ), shaving off a factor k. Our
technique also applies to other constructions, and as corollaries we improve the size of Thorup and Zwick’s
emulator [20] and Abboud, Bodwin, and Pettie’s (1 + , β)-spanners.2
Theorem 1. Fix any weighted graph G and integer k ≥ 1. There is a (β, )-hopset for G with size

k
1
1+
.
O(n 2k+1 −1 ) and β = 2 (4+o(1))k

Theorem 2. (cf. [20]) Fix any unweighted graph G and integer k ≥ 1. There is a sublinear additive emulator
H for G with size O(n

1+

1
2k+1 −1

) and stretch function f (d) = d + (4 + o(1))kd1−1/k .

Theorem 3. (cf. [1]) Fix any unweighted graph G, integer k ≥ 1, and real  > 0. There is a (1 + , ((4 +

o(1))k/)k−1 )-spanner H for G with size O((k/)h n

1+

1
2k+1 −1

), where h =

3·2k−1 −(k+2)
2k+1 −1

< 3/4.

Remark 1. In recent and independent technical report, Elkin and Neiman [10] also observed that Thorup and Zwick’s emulator yields an essentially optimal hopset. They proposed a modification to Thorup
1
1+
and Zwick’s construction that reduces the size to O(n 2k+1 −1 ) (eliminating a factor k), but increases the
hopbound β from O(k/)k to O((k + 1)/)k+1 . For example, their technique does not imply any of the
improvements found in Theorems 1, 2, or 3.

2

The Hopset Construction

In this section, we present the construction of the hopset based on Thorup and Zwick’s emulator [20], then
analyze its size, stretch, and hopbound.
The construction is parameterized by an integer k ≥ 1 and a set {qi } of sampling probabilities. Let
V = V0 ⊇ V1 ⊇ V2 ⊇ · · · ⊇ Vk ⊇ Vk+1 = ∅ be the vertex sets in each layer. For each i ∈ [0, k), each vertex in
Vi is independently promoted to Vi+1 with probability qi+1 /qi . Thus E[|Vi |] = nqi . For each vertex v ∈ V
2A

(1 + , β)-spanner of an unweighted graph is one with stretch function f (d) = (1 + )d + β.

2

and i ∈ [1, k], define pi (v) to be any vertex in Vi such that distG (v, pi (v)) = distG (v, Vi ). For any vertex
v ∈ Vi \ Vi+1 , define B(v) to be:
B(v) = {u ∈ Vi | distG (v, u) < distG (v, pi+1 (v))}
Note that pk+1 (v) does not exist; by convention distG (v, pk+1 (v)) = ∞. The hopset is defined to be H =
E0 ∪ E1 ∪ · · · ∪ Ek , where
[
Ei =
{(v, u) | u ∈ B(v) ∪ {pi+1 (v)}} .
v∈Vi \Vi+1

The length of an edge in H is always the distance between its endpoints. This concludes the description of
the construction.

2.1

Size Analysis

The expected size of Ei is at most E[|Vi |](qi /qi+1 ) = nqi2 /qi+1 , for each i ∈ [0, k), and is (nqk )2 if i = k.
Following Pettie [17], we choose {qi } such that the layers of the hopset have geometrically decaying sizes.
Setting qi = n

−

2i −1
2k+1 −1

· 2−2

i

−i+1

nqi2 /qi+1

, the expected size of Ei , for i ∈ [0, k), is

2  

i
i+1 −1
i
i+1
− 2 −1
−2
= n · n 2k+1 −1 · 2−2 −i+1
n 2k+1 −1 · 2−2 −i
i+1

i+1

1− 2k+1−2 + 2k+1−1

=n
=n

1+

2

−1

1
2k+1 −1

2

−1

· 2−i+2 .

· 2−2

i+1

−2i+2−(−2i+1 −i)

The expected size of Ek is
2

2



(nqk ) = n · n
=n

1+

−

2k −1
2k+1 −1

1
2k+1 −1

2

·2

k+1

2−2

−2k −k+1

−2k+2

 n

1+

1
2k+1 −1

· 2−k+2 ,

so the expected size of H is at most
k
X
i=0

2.2

E[|Ei |] ≤ n

1+

1
2k+1 −1

k
X

!
2

−i+2

= O(n

1+

1
2k+1 −1

).

i=0

Stretch and Hopbound Analysis

Let us first give an informal sketch of the analysis. Let a, b be vertices. Choose an integer r ≥ 2, and imagine
dividing up the shortest a–b path into rk intervals of length µ = distG (a, b)/rk , where µ defines one “unit”
of length. Once r and µ are fixed we prove that given any two vertices u, v at distance at most ri µ, there is
either an hi -hop path from u to v with additive stretch O(iri−1 ) · µ, or there is an hi -hop path from u to a
Vi+1 -vertex with length (ri + O(iri−1 )) · µ. Of course, when i = k the set Vk+1 = ∅ is empty, so we cannot be
in the second case. Since, by definition of µ, distG (a, b) ≤ rk µ, there must be an hk -hop path with additive
stretch O(krk−1 ) · µ. In order for this stretch to be  distG (a, b) we must set r = Θ(k/).
So, to recap, the integer parameter r = Θ(k/) depends on the desired stretch , and r determines the
hopcount sequence (hi ), which is defined inductively as follows.
h0 = 1,
for i ∈ [1, k].

hi = (r + 1)hi−1 + r

The parameter β of the hopset is exactly hk . It is straightforward to show that hk < 2(r + 1)k . Once r
and (hi ) are fixed, Theorem 4 is proved by induction.
3

multi-hop segment
single-hop segment

Case 1: (u0 , v 0 ) ∈ H.

0

u

uj1

u

uj1 +1

uj2 −1

v0

uj2

u00 = pi+1 (u0 )

e2
Cas
u0

v0

uj1

u

v

uj1 +1

uj2 −1

uj2

v

Figure 1: The two cases depending on whether (u0 , v 0 ) ∈ H or not. The first case leads to (i) and the second
case leads to (ii) in the statement of Theorem 4.
Theorem 4. For any fixed real µ (the “unit”), for all i ∈ [0, k] and any pair u, v ∈ V such that distG (u, v) ≤
ri µ, at least one of the following statements holds.
(h )

i
(i) distG∪H
(u, v) ≤ distG (u, v) + ((r + 4)i − ri )µ,

(h )

i
(ii) There exists ui+1 ∈ Vi+1 such that distG∪H
(u, ui+1 ) ≤ (r + 4)i µ.

Proof. The proof is by induction on i. In the base case i = 0 and h0 = 1. Let u, v ∈ V with distG (u, v) ≤
(1)
r0 µ = µ. If (u, v) ∈ H then distG∪H (u, v) = distG (u, v) so (i) holds. Otherwise, (u, v) ∈
/ H, meaning
(1)
v ∈
/ B(u). If u ∈ V0 \ V1 then distG∪H (u, p1 (u)) ≤ distG (u, v) ≤ µ, and if u ∈ V1 then p1 (u) = u, so
(1)
distG∪H (u, p1 (u)) = 0. In either case, (ii) holds.
Now assume i > 0. Consider vertices u, v ∈ V with distG (u, v) ≤ ri µ and let P be a shortest u–v path
in G. Then, as shown in Figure 1, we partition P into at most 2r − 1 segments hu0 = u, u1 i, hu1 , u2 i,
. . ., hu`−1 , u` = vi as follows. Starting at u0 = u, we pick u1 to be the farthest vertex on P such that
distG (u0 , u1 ) ≤ ri−1 µ, and let (u1 , u2 ) be the next edge on the path.3 Repeat the process until we reach
u` = v, oscillating between selecting segments that have length at most ri−1 µ and single edges.
• Multi-hop segment: the shortest path from us to us+1 satisfies distG (us , us+1 ) ≤ ri−1 µ.
• Single-hop segment: the segment is actually an edge (us , us+1 ) ∈ E.

By the induction hypothesis, each multi-hop segment satisfies (i) or (ii) within hi−1 hops. Moreover,
in each greedy iteration the sum of the lengths from picked multi-hop segment and immediately followed
single-hop segment is strictly greater than ri µ except the last one. Therefore, by the pigeonhole principle,
there are at most r multi-hop segments on P and at most r − 1 single-hop segments on P .
If condition (i) holds for all multi-hop segments, then in at most rhi−1 + r − 1 ≤ hi hops,
(h )

i
distG∪H
(u, v) ≤ distG (u, v) + r((r + 4)i−1 − ri−1 )µ

≤ distG (u, v) + ((r + 4)i − ri )µ,

3 Note

that if the first edge has length more than ri−1 µ, then u1 = u0 .

4

and condition (i) holds for P .
Otherwise, condition (i) does not hold for at least one multi-hop segment. Consider the first multihop segment huj1 , uj1 +1 i and the last multi-hop segment huj2 −1 , uj2 i that do not satisfy condition (i). By
condition (ii), there exist u0 and v 0 ∈ Vi satisfying
(h

)

(h

)

i−1
distG∪H
(uj1 , u0 ) ≤ (r + 4)i−1 µ

i−1
distG∪H
(uj2 , v 0 ) ≤ (r + 4)i−1 µ.

Now we have two cases depending on whether (u0 , v 0 ) ∈ H or not. If (u0 , v 0 ) ∈ H, then by the triangle
inequality, we can get from uj1 to uj2 with 2hi−1 + 1 hops and additive stretch
(2h

i−1
distG∪H

+1)

(h

)

(h

(1)

)

i−1
i−1
(uj1 , uj2 ) − distG (uj1 , uj2 ) ≤ distG∪H
(uj1 , u0 ) + distH (u0 , v 0 ) + distG∪H
(v 0 , uj2 ) − distG (uj1 , uj2 )

(h

)

(h

)

i−1
i−1
≤ 2 distG∪H
(uj1 , u0 ) + 2 distG∪H
(v 0 , uj2 )

≤ 4(r + 4)i−1 µ.

We know there are a total of at most r − 1 multi-hop segments satisfying condition (i). Hence, within at
most (r − 1)hi−1 + r − 1 + 2hi−1 + 1 ≤ hi hops, we can get from u to v with additive stretch
(2h

(h )

+1)

i−1
i
distG∪H
(u, v) − distG (u, v) ≤ (r − 1)((r + 4)i−1 − ri−1 )µ + distG∪H
(uj1 , uj2 ) − distG (uj1 , uj2 )


i−1
i−1
i−1
≤ (r − 1)((r + 4)
− r ) + 4(r + 4)
µ


i−1
i
i−1
= (r + 3)(r + 4)
−r +r
µ

≤ ((r + 4)i − ri )µ

(ri−1 ≤ (r + 4)i−1 )

and condition (i) holds for P in this case.
On the other hand, suppose that (u0 , v 0 ) ∈
/ H. Since both u0 , v 0 ∈ Vi but (u0 , v 0 ) ∈
/ H, we know that
(1) 0
00
0
u = pi+1 (u ) ∈ Vi+1 must exist with distH (u , u00 ) ≤ distG (u0 , v 0 ). Hence, we can get from uj1 to u00 via an
(hi−1 + 1)-hop path with length
(h

i−1
distG∪H

+1)

(h

)

(h

)

(1)

i−1
(uj1 , u00 ) ≤ distG∪H
(uj1 , u0 ) + distH (u0 , u00 )
i−1
≤ distG∪H
(uj1 , u0 ) + distG (u0 , v 0 )

(h

)

(h

)

i−1
i−1
≤ 2 distG∪H
(uj1 , u0 ) + distG (uj1 , uj2 ) + distG∪H
(uj2 , v 0 )

≤ 3(r + 4)i−1 µ + distG (uj1 , uj2 ).

Similar to the previous case, there are at most r − 1 multi-hop segments appeared before uj1 , and all of
them are satisfying condition (i). Hence, the surplus
((r−1)hi−1 +r−1)

distG∪H

(u, uj1 ) ≤ distG (u, uj1 ) + (r − 1)((r + 4)i−1 − ri−1 )µ.

Therefore, in at most (r − 1)hi−1 + r − 1 + hi−1 + 1 ≤ hi hops,
(h )

((r−1)h

+r−1)

(h

+1)

i−1
i
distG∪H
(u, u00 ) ≤ distG∪H i−1
(u, uj1 ) + distG∪H
(uj1 , u00 )


≤ (r − 1)((r + 4)i−1 − ri−1 ) + 3(r + 4)i−1 µ + distG (u, uj2 )


≤ (r + 2)(r + 4)i−1 − ri + ri−1 µ + distG (u, uj2 )


≤ (r + 4)i − ri µ + distG (u, uj2 )
(ri−1 ≤ (r + 4)i−1 )

≤ (r + 4)i µ

(distG (u, uj2 ) ≤ distG (u, v) ≤ ri µ)

5

Proof of Theorem 1. Fix u, v ∈ V and d = distG (u, v). Define 0 = ln(1 + ). Notice that 1/0 = (1 +
o(1))(1/). Set r = d4k/0 e = Θ(k/) and µ = d/rk . By Theorem 4, since Vk+1 = ∅, condition (i) must hold:
within hk < 2(r + 1)k hops we have
(h )

k
dG∪H
(u, v) ≤ distG (u, v) + ((r + 4)k − rk )µ
!


k
43 k3
4k 42 2
+
+ ··· d
+
=d+
r
r2
r3


03
02
0
+
+ ··· d
≤ 1+ +
2!
3!

(since 4k/r ≤ 0 )

0

≤ e d = (1 + )d.
Observe that if we set k = log log n − O(1) the size becomes linear.
Corollary 1. Every n-vertex graph has an O(n)-size (β, )-hopset with β = 2( (4+o(1))k
)k and k = log log n −

O(1).

3

Conclusion

In this paper our goal was to demonstrate that hopset constructions need not be complex, and that optimal
hopsets can be constructed with a simple and elegant algorithm, namely a small modification to Thorup and
Zwick’s emulator construction [20]. From a purely quantitative perspective our hopsets also improve on the
sparseness and/or hopbound of other constructions [7, 9, 10]. As a happy byproduct of our construction, we
also shave small factors off the best sublinear additive emulators [20] and (1 + , β)-spanners [1].
We now have a good understanding of the tradeoffs available between β and the hopset size when the
stretch is fixed at 1 + ,  > 0 being a small real. However, when  = 0 or  is large, there are still gaps
between√the best upper and lower bounds. For example, when  = 0 a trivial hopset4 has size O(n) with
δ
β = O( n log n). A construction of Hesse [13] (see also [1, §6])
√ implies that β must be at least n for some
δ, but it is open whether O(n)-size hopsets exist with β  n. At the other extreme, Thorup and Zwick’s
distance oracles imply that O(κn1+1/κ )-size hopsets exist with β = 2 and stretch 2κ − 1. Is this tradeoff
optimal? Are there other tradeoffs available when β is a fixed constant (say 3 or 4), independent of κ?
Acknowledgement.

Thanks to Richard Peng for help with the references for zero-stretch hopsets.

References
[1] A. Abboud, G. Bodwin, and S. Pettie. A hierarchy of lower bounds for sublinear additive spanners.
In Proceedings 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 568–576,
2017.
[2] D. Aingworth, C. Chekuri, P. Indyk, and R. Motwani. Fast estimation of diameter and shortest paths
(without matrix multiplication). SIAM Journal on Computing, 28(4):1167–1181, 1999.
[3] I. Althöfer, G. Das, D. Dobkin, D. Joseph, and J. Soares. On sparse spanners of weighted graphs.
Discrete and Computational Geometry, 9:81–100, 1993.
[4] S. Baswana, T. Kavitha, K. Mehlhorn, and S. Pettie. Additive spanners and (α, β)-spanners. ACM
Trans. Algorithms, 7(1), 2010.
4 Let

H be a clique on a set of

√

n vertices chosen uniformly at random.

6

[5] A. Bernstein. Fully dynamic (2 + )-approximate all-pairs shortest paths with fast query and close to
linear update time. In Proceedings 50th Annual IEEE Symposium on Foundations of Computer Science
(FOCS), pages 693–702, 2009.
[6] E. Cohen. Using selective path-doubling for parallel shortest-path computations. Journal of Algorithms,
22(1):30–56, 1997.
[7] E. Cohen. Polylog-time and near-linear work approximation scheme for undirected shortest paths. J.
ACM, 47(1):132–166, 2000.
[8] D. Dor, S. Halperin, and U. Zwick. All-pairs almost shortest paths. SIAM Journal on Computing,
29(5):1740–1759, 2000.
[9] M. Elkin and O. Neiman. Hopsets with constant hopbound, and applications to approximate shortest
paths. In Proceedings 57th Annual IEEE Symposium on Foundations of Computer Science, (FOCS),
pages 128–137, 2016.
[10] M. Elkin and O. Neiman. Linear-size hopsets with small hopbound, and distributed routing with low
memory. CoRR, abs/1704.08468, 2017.
[11] M. Henzinger, S. Krinninger, and D. Nanongkai. Decremental single-source shortest paths on undirected
graphs in near-linear total update time. In Proceedings 55th Annual IEEE Symposium on Foundations
of Computer Science (FOCS), pages 146–155, 2014.
[12] M. Henzinger, S. Krinninger, and D. Nanongkai. A deterministic almost-tight distributed algorithm for
approximating single-source shortest paths. In Proceedings 48th Annual ACM Symposium on Theory of
Computing (STOC), pages 489–498, 2016.
[13] W. Hesse. Directed graphs requiring large numbers of shortcuts. In Proceedings 14th Annual ACM-SIAM
Symposium on Discrete Algorithms (SODA), pages 665–669, 2003.
[14] P. N. Klein and S. Subramanian. A randomized parallel algorithm for single-source shortest paths.
Journal of Algorithms, 25(2):205–220, 1997.
[15] M. B. T. Knudsen. Additive spanners: A simple construction. In Proceedings 14th Scandinavian
Symposium and Workshops on Algorithm Theory (SWAT), pages 277–281, 2014.
[16] G. L. Miller, R. Peng, A. Vladu, and S. C. Xu. Improved parallel algorithms for spanners and hopsets.
In Proceedings 27th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages
192–201, 2015.
[17] S. Pettie. Low distortion spanners. ACM Trans. Algorithms, 6(1):7:1–7:22, 2009.
[18] H. Shi and T. H. Spencer. Time-work tradeoffs of the single-source shortest paths problem. Journal of
Algorithms, 30(1):19–32, 1999.
[19] M. Thorup and U. Zwick. Approximate distance oracles. J. ACM, 52(1):1–24, 2005.
[20] M. Thorup and U. Zwick. Spanners and emulators with sublinear distance errors. In Proceedings 17th
Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 802–809, 2006.
[21] J. D. Ullman and M. Yannakakis. High-probability parallel transitive-closure algorithms. SIAM J.
Comput., 20(1):100–125, 1991.

7

