Research map / Learning theory and algorithms / Combinatorial and search optimization
Efficient Fault-Tolerant Search by Fast Indexing of Subnetworks
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Builds randomized sampling-tree (L,f)-replacement path coverings that can be queried fast, yielding sensitivity oracles for L-hop shortest path, k-Path and k-Clique under failures.
Problem
Fault-tolerant (sensitivity) oracles for network problems: answering L-hop shortest path, k-path and k-clique queries in G minus up to f link/node failures, with small size and fast query time.
Approach
Replace independent random link-deletion subnetworks with sampling trees that add/remove links top-down, so stored subnetworks are grouped and a root-to-leaf walk retrieves relevant subnetworks quickly, keeping the randomized size of Weimann-Yuster while cutting query time.
Key results
- Achieves (L,f)-RPC of size O~(f L^{f+o(1)}) with query time O~(f^{5/2} L^{o(1)}) for f = o(log L), versus O~(f^2 L^f) query time for the randomized baseline.
- Gives k-Path sensitivity oracle with query time O~(4^f f^{2-o(1)} k^{o(1)}) and space O~((k+4)/f)^{f+o(1)} f^{3/2} k, improving query time for f = o(log k).
- Extends fixed-parameter sensitivity oracles to k-Clique with query time O~(4^f f^{2-o(1)} k^{o(1)}), the first such oracle for k-Clique.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| index randomized replacement-path subnetworks with sampling trees | (L,f)-RPC · (L,f)-RPC | query time: \widetilde{O}(f^2 L^f) -> \widetilde{O}(f^{\frac{5}{2}} L^{o(1)}) | Helped |
| index replacement-path subnetworks with sampling trees instead of using the randomized construction | (L,f)-RPC · (L,f)-RPC | total subnetworks: \widetilde{O}(fL^f) -> \widetilde{O}(fL^{f+o(1)}) | No clear effect |
| index replacement-path subnetworks with sampling trees instead of using the deterministic construction | (L,f)-RPC · (L,f)-RPC | total subnetworks: \widetilde{O}(fL)^{f+1} -> \widetilde{O}(fL^{f+o(1)}) | Helped |
| index replacement-path subnetworks with sampling trees instead of using the deterministic construction | (L,f)-RPC · (L,f)-RPC | query time: \widetilde{O}(f^2 L) -> \widetilde{O}(f^{\frac{5}{2}} L^{o(1)}) | Helped |
| use the new construction for k-Path sensitivity oracles | k-Path · k-Path | query time: f^2 2^k \textsf{poly}(k) -> \widetilde{O}(4^f f^{2-o(1)} k^{o(1)}) | Helped |
Limitations
- Assumes f = o(log L); larger f increases size and query time by n^{o(1)} factors.
- Space for distance oracle requires Omega(n^2) storage of distances per leaf.
- Randomized construction; success holds with high probability rather than deterministically.
Experimental setup
Metrics: number of subnetworks query time space preprocessing time
Baselines: Weimann-Yuster (L,f)-RPC Karthik-Parter deterministic (L,f)-RPC Choudhary-Gupta-style k-Path sensitivity oracle
Builds on: Weimann-Yuster replacement path covering Karthik-Parter deterministic RPC fixed-parameter sensitivity oracles for k-Path
Closest papers by meaning
- Approximate Distance Oracle for Fault-Tolerant Geometric Spanners (AAAI 2024 · similarity 0.86)
- Limited Query Graph Connectivity Test (AAAI 2024 · similarity 0.85)
- Sort Before You Prune: Improved Worst-Case Guarantees of the DiskANN Family of Graphs (ICML 2025 · similarity 0.85)
- The Query Complexity of Local Search in Rounds on General Graphs (NeurIPS 2026 · similarity 0.84)
- Paths, Proofs, and Perfection: Developing a Human-Interpretable Proof System for Constrained Shortest Paths (AAAI 2024 · similarity 0.84)
- Query-Limited Community Recovery in Stochastic Block Models (NeurIPS 2026 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.