Near-Optimal Fault-Tolerant Strong Connectivity Preservers

Abstract

A $k$-fault-tolerant connectivity preserver of a directed $n$-vertex graph $G$ is a subgraph $H$ such that, for any edge set $F\subseteq E(G)$ of size $|F|\le k$, the strongly connected components of $G-F$ and $H-F$ are the same. While some graphs require a preserver with $\Omega (2^{k}n)$ edges [BCR18], the best-known upper bound is $\tilde{O}(k{2}^k{n}^{2-1/k})$ edges [CC20], leaving a significant gap of $\Omega (n^{1-1/k})$. In contrast, there is no gap in undirected graphs; the optimal bound of $\Theta (kn)$ has been well-established since the 90s [NI92]. We nearly close the gap for directed graphs; we prove that there exists a $k$-fault-tolerant connectivity preserver with $O(k{4}^{k}n\log n)$ edges, and we can construct one with $O(8^{k}n{\log }^{5/2}n)$ edges in $\text{poly}(2^{k}n)$ time. Our results also improve the state-of-the-art for a closely related object; a \textit{$k$-connectivity preserver} of $G$ is a subgraph $H$ where, for all $i\le k$, the strongly $i$-connected components of $G$ and $H$ agree. By a known reduction, we obtain a $k$-connectivity preserver with $O(k{4}^{k}n\log n)$ edges, improving the previous best bound of $\tilde{O}(k{2}^k{n}^{2-1/(k-1)})$ [CC20]. Therefore, for any constant $k$, our results are optimal to a $\log n$ 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(n\sqrt{kn})$ edges.

FOCS 2025