Optimal strong connectivity preservers found with efficient two-edge failure handling

Optimal-Size Strong Connectivity Preservers under Two Edge Failures in Subcubic Time

Data Structures and Algorithms

Summary

Strong connectivity preservers are smaller graphs that keep the important connection structure of the original graph even if some connections fail. The authors found the smallest possible size of these preservers when up to two connections fail, proving it grows like N times log N for large graphs. They also developed a randomized algorithm that quickly builds these preservers in subcubic time. This work closes previous gaps in understanding how large these preservers need to be and how fast they can be computed.

What this means in practice

  • For network reliability engineers: Design fault-resilient communication networks that maintain connectivity after two link failures with optimally compact monitoring structures.
  • For distributed system architects: Build efficient network overlays that preserve connectivity under multiple link failures using minimal additional infrastructure.

A theory result. No direct application yet.

Authors

Wanhee Lee, Chenglin Fan

Abstract

A $k$-edge-failure strong connectivity preserver of a directed graph on $N$ vertices is a spanning subgraph that has the same strongly connected components as the input after each set of at most $k$ edge deletions. The lower-bound construction of Baswana, Choudhary, and Roditty [BCR18], adapted to strong connectivity in [CC20], gives the previous best bound of $Ω(2^kN)$ necessary edges. Hoppenworth, Saranurak, and Wang [HSW25] prove an $O(k4^kN\log N)$ upper bound, leaving a logarithmic gap for fixed $k$. We close this gap by giving an explicit strongly connected graph on $N=2^d$ vertices with $N-1+(N/2)\log_2N$ edges, every one of which is necessary in a two-failure preserver. Together with the upper bound of [HSW25], this proves that the optimal size in the worst case is $Θ_k(N\log N)$ for every fixed $k\geq2$, whereas it is $Θ(N)$ for $k=1$ [GIP20]. The same graph has a one-failure preserver with at most $3(N-1)$ edges. We also give a randomized algorithm that either returns a spanning subgraph or reports failure. For every fixed $c,\varepsilon>0$, with probability at least $1-N^{-c}$ it returns a correct preserver for $k=2$ with $O(N\log N)$ edges, in $\widetilde O(N^{(ω+3)/2+\varepsilon})$ time and $\widetilde O(N^2)$ space. Here $ω$ is the matrix multiplication exponent over a fixed finite field.