A Lower Bound for Light Spanners in General Graphs

A recent upper bound by Le and Solomon [STOC '23] has established that every n-node graph has a (1 + ε)(2k -1)-spanner with lightness O(ε -1 n 1/k ). This bound is optimal up to its dependence on ε; the remaining open problem is whether this dependence can be improved or perhaps even removed entirely.

We show that the ε-dependence cannot in fact be completely removed. For constant k and for ε := Θ(n -1 2k-1 ), we show a lower bound on lightness of

For example, this implies that there are graphs for which any 3-spanner has lightness Ω(n 2/3 ), improving on the previous lower bound of Ω(n 1/ 2). An unusual feature of our lower bound is that it is conditional on the girth conjecture with parameter k -1 rather than k. We additionally show that this implies certain technical limitations to improving our lower bound further. In particular, under the same conditional, generalizing our lower bound to all ε or obtaining an optimal ε-dependence are as hard as proving the girth conjecture for all constant k.