Optimal Vertex Fault Tolerant Spanners (for fixed stretch)

Greg Bodwin, Michael Dinitz, Merav Parter, Virginia Vassilevska Williams

This paper, presented by researchers from MIT and Johns Hopkins, provides a definitive answer to a long-standing question in network design: how much extra "space" (edges) do you need to make a graph spanner resilient to failures?

TL;DR

The authors prove that for a fixed stretch factor, you can build a fault-tolerant spanner with a size that depends sublinearly on the number of faults ($f$). They provide a simple greedy algorithm to construct these spanners and prove that their bounds are mathematically optimal, settling a gap where previous methods required significantly more edges.

What Problem Does This Paper Address?

In computer science, a spanner is a sparse skeleton of a graph. If you have a massive network (like the internet or a roadmap), a spanner is a subgraph that keeps the distances between any two points roughly the same (within a "stretch factor" $k$) while using as few edges as possible.

The challenge arises with fault tolerance. If a few nodes (vertex faults) or links (edge faults) fail, a standard spanner might break, causing distances to skyrocket. To prevent this, we build Fault-Tolerant (FT) spanners. Historically, researchers believed that to survive $f$ faults, you had to pay a high price—usually increasing the size of the spanner by a factor of $f$ or even $f^2$. This paper asks: What is the absolute minimum number of edges needed to guarantee a specific stretch factor even when $f$ elements fail?

Methods

The most surprising aspect of this paper is the simplicity of the construction versus the complexity of the proof.

  1. The Algorithm: The authors use a "Greedy Algorithm." You look at every edge in the original graph (sorted by weight) and add it to your spanner only if there isn't already a short path between those two nodes that can survive $f$ faults. While this algorithm is a natural extension of standard spanner construction, proving it produces a small graph is notoriously difficult.
  2. The Analysis (The "Blockade" Technique): To prove the upper bound, the authors had to count "closed walks" (loops) in the graph. For higher stretch factors ($k \ge 3$), standard counting fails because some parts of the graph might be "denser" than others. They introduced a novel technique called blockades. By identifying and "blocking" certain irregular paths, they were able to use an inductive counting argument to show the total number of edges remains small.
  3. Lower Bounds: To prove their results were optimal, they used constructions based on the Erdős Girth Conjecture, a famous hypothesis in graph theory about the relationship between the number of edges and the shortest cycle in a graph.

Datasets

As a theoretical paper in graph theory and algorithms, this work does not use empirical datasets. Instead, it uses infinite families of extremal graphs (theoretical graph structures that push mathematical limits) to prove lower bounds and validate the efficiency of the proposed algorithm.

Key Insights and Ideas

  • Sublinear is Possible: The biggest "aha moment" is that fault tolerance is "cheaper" than previously thought. Instead of paying a factor of $f$, you only pay roughly $f^{1-1/k}$. For a stretch of 3 ($k=2$), this means instead of doubling the size for every new fault, the size only grows by the square root of the number of faults.
  • Greedy is Good: The paper shows that the most "obvious" algorithm—the greedy one—is actually the optimal one. This is a major win for practitioners, as greedy algorithms are easy to implement and reason about.
  • Vertex vs. Edge Faults: The authors show that for vertex faults, their bound is perfectly tight. Interestingly, they found that edge-fault tolerance follows the same upper bounds but might have different lower-bound characteristics for high stretch factors.

Key Results

  • Optimal Size: For an $n$-node graph and $f$ vertex faults, a $(2k-1)$-stretch spanner requires only $O_k(f^{1-1/k}n^{1+1/k})$ edges.
  • Optimality: They prove this is the best possible result (unless the Erdős Girth Conjecture is false). Any data structure providing these distance guarantees must use at least this much space.
  • First Sublinear Bound: This is the first known instance in fault-tolerant network design where adding resilience costs a sublinear factor in the number of faults.

Limitations and Future Work

  • Fixed Stretch: The "Optimal" part of the title refers to the setting where the stretch factor $k$ is a fixed constant. If $k$ grows with the size of the graph, the bounds may change.
  • The Exponential Constant: The $O_k$ notation hides a factor that is exponential in $k$ ($2^{O(k)}$). While this is "constant" for small $k$, it becomes a bottleneck for very large stretch factors.
  • The Edge-Fault Gap: For edge-fault tolerance with stretch $k \ge 3$, there is still a small gap between the proven upper bound and the known lower bound. Closing this specific gap remains an open problem for the community.

Summary updated

Abstract

A k-spanner of a graph G is a sparse subgraph H whose shortest path distances match those of G up to a multiplicative error k. In this paper we study spanners that are resistant to faults. A subgraph H ⊆ G is an f vertex fault tolerant (VFT) k-spanner if H \ F is a k-spanner of G \ F for any small set F of f vertices that might “fail.” One of the main questions in the area is: what is the minimum size of an f fault tolerant k-spanner that holds for all n node graphs (as a function of f, k and n)? This question was first studied in the context of geometric graphs [Levcopoulos et al. STOC ’98, Czumaj and Zhao SoCG ’03] and has more recently been considered in general undirected graphs [Chechik et al. STOC ’09, Dinitz and Krauthgamer PODC ’11]. In this paper, we settle the question of the optimal size of a VFT spanner, in the setting where the stretch factor k is fixed. Specifically, we prove that every (undirected, possibly weighted) n-node graph G has a (2k – 1)-spanner resilient to f vertex faults with Ok (f1–1/kn1+1/k) edges, and this is fully optimal (unless the famous Erdös Girth Conjecture is false). Our lower bound even generalizes to imply that no data structure capable of approximating distG\F (s, t) similarly can beat the space usage of our spanner in the worst case. To the best of our knowledge, this is the first instance in fault tolerant network design in which introducing fault tolerance to the structure increases the size of the (non-FT) structure by a sublinear factor in f. Another advantage of this result is that our spanners are constructed by a very natural and simple greedy algorithm, which is the obvious extension of the standard greedy algorithm used to build spanners in the non-faulty setting. We also consider the edge fault tolerant (EFT) model, defined analogously with edge failures rather than vertex failures. We show that the same spanner upper bound applies in this setting. Our data structure lower bound extends to the case k = 2 (and hence we close the EFT problem for 3-approximations), but it falls to D(f 1/2-1/(2k) · n1+1/k) for k > 3. We leave it as an open problem to close this gap.
BibTeX
@inproceedings{bodwin2018optimal,
  author = {Greg Bodwin and Michael Dinitz and Merav Parter and Virginia Vassilevska Williams},
  title = {{Optimal Vertex Fault Tolerant Spanners (for fixed stretch)}},
  booktitle = {SODA},
  year = {2018},
  url = {https://openreview.net/forum?id=ks2QF8mgCm1},
}

Loading related content...

Figure