2026-08-16T20:29:29Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12432 2024-03-06T10:50:07Z ddc:004 open_access

New Extremal Bounds for Reachability and Strong-Connectivity Preservers Under Failures Chakraborty, Diptarka Choudhary, Keerti Preservers Strong-connectivity Reachability Fault-tolerant Graph sparsification 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{|P|√n, n√|P|}) bound on a subgraph that is an 1-fault-tolerant reachability preserver for a given vertex-pair set P ⊆ V× V, i.e., it preserves reachability between any pair of vertices in P under single edge (or vertex) failure. Our result is a significant improvement over the previous best O(n |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. - In the lower bound side, we show that a 2-fault-tolerant reachability preserver for a vertex-pair set P ⊆ V×V of size Ω(n^ε), for even any arbitrarily small ε, requires at least Ω(n^(1+ε/8)) edges. This refutes the existence of linear-sized dual fault-tolerant preservers for reachability for any polynomial sized vertex-pair set. - We also present the first sub-quadratic bound of at most Õ(k 2^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]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Diptarka Chakraborty and Keerti Choudhary 2020 Is Part Of LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2020.25 urn:nbn:de:0030-drops-124327 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.25 eng https://creativecommons.org/licenses/by/3.0/legalcode