A Unified and Fine-Grained Approach for Light Spanners
share
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 (1) stronger lightness bounds, and (2) faster construction times. Our results include: _ K_r-minor-free graphs: A truly optimal spanner construction and a fast construction. _ General graphs: A truly optimal spanner – almost and a linear-time construction with near-optimal lightness. _ Low dimensional Euclidean spaces: We demonstrate that Steiner points help in reducing the lightness of Euclidean 1+ϵ-spanners almost quadratically for d≥ 3.
READ FULL TEXT