An Alternate Proof of Near-Optimal Light Spanners

Abstract

In 2016, a breakthrough result of Chechik and Wulff-Nilsen [SODA '16] established that every $n$-node graph $G$ has a $(1+\epsilon )(2k-1)$-spanner of lightness $O_{\epsilon }(n^{1/k})$, and recent followup work by Le and Solomon [STOC '23] generalized the proof strategy and improved the dependence on $\epsilon$. We give a new proof of this result, with the improved $\epsilon$-dependence. Our proof is a direct analysis of the often-studied greedy spanner, and can be viewed as an extension of the folklore Moore bounds used to analyze spanner sparsity.

26 pages. This is the TheoretiCS journal version (invited paper from SOSA 2024)

References in corpus (2)

• Optimal Euclidean spanners: really short, thin and lanky
• Can't See The Forest for the Trees: Navigating Metric Spaces by Bounded Hop-Diameter Spanners