Near-Optimal Fault-Tolerant Strong Connectivity Preservers

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 Ω(2kn) 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 Ω(n1−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(k4knlogn) edges, and we can construct one with O(8knlog5/2n) edges in poly(2kn) 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(k4knlogn) 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.