New (α, β) Spanners and Hopsets

An f (d)-spanner of an unweighted n-vertex graph G = (V, E) is a subgraph H satisfying that dist H (u, v) is at most f (dist G (u, v)) for every u, v ∈ V. A simple girth argument implies that any f (d)-spanner with O(n 1+1/k ) edges must satisfy that f (d)/d = Ω(k/d + 1). A matching upper bound (even up to constants) for super-constant values of d is currently known only for d = Ω((log k) log k ) as given by the well known (1 + , β) spanners of Elkin and Peleg, and its recent improvements by SODA'17], and [Abboud-Bodwin-Pettie, SODA'18].

We present new spanner constructions that achieve a nearly optimal stretch of O(k/d + 1 ) for any distance value d ∈ [1, k 1-o(1) ] and d ≥ k 1+o(1) . We also show more optimized spanner constructions with nearly linear number of edges. Specifically, for every ∈ (0, 1) and integer k ≥ 1, we show the construction of (3 + , β) spanners for β = O (k log(3+8/ ) ) and O (n 1+1/k ) edges.

In addition, we consider the related graph concept of hopsets introduced by [Cohen, J. ACM '00]. Informally, an hopset H is a weighted edge set that, when added to the graph G, allows one to get a path from each node u to a node v with at most β hops (i.e., edges) and length at most α • dist G (u, v). We present a new family of (α, β) hopsets with O(k • n 1+1/k ) edges and α • β = O(k). Turning to nearly linear-size hopsets, we show a construction of (3 + , β) hopset with O (n 1+1/k ) edges and hop-bound of β = O (k log(3+9/ ) ), improving upon the state-of-the-art hop-bound of β = O(log k/ ) log k .