pith. sign in

arxiv: 2402.12832 · v8 · submitted 2024-02-20 · 💻 cs.DS

Nearly Optimal Fault Tolerant Distance Oracle

Dipan Dey , Manoj Gupta This is my paper

Pith reviewed 2026-05-24 03:42 UTC · model grok-4.3

classification 💻 cs.DS
keywords fault tolerant distance oracleshortest pathedge faultsundirected weighted graphdata structurequery timespace complexity
0
0 comments X

The pith

An f-fault tolerant distance oracle answers shortest paths avoiding f faulty edges in O((c f log (nW))^{O(f^2)}) time using O(f^4 n^2 log^2 (nW)) space.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper constructs an f-fault tolerant distance oracle for undirected graphs with integer edge weights from 1 to W. It allows precomputing a data structure that, for any set of f faulty edges F, source s, and target t, returns the shortest path from s to t that avoids all edges in F. The achieved query time is O((c f log (nW))^{O(f^2)}) and the space is O(f^4 n^2 log^2 (nW)), where c is a constant. For any fixed constant f this performance is nearly optimal up to logarithmic factors. This matters because it provides an efficient way to handle a small number of link failures in routing without recomputing paths from scratch each time.

Core claim

We present an f-fault tolerant distance oracle for an undirected weighted graph where each edge has an integral weight from [1 … W]. Given a set F of f edges, as well as a source node s and a destination node t, our oracle returns the shortest path from s to t avoiding F in O((c f log (nW))^{O(f^2)}) time, where c > 1 is a constant. The space complexity of our oracle is O(f^4 n^2 log^2 (nW)). For a constant f, our oracle is nearly optimal both in terms of space and time (barring some logarithmic factor).

What carries the argument

The f-fault tolerant distance oracle, a data structure built on the graph to support fast queries for shortest paths that avoid any given set of f edges.

If this is right

  • The query time depends only on f and logarithmic terms in n and W when f is fixed.
  • The space usage is quadratic in n multiplied by a polynomial factor in f and log W.
  • For constant f the bounds are nearly optimal up to logs, matching known lower bounds in the leading terms.
  • The oracle works for any static undirected graph with positive integer edge weights and can be built once before faults appear.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The construction might extend to a constant number of vertex faults using similar reduction ideas.
  • Network routing systems could use the oracle to precompute responses for frequent small failure sets.
  • It could serve as a building block for handling slowly changing edge weights in nearly static networks.
  • Tighter lower bounds on fault-tolerant oracles could be derived by comparing against this upper bound.

Load-bearing premise

The graph is static and undirected with fixed positive integer edge weights and the oracle is constructed before the faults are known.

What would settle it

A family of graphs where any f-fault tolerant distance oracle requires more than O(f^4 n^2 log^2 (nW)) space for constant f would falsify the near-optimality claim.

Figures

Figures reproduced from arXiv: 2402.12832 by Dipan Dey, Manoj Gupta.

