Efficient Fault-Tolerant Search by Fast Indexing of Subnetworks

We design sensitivity oracles for error-prone networks. For a network problem Π, the data structure preprocesses a network G = (V, E) and sensitivity parameter f such that, for any set F ⊆ V ∪ E of up to f link or node failures, it can report the solution of Π in G−F. We study three network problems Π. • L-HOP SHORTEST PATH: Given s, t ∈ V, is there a shortest s-t-path in G−F with at most L links? • k-PATH: Does G−F contain a simple path with k links? • k-CLIQUE: Does G−F contain a clique of k nodes? Our main technical contribution is a new construction of (L, f)-replacement path coverings ((L, f)-RPC) in the parameter realm where f = o(log L). An (L, f)-RPC is a family G of subnetworks of G which, for every F ⊆E with |F|< f, has a subfamily GF ⊆G such that (i) no subnetwork in GF contains a link of F and (ii) for each s, t∈V, if G−F contains a shortest s-t-path with at most L links, then some subnetwork in GF retains at least one such path. Our (L, f)-RPC has almost the same size as the one by Weimann and Yuster (2013) but it improves the time to query GF from Oe(f2Lf) to Oe(f25 Lo(1)). It also improves over the size and query time of the (L, f)-RPC by Karthik and Parter (2021) by nearly a factor of L. From this construction, we derive oracles for L-HOP SHORTEST PATH, k-PATH, and k-CLIQUE. Notably, our solution for k-PATH improves the query time of the one by Bilò et al. (2022a) for f = o(log k).