Near-Additive Spanners and Near-Exact Hopsets, A Unified View
Given an unweighted undirected graph G = (V, E), and a pair of parameters ✏ > 0, = 1,2,..., a subgraph G0 = (V,H), H ✓ E, of G is a (1 + ✏,)-spanner (aka, a near- additive spanner) of G if for every u, v 2 V ,
dG0 (u, v) (1 + ✏)dG(u, v) + .
It was shown in  that for any n-vertex G as above, and any ✏ > 0 and = 1, 2, . . ., there
exists a (1 + ✏, )-spanner G0 with O✏,(n1+1/) edges, with log !log 2
= EP = ✏ .
This bound remains state-of-the-art, and its dependence on ✏ (for the case of small ) was shown to be tight in .
Given a weighted undirected graph G = (V, E, !), and a pair of parameters ✏ > 0, =1,2,...,agraphG0 =(V,H,!0)isa(1+✏,)-hopset(aka,anear-exacthopset)ofGif
for every u, v 2 V,
where d() 0 (u, v) stands for a -(hop)-bounded distance between u and v in the union graph
dG(u,v)d() 0(u,v)(1+✏)dG(u,v), G[G
(1 + ✏, )-hopset with O ̃(n1+1/) edges, with = EP.
Not only the two results of  and  are strikingly similar, but so are also their proof
techniques. Moreover, Thorup-Zwick’s later construction of near-additive spanners  was also shown in [24, 29] to provide hopsets with analogous (to that of ) properties.
In this survey we explore this intriguing phenomenon, sketch the basic proof techniques used for these results, and highlight open questions.
- There are currently no refbacks.