Abstract: The greedy spanner is arguably the simplest and most well-studied spanner construction. Experimental results demonstrate that it is at least as good as any other spanner construction in terms of both the size and weight parameters. However, a rigorous proof for this statement has remained elusive. In this work we fill in the theoretical gap via a surprisingly simple observation: The greedy spanner is existentially optimal (or existentially near-optimal) for several important graph families in terms of both size and weight. Roughly speaking, the greedy spanner is said to be existentially optimal (or near-optimal) for a graph family $\mathcal G$ if the worst performance of the greedy spanner over all graphs in $\mathcal G$ is just as good (or nearly as good) as the worst performance of an optimal spanner over all graphs in $\mathcal G$. Focusing on the weight parameter, the state-of-the-art spanner constructions for both general graphs and doubling metrics are complex. Plugging our observation into these results, we conclude that the greedy spanner achieves near-optimal weight guarantees for both general graphs and doubling metrics, thus resolving two longstanding conjectures in the area. Further, we observe that approximate-greedy spanners are existentially near-optimal as well. Consequently, we provide an $O(n \log n)$-time construction of $(1+\epsilon)$-spanners for doubling metrics with constant lightness and degree. Our construction improves previous results in all involved parameters.
Introduction
In network design, a spanner is a subgraph that preserves distances between nodes within a factor $t$, known as the "stretch." The goal is to find spanners that are both sparse (containing few edges) and light (having a total weight close to the Minimum Spanning Tree).
For decades, the "greedy spanner" algorithm has been the intuitive choice for practitioners. It is remarkably simple: sort all edges by weight and add an edge only if the current subgraph does not already provide a path shorter than $t$ times the edge's weight. While experimental evidence consistently showed that this algorithm performs as well as or better than any other, theoretical proofs of its optimality remained elusive. This led researchers to develop highly complex, specialized algorithms to achieve theoretical bounds for general graphs and doubling metrics. This work addresses the fundamental question: Is the simple greedy algorithm actually as good as these complex alternatives?
The Greedy Algorithm and Existential Optimality
The core of the greedy approach is defined by a simple iterative process. By processing edges in non-decreasing order of weight, the algorithm ensures that every edge added is essential for maintaining the desired stretch factor $t$.
The authors introduce a powerful new framework called existential optimality. The central observation is that for any graph family closed under edge removal (such as planar graphs or general weighted graphs), the greedy $t$-spanner is its own "best version." Specifically, the only $t$-spanner of a greedy $t$-spanner is the greedy spanner itself.
This property allows for a "plug-and-play" proof strategy. If any algorithm exists that can produce a light or sparse spanner for a specific graph family, the greedy algorithm must produce one that is at least as good in the worst case. By leveraging existing complex upper bounds from researchers like Chechik, Wulff-Nilsen, and Gottlieb, the authors prove the greedy spanner's optimality without needing to replicate their intricate constructions.
Key Insights and Results
General Graphs
The greedy spanner is now proven to achieve near-optimal weight guarantees for general graphs. This resolves a long-standing conjecture and simplifies the theoretical landscape by showing that the most intuitive algorithm is indeed the most effective.
Doubling Metrics
For doubling metrics, the authors provide an $O(n \log n)$ time construction for $(1+\epsilon)$-spanners. This matches the state-of-the-art results previously only available for Euclidean spaces. Their construction achieves constant lightness and constant degree, improving upon previous methods that were slower ($O(n \log^2 n)$) and resulted in unbounded degrees.
Existential vs. Universal Optimality
The paper distinguishes between universal optimality (being optimal for every specific graph) and existential optimality (matching the best possible theoretical bound for a graph family in the worst case). The greedy spanner is shown to be existentially optimal, meaning its worst-case performance is as good as any other possible algorithm for that class of graphs.
Conclusion and Future Work
This research bridges the gap between practice and theory in spanner construction. By proving that the greedy spanner is existentially optimal, the authors have simplified the field and provided a more efficient $O(n \log n)$ algorithm for doubling metrics.
While these results are a significant step forward, dependencies on the stretch parameter $\epsilon$ and the doubling dimension $ddim$ remain significant. Future work may focus on optimizing these dependencies. Furthermore, the concept of "existential optimality" may serve as a new paradigm for proving the effectiveness of other greedy-style algorithms across various domains in computer science.
Summary updated