New Extremal bounds for Reachability and Strong-Connectivity Preservers under failures

In this paper, we consider the question of computing sparse subgraphs for any input directed graph \(G=(V,E)\) on \(n\) vertices and \(m\) edges, that preserves reachability and/or strong connectivity structures. We show \(O(n+\min\{|{\mathcal{P}}|\sqrt{n},n\sqrt{|{\mathcal{P} }|}\})\) bound on a subgraph that is an \(1\) -fault-tolerant reachability preserver for a given vertex-pair set \({\mathcal{P}}\subseteq V\times V\) , i.e., it preserves reachability between any pair of vertices in \({\mathcal{P}}\) under single edge (or vertex) failure. Our result is a significant improvement over the previous best \(O(n|{\mathcal{P}}|)\) bound obtained as a corollary of single-source reachability preserver construction. We prove our upper bound by exploiting the special structure of single fault-tolerant reachability preserver for any pair, and then considering the interaction among such structures for different pairs. We also present the first sub-quadratic bound of at most \(\tilde{O}(k2^{k}n^{2-1/k})\) size, for strong-connectivity preservers of directed graphs under \(k\) failures. To the best of our knowledge no non-trivial bound for this problem was known before, for a general \(k\) . We get our result by adopting the color-coding technique of Alon, Yuster, and Zwick [JACM’95].