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/^k) edges must satisfy that f(d)/d = Ω(dk/de). 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 + e, β) spanners of Elkin and Peleg, and its recent improvements by [Elkin-Neiman, SODA'17], and [Abboud-Bodwin-Pettie, SODA'18]. We present new spanner constructions that achieve a nearly optimal stretch of O(dk/de) for any distance value d ∈ [1, k¹⁻o(1⁾] and d ≥ k¹+o(1⁾. We also show more optimized spanner constructions with nearly linear number of edges. Specifically, for every e ∈ (0, 1), we show the construction of (3 + e, β) spanners for β = O_e(k^log(3+8/e⁾) with O^e_e(n) 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^e(k · n¹+1/^k) edges and α · β = O(k). Turning to nearly linear-size hopsets, we show a construction of (3 + e, β) hopset with O^e_e(n) edges and hop-bound of β = O_e((log n)^log(3+9/e⁾), improving upon the state-of-the-art hop-bound of β = O(log log n)^log log n .