Almost-Optimal Sublinear Additive Spanners
share
Given an undirected unweighted graph G = (V, E) on n vertices and m edges, a subgraph H⊆ G is a spanner of G with stretch function f: ℝ_+ →ℝ_+, iff for every pair s, t of vertices in V, _H(s, t)≤ f(_G(s, t)). When f(d) = d + o(d), H is called a sublinear additive spanner; when f(d) = d + o(n), H is called an additive spanner, and f(d) - d is usually called the additive stretch of H. As our primary result, we show that for any constant δ>0 and constant integer k≥ 2, every graph on n vertices has a sublinear additive spanner with stretch function f(d)=d+O(d^1-1/k) and O(n^1+1+δ/2^k+1-1) edges. When k = 2, this improves upon the previous spanner construction with stretch function f(d) = d + O(d^1/2) and Õ(n^1+3/17) edges [Chechik, 2013]; for any constant integer k≥ 3, this improves upon the previous spanner construction with stretch function f(d) = d + O(d^1-1/k) and O(n^1+(3/4)^k-2/7 - 2· (3/4)^k-2) edges [Pettie, 2009]. Most importantly, the size of our spanners almost matches the lower bound of Ω(n^1+1/2^k+1-1) [Abboud, Bodwin, Pettie, 2017]. As our second result, we show a new construction of additive spanners with stretch O(n^0.403) and O(n) edges, which slightly improves upon the previous stretch bound of O(n^3/7+ϵ) achieved by linear-size spanners [Bodwin and Vassilevska Williams, 2016]. An additional advantage of our spanner is that it admits a subquadratic construction runtime of Õ(m + n^13/7), while the previous construction in [Bodwin and Vassilevska Williams, 2016] requires all-pairs shortest paths computation which takes O(min{mn, n^2.373}) time.
READ FULL TEXT