Almost-Optimal Sublinear Additive Spanners

Given an undirected unweighted graph G = (V, E) on n vertices and m edges, a subgraph 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 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 edges [Pettie, 2009] . Most importantly, the size of our spanners almost matches the lower bound of Ω n 1+ 1 2 k+1 -1