FOCS Conference 2025 Conference Paper
Near-Optimal Fault-Tolerant Strong Connectivity Preservers
- Gary Hoppenworth
- Thatchaphol Saranurak
- Benyu Wang
A k-fault-tolerant connectivity preserver of a directed n-vertex graph G is a subgraph H such that, for any edge set F ⊆ E(G) of size |F| ≤ k, the strongly connected components of G−F and H −F are the same. While some graphs require a preserver with Ω(2 k n) edges [1], the best-known upper bound is $\tilde O\left( {k{2^k}{n^{2 - /k}}} \right)$ edges [2], leaving a significant gap of Ω(n 1−1/k ). In contrast, there is no gap in undirected graphs; the optimal bound of Θ(kn) has been well-established since the 90s [3]. We nearly close the gap for directed graphs; we prove that there exists a k-fault-tolerant connectivity preserver with O(k4 k nlogn) edges, and we can construct one with O(8 k nlog 5/2 n) edges in poly(2 k n) time. Our results also improve the state-of-the-art for a closely related object; a k-connectivity preserver of G is a subgraph H where, for all i ≤ k, the strongly i-connected components of G and H agree. By a known reduction, we obtain a k-connectivity preserver with O(k4 k nlogn) edges, improving the previous best bound of $\tilde O\left( {k{2^k}{n^{2 - 1/(k - 1)}}} \right)$ [2]. Therefore, for any constant k, our results are optimal to a logn factor for both problems. Lastly, we show that the exponential dependency on k is not inherent for k-connectivity preservers by presenting another construction with $O\left( {n{\text{ }}\sqrt {kn} } \right)$ edges.