A Unified and Fine-Grained Approach for Light Spanners

Abstract: Seminal works on light spanners from recent years provide near-optimal tradeoffs between the stretch and lightness of spanners in general graphs, minor-free graphs, and doubling metrics. In FOCS’19 the authors provided a “truly optimal” tradeoff for Euclidean low-dimensional spaces. Some of these papers employ inherently different techniques than others. Moreover, the runtime of these constructions is rather high.

In this work we present a unified and fine-grained approach for light spanners. Besides the obvious theoretical importance of unification, we demonstrate the power of our approach in obtaining a plethora of new results with: (1) improved lightness bounds, and (2) faster construction times.