Near-Additive Spanners and Near-Exact Hopsets, A Unified View

Abstract

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 [25] 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 [3].

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

0 G[G
G[G. Itwasshownin[22]thatforanyn-vertexGand✏andasabove,thereexistsa

(1 + ✏, )-hopset with O ̃(n1+1/) edges, with = EP.
Not only the two results of [25] and [22] are strikingly similar, but so are also their proof

techniques. Moreover, Thorup-Zwick’s later construction of near-additive spanners [41] was also shown in [24, 29] to provide hopsets with analogous (to that of [41]) properties.

In this survey we explore this intriguing phenomenon, sketch the basic proof techniques used for these results, and highlight open questions.