Figure 1
Figure 1. Figure 1: X is the set of green vertices and Y is the set of blue vertices. x satisfies (a) and y satisfies (b). (a) If u is the nearest vertex of V(F) from x, then |x p| < (xu)2 , and (b) If v is the nearest vertex of V(F) from y, then | yq| < ( y v)2 Intuitively, x is closer to p than the nearest faulty edge. Similarly, y is closer to q than the nearest faulty edge. We will see later that we can design maximisers … view at source ↗
Figure 2
Figure 2. Figure 2: X is the set of green vertices and Y is the set of blue vertices. x satisfies (a) and y satisfies (b). 5 A new tool: Jump Sequence Let R = st ⋄ F ′ where F ′ ⊆ F and F is a set of edges of size f . Let u be a vertex in V(F). Consider the sequence of vertices x1 = s, x2 , x3 ,... , xk where, for 1 ≤ i ≤ k − 1, xi is the first vertex on path R from xi−1 satisfying |R[xi−1 , xi ]| ≥ max{1,(xi−1u ⋄ F)2 } (1) I… view at source ↗
Figure 3
Figure 3. Figure 3: A jump from xi−1 using u. Note that we can start the sequence from either s or t, yielding different sequences. We denote JUMP(R[s, t]) as the sequence starting from s and JUMP(R[t,s]) as the other sequence. In this section, we focus on JUMP(R[s, t]), and all our results apply to R[t,s] by symmetry. In JUMP(R[s, t]), we advance along R[s, t] in steps of (x1u ⋄ F)2 , (x2u ⋄ F)2 , and so on. Note that if u i… view at source ↗
Figure 4
Figure 4. Figure 4: u can lie only on the violet subpath of R. The horizontal black path is Pi . Some remarks are in order. The above statement is one of the most important deductions in our paper. We are able to prove that u does not lie on Pi but lies on the detour of R. This will help us in proving that u satisfies (P2). We will now show that Tx (u) contains no endpoints from V(F). For contradiction, let ek = (ak , bk ) be… view at source ↗
Figure 5
Figure 5. Figure 5: If ai ∈ Tx (u), then Pi [s, t] contains u and this contradicts Equation (12). ii. bk cannot lie in Tx (u) If bk is nearest to u in Tx (u), then our arguments are the same as in Case (a)(ii). Thus, u satisfies (P2) and it is an x-clean vertex. u ak bk s t x Pi Pk R [PITH_FULL_IMAGE:figures/full_fig_p021_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Here the blue path is Pi . su is intact from failure F and is in the first segment of R. So, the detour of R starts somewhere in the dashed path from u to ak . Or the detour starts on Pk . This contradicts our assumption in (S1) that the detour starts on Pi . 9.3.2 Running time and the size of INTERMEDIATE set The running time is dominated by Line 8 of FIND-INTERMEDIATE2 (x, y,φ, v). In this line, the proc… view at source ↗
read the original abstract

We present an $f$-fault tolerant distance oracle for an undirected weighted graph where each edge has an integral weight from $[1 \dots W]$. Given a set $F$ of $f$ edges, as well as a source node $s$ and a destination node $t$, our oracle returns the \emph{shortest path} from $s$ to $t$ avoiding $F$ in $O((cf \log (nW))^{O(f^2)})$ time, where $c > 1$ is a constant. The space complexity of our oracle is $O(f^4n^2\log^2 (nW))$. For a constant $f$, our oracle is nearly optimal both in terms of space and time (barring some logarithmic factor).

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 0 minor

Summary. The manuscript presents an f-fault-tolerant exact distance oracle for undirected graphs with positive integer edge weights in [1..W]. Given any set F of f edges, source s, and target t, the oracle returns the shortest s-t path avoiding F. The claimed space is O(f^4 n^2 log^2 (nW)) and query time is O((c f log (nW))^{O(f^2)}) for a constant c>1. The construction is static (preprocess once before faults are revealed) and is asserted to be nearly optimal for constant f up to logarithmic factors.

Significance. If the claimed construction and analysis are correct, the result would be a notable advance for fault-tolerant distance oracles, supplying the first explicit polynomial-in-f space bound together with query time whose dependence on f is exp(O(f^2)) while remaining polynomial in log(nW). This would improve substantially on prior work for small constant f and would be of direct interest to the data-structure and network-algorithm communities.

major comments (1)
  1. Abstract: the manuscript consists solely of the abstract, which states the final space and time bounds without any derivation, proof sketch, construction details, or supporting data. It is therefore impossible to verify whether the mathematics actually supports the stated claim. This is load-bearing for the central contribution.

Simulated Author's Rebuttal

1 responses · 1 unresolved

We thank the referee for their review. We respond point-by-point to the sole major comment below.

read point-by-point responses

  1. Referee: [—] Abstract: the manuscript consists solely of the abstract, which states the final space and time bounds without any derivation, proof sketch, construction details, or supporting data. It is therefore impossible to verify whether the mathematics actually supports the stated claim. This is load-bearing for the central contribution.

    Authors: We agree that the text supplied with this query consists only of the abstract and contains no construction, proof sketch, or analysis. Consequently it is not possible to verify the claimed bounds from the given material. The arXiv version (2402.12832) is stated to contain the full details, but those details are not reproduced here. revision: yes

standing simulated objections not resolved
  • Verification of the correctness of the space and query-time bounds, because no construction or proof is supplied in the manuscript text provided to us.

Circularity Check

0 steps flagged

No circularity: explicit construction with independent bounds

full rationale

The paper states an explicit algorithmic construction of an f-fault-tolerant exact distance oracle on undirected weighted graphs, giving concrete space O(f^4 n^2 log^2(nW)) and query time O((c f log(nW))^{O(f^2)}) bounds directly from the construction. No equations, fitted parameters, self-citations, or ansatzes appear in the provided abstract or high-level claim that would reduce the stated result to its own inputs by definition. The result is presented as a new data structure whose performance is derived from its preprocessing and query procedures rather than renamed or fitted quantities. This is the normal case of a self-contained algorithmic claim.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Review performed on abstract only; the ledger records only the domain assumptions explicitly stated in the abstract.

axioms (1)
  • domain assumption The input graph is undirected with positive integral edge weights in [1..W]
    Explicitly stated in the abstract.

pith-pipeline@v0.9.0 · 5653 in / 1267 out tokens · 31943 ms · 2026-05-24T03:42:14.051057+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

39 extracted references · 39 canonical work pages

  1. [1]

    Restoration by path concatenation: fast recovery of MPLS paths

    Yehuda Afek, Anat Bremler - Barr, Haim Kaplan, Edith Cohen, and Michael Merritt. Restoration by path concatenation: fast recovery of MPLS paths. Distributed Computing , 15(4):273--283, 2002

    work page 2002

  2. [2]

    A refined laser method and faster matrix multiplication

    Josh Alman and Virginia Vassilevska Williams. A refined laser method and faster matrix multiplication. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 522--539. SIAM, 2021

    work page 2021

  3. [3]

    Approximate distance sensitivity oracles in subquadratic space

    Davide Bil \`o , Shiri Chechik, Keerti Choudhary, Sarel Cohen, Tobias Friedrich, Simon Krogmann, and Martin Schirneck. Approximate distance sensitivity oracles in subquadratic space. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing , pages 1396--1409, 2023

    work page 2023

  4. [4]

    Aaron Bernstein and David R. Karger. Improved distance sensitivity oracles via random sampling. In Shang - Hua Teng, editor, Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, San Francisco, California, USA, January 20-22, 2008 , pages 34--43. SIAM , 2008

    work page 2008

  5. [5]

    A nearly optimal oracle for avoiding failed vertices and edges

    Aaron Bernstein and David Karger. A nearly optimal oracle for avoiding failed vertices and edges. In Proceedings of the forty-first annual ACM symposium on Theory of computing , pages 101--110. ACM, 2009

    work page 2009

  6. [6]

    A nearly optimal oracle for avoiding failed vertices and edges

    Aaron Bernstein and David Karger. A nearly optimal oracle for avoiding failed vertices and edges. In Proceedings of the forty-first annual ACM symposium on Theory of computing , pages 101--110, 2009

    work page 2009

  7. [7]

    Approximate shortest paths avoiding a failed vertex: Near optimal data structures for undirected unweighted graphs

    Surender Baswana and Neelesh Khanna. Approximate shortest paths avoiding a failed vertex: Near optimal data structures for undirected unweighted graphs. Algorithmica , 66:18--50, 2013

    work page 2013

  8. [8]

    Distance sensitivity oracles with subcubic preprocessing time and fast query time

    Shiri Chechik and Sarel Cohen. Distance sensitivity oracles with subcubic preprocessing time and fast query time. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing , pages 1375--1388, 2020

    work page 2020

  9. [9]

    (1 + )-approximate f-sensitive distance oracles

    Shiri Chechik, Sarel Cohen, Amos Fiat, and Haim Kaplan. (1 + )-approximate f-sensitive distance oracles. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19 , pages 1479--1496, 2017

    work page 2017

  10. [10]

    All-pairs shortest paths with real weights in o (n 3/log n) time

    Timothy M Chan. All-pairs shortest paths with real weights in o (n 3/log n) time. In Algorithms and Data Structures: 9th International Workshop, WADS 2005, Waterloo, Canada, August 15-17, 2005. Proceedings 9 , pages 318--324. Springer, 2005

    work page 2005

  11. [11]

    More algorithms for all-pairs shortest paths in weighted graphs

    Timothy M Chan. More algorithms for all-pairs shortest paths in weighted graphs. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing , pages 590--598, 2007

    work page 2007

  12. [12]

    All-pairs shortest paths with real weights in o (n 3/log n) time

    Timothy M Chan. All-pairs shortest paths with real weights in o (n 3/log n) time. Algorithmica , 50:236--243, 2008

    work page 2008

  13. [13]

    Matrix multiplication via arithmetic progressions

    Don Coppersmith and Shmuel Winograd. Matrix multiplication via arithmetic progressions. In Proceedings of the nineteenth annual ACM symposium on Theory of computing , pages 1--6, 1987

    work page 1987

  14. [14]

    A more efficient algorithm for the min-plus multiplication

    Wlodzimierz Dobosiewicz. A more efficient algorithm for the min-plus multiplication. International journal of computer mathematics , 32(1-2):49--60, 1990

    work page 1990

  15. [15]

    Dual-failure distance and connectivity oracles

    Ran Duan and Seth Pettie. Dual-failure distance and connectivity oracles. In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, New York, NY, USA, January 4-6, 2009 , pages 506--515, 2009

    work page 2009

  16. [16]

    Maintaining exact distances under multiple edge failures

    Ran Duan and Hanlin Ren. Maintaining exact distances under multiple edge failures. In Stefano Leonardi and Anupam Gupta, editors, STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022 , pages 1093--1101. ACM , 2022

    work page 2022

  17. [17]

    Oracles for distances avoiding a failed node or link

    Camil Demetrescu, Mikkel Thorup, Rezaul Alam Chowdhury, and Vijaya Ramachandran. Oracles for distances avoiding a failed node or link. SIAM J. Comput. , 37(5):1299--1318, 2008

    work page 2008

  18. [18]

    Algorithm 97

    Robert W Floyd. Algorithm 97. Comm. ACM , 5:345, 1967

    work page 1967

  19. [19]

    New bounds on the complexity of the shortest path problem

    Michael L Fredman. New bounds on the complexity of the shortest path problem. SIAM Journal on Computing , 5(1):83--89, 1976

    work page 1976

  20. [20]

    Powers of tensors and fast matrix multiplication

    Fran c ois Le Gall. Powers of tensors and fast matrix multiplication. In International Symposium on Symbolic and Algebraic Computation, ISSAC '14, Kobe, Japan, July 23-25, 2014 , pages 296--303, 2014

    work page 2014

  21. [21]

    Constructing a distance sensitivity oracle in O (n^ 2.5794 M ) time

    Yong Gu and Hanlin Ren. Constructing a distance sensitivity oracle in O (n^ 2.5794 M ) time. In Nikhil Bansal, Emanuela Merelli, and James Worrell, editors, 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12-16, 2021, Glasgow, Scotland (Virtual Conference) , volume 198 of LIPIcs , pages 76:1--76:20. Schloss Dagstuhl...

    work page 2021

  22. [22]

    Generic single edge fault tolerant exact distance oracle

    Manoj Gupta and Aditi Singh. Generic single edge fault tolerant exact distance oracle. In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic , pages 72:1--72:15, 2018

    work page 2018

  23. [23]

    Faster replacement paths and distance sensitivity oracles

    Fabrizio Grandoni and Virginia Vassilevska Williams. Faster replacement paths and distance sensitivity oracles. ACM Transactions on Algorithms (TALG) , 16(1):1--25, 2019

    work page 2019

  24. [24]

    Improved algorithm for all pairs shortest paths

    Yijie Han. Improved algorithm for all pairs shortest paths. Information Processing Letters , 91(5):245--250, 2004

    work page 2004

  25. [25]

    An o (n 3 (loglog n/log n) 5/4) time algorithm for all pairs shortest paths

    Yijie Han. An o (n 3 (loglog n/log n) 5/4) time algorithm for all pairs shortest paths. In European Symposium on Algorithms , pages 411--417. Springer, 2006

    work page 2006

  26. [26]

    An o (n 3 (log log n/log n) 5/4) time algorithm for all pairs shortest path

    Yijie Han. An o (n 3 (log log n/log n) 5/4) time algorithm for all pairs shortest path. Algorithmica , 51:428--434, 2008

    work page 2008

  27. [27]

    Vickrey prices and shortest paths: What is an edge worth? In Proceedings 42nd IEEE symposium on foundations of computer science , pages 252--259

    John Hershberger and Subhash Suri. Vickrey prices and shortest paths: What is an edge worth? In Proceedings 42nd IEEE symposium on foundations of computer science , pages 252--259. IEEE, 2001

    work page 2001

  28. [28]

    Sensitivity and dynamic distance oracles via generic matrices and frobenius form

    Adam Karczmarz and Piotr Sankowski. Sensitivity and dynamic distance oracles via generic matrices and frobenius form. In 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, Santa Cruz, CA, USA, November 6-9, 2023 , 2023

    work page 2023

  29. [29]

    Sparse fault-tolerant bfs trees

    Merav Parter and David Peleg. Sparse fault-tolerant bfs trees. In European Symposium on Algorithms , pages 779--790. Springer, 2013

    work page 2013

  30. [30]

    On the complexity of matrix multiplication

    Andrew James Stothers. On the complexity of matrix multiplication. 2010

    work page 2010

  31. [31]

    A new upper bound on the complexity of the all pairs shortest path problem

    Tadao Takaoka. A new upper bound on the complexity of the all pairs shortest path problem. Information Processing Letters , 43(4):195--199, 1992

    work page 1992

  32. [32]

    A faster algorithm for the all-pairs shortest path problem and its application

    Tadao Takaoka. A faster algorithm for the all-pairs shortest path problem and its application. In Computing and Combinatorics: 10th Annual International Conference, COCOON 2004, Jeju Island, Korea, August 17-20, 2004. Proceedings 10 , pages 278--289. Springer, 2004

    work page 2004

  33. [33]

    An o (n3loglogn/logn) time algorithm for the all-pairs shortest path problem

    Tadao Takaoka. An o (n3loglogn/logn) time algorithm for the all-pairs shortest path problem. Information Processing Letters , 96(5):155--161, 2005

    work page 2005

  34. [34]

    Sensitive distance and reachability oracles for large batch updates

    Jan van den Brand and Thatchaphol Saranurak. Sensitive distance and reachability oracles for large batch updates. In David Zuckerman, editor, 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019 , pages 424--435. IEEE Computer Society, 2019

    work page 2019

  35. [35]

    A theorem on boolean matrices

    Stephen Warshall. A theorem on boolean matrices. Journal of the ACM (JACM) , 9(1):11--12, 1962

    work page 1962

  36. [36]

    Multiplying matrices faster than coppersmith-winograd

    Virginia Vassilevska Williams. Multiplying matrices faster than coppersmith-winograd. In Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012 , pages 887--898, 2012

    work page 2012

  37. [37]

    Faster all-pairs shortest paths via circuit complexity

    Ryan Williams. Faster all-pairs shortest paths via circuit complexity. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing , pages 664--673, 2014

    work page 2014

  38. [38]

    Replacement paths and distance sensitivity oracles via fast matrix multiplication

    Oren Weimann and Raphael Yuster. Replacement paths and distance sensitivity oracles via fast matrix multiplication. ACM Trans. Algorithms , 9(2), March 2013

    work page 2013

  39. [39]

    A slightly improved sub-cubic algorithm for the all pairs shortest paths problem with real edge lengths

    Uri Zwick. A slightly improved sub-cubic algorithm for the all pairs shortest paths problem with real edge lengths. In International Symposium on Algorithms and Computation , pages 921--932. Springer, 2004

    work page 2004