Optimal Vertex Fault-Tolerant Spanners in Polynomial Time

Greg Bodwin, Michael Dinitz, Caleb Robelle

Abstract

Recent work has pinned down the existentially optimal size bounds for vertex fault-tolerant spanners: for any positive integer $k$, every $n$-node graph has a $(2k-1)$-spanner on $O(f^{1-1/k} n^{1+1/k})$ edges resilient to $f$ vertex faults, and there are examples of input graphs on which this bound cannot be improved. However, these proofs work by analyzing the output spanner of a certain exponential-time greedy algorithm. In this work, we give the first algorithm that produces vertex fault tolerant spanners of optimal size and which runs in polynomial time. Specifically, we give a randomized algorithm which takes $\widetilde{O}\left( f^{1-1/k} n^{2+1/k} + mf^2\right)$ time. We also derandomize our algorithm to give a deterministic algorithm with similar bounds. This reflects an exponential improvement in runtime over [Bodwin-Patel PODC '19], the only previously known algorithm for constructing optimal vertex fault-tolerant spanners.

Introduction

In network design, a spanner is a sparse subgraph that preserves distances between nodes within a small multiplicative factor, known as the stretch. For instance, a 3-spanner ensures that the distance between any two nodes in the subgraph is at most 3 times their distance in the original graph. However, real-world networks are prone to failures. A Fault-Tolerant (FT) Spanner must maintain its stretch properties even if a subset of nodes (vertices) or links (edges) are removed.

While it has been established that "optimal" sized vertex fault-tolerant (VFT) spanners exist—meaning they possess the minimum possible number of edges for a specified level of fault tolerance—constructing them has historically been computationally expensive. The standard "greedy" algorithm for this task requires solving the NP-hard "length-bounded cut" problem for every candidate edge, resulting in an exponential runtime. Previous attempts to develop polynomial-time alternatives often resulted in sub-optimal spanners, typically larger by factors of $k$ or $f$. This paper bridges this gap by providing the first polynomial-time algorithm that constructs VFT spanners of existentially optimal size.

Methodology

The core of this work is the "slack-greedy" framework. Instead of the computationally prohibitive task of checking if an edge is strictly necessary for every possible set of $f$ faults, the authors employ two primary strategies:

1. Randomized Sampling

To determine if an edge $(u, v)$ should be included in the spanner, the algorithm samples several random subgraphs. In each sample, every node (excluding $u$ and $v$) is included with a probability of $1/(2f)$. If the distance between $u$ and $v$ exceeds the stretch threshold in a significant fraction of these samples, the edge is added. This "slack" in the greedy selection process is the key to achieving polynomial runtime.

2. Deterministic Derandomization

The randomized approach is derandomized using a deterministic "set system" built with almost-universal hash functions. By leveraging techniques from Message Authentication Codes (MACs) in cryptography, the authors create a small, efficient family of hash functions that provide the same coverage guarantees as random sampling, ensuring the algorithm remains efficient in a deterministic setting.

3. Algorithmic Efficiency

To further optimize performance, the algorithm utilizes an incremental reachability data structure and a "layered graph" technique. These tools allow for rapid distance updates as edges are added, avoiding the need for full recomputations from scratch.

Key Results

The proposed algorithm achieves the theoretical lower limit for $(2k-1)$-spanners, producing subgraphs with $O(f^{1-1/k}n^{1+1/k})$ edges. Crucially, it transforms the runtime from exponential ($O(mn^{O(f)})$) to polynomial.

Comparison of vertex fault-tolerant spanner algorithms, highlighting the optimal size and polynomial runtime achieved in this work.

As shown in the table above, this work (bottom row) achieves the same optimal spanner size as [BP19] but with a significantly improved runtime of $\widetilde{O}(f^{1-1/k}n^{2+1/k} + mf^2)$. This represents an exponential speedup over previous optimal constructions and even outperforms some sub-optimal polynomial-time algorithms that were off by factors of $k$ or $f$.

Discussion and Future Work

A significant insight of this research is the shift from "global" analysis (e.g., blocking sets) to "local" analysis based on the probability of an edge being useful for a random fault set. Furthermore, the use of cryptographic MACs for derandomization represents a novel application of these techniques in the field of graph spanners. Notably, the "slack-greedy" approach ensures optimal size regardless of the validity of the Erdős Girth Conjecture.

Despite these advances, several open questions remain:

  • Runtime Optimization: While polynomial, the current algorithm is still slower than the near-linear time algorithms available for non-fault-tolerant spanners. Whether an $\widetilde{O}(m)$ algorithm exists for optimal FT spanners is an open question.
  • Edge Fault Tolerance: While the techniques are applicable to edge faults, the theoretical lower bounds for edge-FT spanners are less understood for $k \ge 3$.
  • Distributed Implementation: Greedy algorithms are difficult to parallelize. Future research could investigate achieving these optimal bounds in distributed or parallel computing models.

Summary updated

Abstract

Recent work has pinned down the existentially optimal size bounds for vertex fault-tolerant spanners: for any positive integer $k$, every $n$-node graph has a $(2k-1)$-spanner on $O(f^{1-1/k} n^{1+1/k})$ edges resilient to $f$ vertex faults, and there are examples of input graphs on which this bound cannot be improved. However, these proofs work by analyzing the output spanner of a certain exponential-time greedy algorithm. In this work, we give the first algorithm that produces vertex fault tolerant spanners of optimal size and which runs in polynomial time. Specifically, we give a randomized algorithm which takes $\widetilde{O}\left( f^{1-1/k} n^{2+1/k} + mf^2\right)$ time. We also derandomize our algorithm to give a deterministic algorithm with similar bounds. This reflects an exponential improvement in runtime over [Bodwin-Patel PODC '19], the only previously known algorithm for constructing optimal vertex fault-tolerant spanners.
BibTeX
@inproceedings{bodwin2021optimal,
  author = {Greg Bodwin and Michael Dinitz and Caleb Robelle},
  title = {{Optimal Vertex Fault-Tolerant Spanners in Polynomial Time}},
  booktitle = {SODA},
  year = {2021},
  url = {https://openreview.net/forum?id=11fQ3AK5IA},
}
Figure