A Lower Bound for Light Spanners in General Graphs

Greg Bodwin, Jeremy Flics

A recent upper bound by Le and Solomon [STOC '23] has established that every $n$-node graph has a $(1+\epsilon )(2k-1)$-spanner with lightness $O({\epsilon }^{-1}{n}^{1/k})$. This…