New (α, β) Spanners and Hopsets
Uri Ben-Levy, Merav Parter · Society for Industrial and Applied Mathematics eBooks · 2019
An f (d)-spanner of an unweighted n-vertex graph G = (V, E) is a subgraph H satisfying that distH(u, v) is at most f (distG (u, v)) for every u, v ϵ V. A simple girth argument implies that any f (d)-spanner with O(n1+1/k) edges must satisfy that f (d) / d = Ω(⌈k/d⌉). A matching upper bound (even up to constants) for super-constant values of d is currently known only for d = Ω((logk)log k) as given by the well known (1 + ε, β) 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(⌈k/d⌉) for any distance value d ϵ [1, k1−o(1)] and d ≥ k1+o(1). We also show more optimized spanner constructions with nearly linear number of edges. Specifically, for every ε ϵ (0, 1), we show the construction of (3 + ε, β) spanners for β = Oε (klog(3+8/ε)) with Õε (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 α · distG (u, v). We present a new family of (α, β) hopsets with Õ(k · n1+1/k) edges and α · β = O(k). Turning to nearly linear-size hopsets, we show a construction of (3 + ε, β) hopset with Õε(n) edges and hop-bound of β = Oε ((log n)log(3+9/ε)), improving upon the state-of-the-art hop-bound of β = O(log log n)log log n.