An Alternate Proof of Near-Optimal Light Spanners

05/29/2023

∙

by   Greg Bodwin, et al.

∙

0

∙

share

In 2016, a breakthrough result of Chechik and Wulff-Nilsen [SODA '16] established that every n-node graph G has a (1+ε)(2k-1)-spanner of lightness O_ε(n^1/k), and recent followup work by Le and Solomon [STOC '23] generalized the proof strategy and improved the dependence on ε. We give a new proof of this result (with the improved ε-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.