Pairwise Reachability Oracles and Preservers Under Failures

Abstract

In this paper, we consider reachability oracles and reachability preservers for directed graphs/networks prone to edge/node failures. Let G = (V, E) be a directed graph on n-nodes, and P ⊆ V ×V be a set of vertex pairs in G. We present the first non-trivial constructions of single and dual fault-tolerant pairwise reachability oracle with constant query time. Furthermore, we provide extremal bounds for sparse fault-tolerant reachability preservers, resilient to two or more failures. Prior to this work, such oracles and reachability preservers were widely studied for the special scenario of single-source and all-pairs settings. However, for the scenario of arbitrary pairs, no prior (non-trivial) results were known for dual (or more) failures, except those implied from the single-source setting. One of the main questions is whether it is possible to beat the O(n|P|) size bound (derived from the single-source setting) for reachability oracle and preserver for dual failures (or O(2kn|P|) bound for k failures). We answer this question affirmatively. Below we summarize our contributions. For an n-vertex directed graph G = (V, E) and P ⊆ V × V, we present a construction of O(np|P|) sized dual fault-tolerant pairwise reachability oracle with constant query time. We further provide a matching (up to the word size) lower bound of Ω(np|P|) on the size (in bits) of the oracle for the dual fault setting, thereby proving that our oracle is (near-)optimal. Next, we provide a construction of O(n + min{|P|√n, np|P|}) sized oracle with O(1) query time, resilient to single node/edge failure. In particular, for |P| bounded by O(√n) this yields an oracle of just O(n) size. We complement the upper bound with a lower bound of Ω(n2/3|P|1/2) (in bits), refuting the possibility of a linear-sized oracle for P of size ω(n2/3). We also present a construction of O(n4/3|P|1/3) sized pairwise reachability preservers resilient to dual edge/vertex failures. Previously, such preservers were known to exist only under single failure and had O(n + min{|P|√n, np|P|}) size [Chakraborty and Choudhary, ICALP'20]. We also show a lower bound of Ω(np|P|) edges on the size of dual fault-tolerant reachability preservers, thereby providing a sharp gap between single and dual fault-tolerant reachability preservers for |P| = o(n). Finally, we provide a generic pairwise reachability preserver construction that provides a o(2kn|P|) sized subgraph resilient to k failures, for any k ≥ 1. Before this work, we only knew of an O(2kn|P|) bound implied from the single-source setting [Baswana, Choudhary, and Roditty, STOC'16].