Efficient Fault-Tolerant Search by Fast Indexing of Subnetworks
Davide Bilò, Keerti Choudhary, Sarel Cohen, Tobias Friedrich, Martin Schirneck
Abstract
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 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 in 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 set F of at most f links, has a subfamily G'_F such that (i) no subnetwork in G'_F contains a link of F and (ii) for each s,t in V, if G-F contains a shortest s-t-path with at most L links, then some subnetwork in G'_F 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 G'_F from Õ(f^2 L^f) to Õ(f^(5/2) L^o(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ò for f=o(log k).
BibTeX
@article{Bilò_Choudhary_Cohen_Friedrich_Schirneck_2025, title={Efficient Fault-Tolerant Search by Fast Indexing of Subnetworks}, volume={39}, url={https://ojs.aaai.org/index.php/AAAI/article/view/34846}, DOI={10.1609/aaai.v39i25.34846}, abstractNote={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 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 in 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 set F of at most f links, has a subfamily G’_F such that (i) no subnetwork in G’_F contains a link of F and (ii) for each s,t in V, if G-F contains a shortest s-t-path with at most L links, then some subnetwork in G’_F 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 G’_F from Õ(f^2 L^f) to Õ(f^(5/2) L^o(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ò for f=o(log k).}, number={25}, journal={Proceedings of the AAAI Conference on Artificial Intelligence}, author={Bilò, Davide and Choudhary, Keerti and Cohen, Sarel and Friedrich, Tobias and Schirneck, Martin}, year={2025}, month={Apr.}, pages={26463-26471} }