Almost-Optimal Sublinear Additive Spanners

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 , dist H ( s , t )≤ f ( dist 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.

Authors

• Zihan Tan
• Tianyi Zhang 0008

Keywords

• additive spanners
• shortest paths