Pith. sign in

REVIEW 5 minor

A single-source dual-fault distance oracle can approximate replacement paths using only Õ(n√n) space and near-constant query time.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · grok-4.5

2026-07-12 05:32 UTC pith:45OXNHJZ

load-bearing objection First o(n^{2}) dual-fault single-source approximate distance oracle; the three-level FT construction and inductive analysis look solid.

arxiv 2607.02999 v2 pith:45OXNHJZ submitted 2026-07-03 cs.DS

Approximate Single Source Dual Fault Tolerant Distance Oracle

Koustav Das , Manoj Gupta This is my paper
classification cs.DS MSC 68W2505C8568R10
keywords distance oraclefault tolerancesingle sourcedual edge failuresapproximate shortest pathssubquadratic spacedecomposable paths
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

When two edges fail in a weighted undirected network, the shortest remaining path from a fixed source can still be approximated quickly without storing quadratic data. The paper shows how to build a data structure of size roughly n times square-root n that, given any destination and any two failed edges, returns a (1+O(ε))-approximate distance in polylogarithmic time. Earlier single-fault oracles already achieved near-linear space, yet every previous multi-fault construction needed Ω(n^{2}) space; the new result is the first to break that barrier for two faults. The construction works by carefully storing a small tree of candidate replacement paths (segment children and detour children) at every destination, then answering a query by walking a short recursion that reuses those candidates. A sympathetic reader cares because many practical networks experience only a handful of simultaneous failures, so sub-quadratic space finally makes dual-fault oracles usable at large scale.

Core claim

There exists a (1+O(ε))-approximate single-source dual-fault-tolerant distance oracle of size O(n√n log^{4}_{1+ε} nW) that answers queries in O(log^c_{1+ε} nW) time for any constant c. This is the first dual-fault oracle whose space is o(n^{2}).

What carries the argument

The FT(st) tree of segment and detour children: for each destination t a constant-depth tree stores a logarithmic number of 1- and 2-decomposable replacement paths that either avoid an entire segment containing a fault or start a detour as high as possible on that segment; the query simply walks a short recursion over these precomputed children.

Load-bearing premise

After a tiny random perturbation of edge weights, every pair of vertices still has a unique shortest path even when any two edges have failed; without uniqueness the stored detours may miss the true optimum.

What would settle it

Construct a concrete undirected weighted graph on a few dozen vertices, compute the exact dual-fault distances for every t and every pair of edges, then run the oracle and check whether every returned value lies inside the claimed (1+O(ε)) factor of the true distance.

Watch this falsifier — get emailed when new claim-graph text bears on it.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

0 major / 5 minor

Summary. The paper constructs a single-source dual-fault-tolerant distance oracle for undirected graphs with edge weights in [1,W]. After preprocessing, a query consisting of a target t and a set F of at most two failed edges returns a (1+O(ε))-approximation of the length of the shortest s-t path that avoids F. The data structure occupies Õ(n√n) space and answers queries in Õ(1) time (more precisely O(log^c_{1+ε} nW) for a constant c). The construction proceeds by building, for every t, a three-level tree FT(st) whose nodes store carefully chosen 1- and 2-decomposable paths (segment children and detour children ordered by net-point segments). A recursive query algorithm (QUERYDUAL together with the auxiliary QUERYDETOUR) walks this tree, reducing the problem either to a segment-avoiding path or to a recursive call on an affected vertex; correctness is proved by induction on the ordered list of affected vertices plus t, yielding a (1+k^5 ε) guarantee for the k-th vertex. The same framework first yields a simpler single-fault oracle of the same space bound, which is then extended to two faults.

Significance. The result is the first (1+O(ε))-approximate single-source dual-fault oracle whose space is o(n^{2}). All previous multi-fault (1+ε)-approximate oracles, even in the single-source setting, required Ω(n^{2}) space; the paper therefore closes a natural gap left open by the single-fault constructions of Baswana-Khanna and Bilò et al. The technical contribution—an explicit three-level FT tree that stores only O(log^{4}_{1+ε} nW) carefully selected 2-decomposable paths per target, together with a clean inductive analysis that re-uses the classical k-decomposability lemma—is self-contained and appears reusable for related sensitivity problems. The uniqueness-of-shortest-paths assumption (standard infinitesimal perturbation) is the only non-trivial modelling hypothesis and is already employed throughout the cited literature; once it is granted, both the space bound and the approximation factor follow rigorously.

minor comments (5)
  1. The constant hidden by the O(ε) notation is rather large (k^{5} with k≤5). A short remark in the introduction or conclusion quantifying the concrete factor (e.g., 1+3125ε) would help readers who care about the precise dependence on ε.
  2. Section 8 correctly notes that the approach does not extend to three faults and supplies a concrete counter-example configuration. It would be useful to add a one-sentence pointer to the open question of whether a different sampling or hierarchical decomposition can break the quadratic barrier for f=3.
  3. In Algorithm 3 the grey-highlighted blocks that construct 2-decomposable detour children are dense; a short paragraph of prose immediately after the algorithm that restates the two selection criteria (closest-to-x versus closest-to-p) would improve readability.
  4. Lemma 4.4 and Lemma 5.4 claim that membership of an edge in a primary path (and the identity of its segment) can be decided in Õ(1) time. The LCA-based argument is sketched in Appendix B; a one-line citation to the classic Bender-Farach-Colton structure already appears, but an explicit statement that the same structure also returns the net-point indices would make the claim self-contained.
  5. A few typographical inconsistencies remain (e.g., “st⋆e” versus “st⋆F”, occasional missing spaces after commas in asymptotic expressions). A careful copy-edit pass would remove them.

Circularity Check

0 steps flagged

No significant circularity; the dual-fault oracle construction and (1+O(ε)) approximation are self-contained given standard k-decomposability and uniqueness-by-perturbation lemmas.

full rationale

The derivation of Theorem 1.1 proceeds by explicit construction of FT(st) trees (Algorithms 1/3) whose nodes store 1- or 2-decomposable primary paths, followed by a recursive query (Algorithms 2/4/5) whose approximation factor is obtained by induction on the ordered list L of affected vertices (Lemmas 4.7 and 7.1). Each inductive step applies the triangle inequality together with the net-point segment bound |seg(e,P)| ≤ ε|P| (Lemma 2.5, proved from first principles in Appendix A) and the classical fact that a shortest path after k failures is k-decomposable (Lemma 2.2, cited from ABK+02). The uniqueness assumption (Section 2) is the standard infinitesimal weight perturbation already used in the cited literature (BK09, HS01, GS18, DR22); it is not a self-referential uniqueness theorem of the present authors. Space is obtained by sampling a √n-sized landmark set and storing shortest-path trees, a technique independent of the approximation claim. No parameter is fitted to data and later re-used as a “prediction,” no load-bearing uniqueness result is imported solely from overlapping authors, and no known empirical pattern is merely renamed. The single minor self-citation ([GS18]) supplies only a weaker single-fault baseline and is not required for the dual-fault analysis. Consequently the central claim does not reduce to its own inputs by construction.

Axiom & Free-Parameter Ledger

1 free parameters · 4 axioms · 2 invented entities

The central claim rests on three classical facts (unique shortest paths after perturbation, k-decomposability after k failures, net-point segment-length bound) plus the standard sampling lemma for long paths; ε is the only free accuracy parameter. No new physical entities are postulated; the FT tree and detour children are algorithmic constructions.

free parameters (1)
  • ε
    User-chosen accuracy parameter that appears in the (1+O(ε)) guarantee and controls the number of net-points and detour children (log_{1+ε} nW). Not fitted to data; free design choice.
axioms (4)
  • domain assumption After an infinitesimal distinct weight perturbation every pair of vertices has a unique shortest path even after any set of edge failures (Section 2, citing PP13).
    Used throughout to guarantee that replacement paths are exactly k-decomposable and that the “closest-to-x” detour is well-defined.
  • standard math After k edge failures every new shortest path is k-decomposable (Lemma 2.2, citing ABK+02).
    Justifies storing only 1- or 2-decomposable primary paths at every node of FT(st).
  • standard math A segment containing an edge e on a path P satisfies |seg(e,P)| ≤ ε min{|P[s,u]|,|P[u,t]|} or is the singleton {e} (Lemma 2.5, citing CCFK17).
    Supplies the eta=ε (or eta=ε(1+ε)) factor used in every application of the general approximation lemma.
  • standard math A random sample L of size Õ(√n) hits every path of length ≥√n with high probability; shortest-path trees from L can be stored in Õ(n√n) space.
    Standard sampling argument used to represent long primary paths in O(1) space per node.
invented entities (2)
  • FT(st) three-level tree with segment children and 1-/2-decomposable detour children no independent evidence
    purpose: Compactly encode candidate replacement paths so that a constant-depth recursion can approximate the dual-fault distance.
    Purely algorithmic construction; no independent physical existence claimed.
  • QUERYDETOUR procedure that handles a second fault lying on a previously chosen detour no independent evidence
    purpose: Close the case analysis when the 1-decomposable detour itself contains the second failure.
    Algorithmic subroutine invented for the dual-fault setting; correctness proved by case analysis inside the paper.

pith-pipeline@v1.1.0-grok45 · 33990 in / 3292 out tokens · 27800 ms · 2026-07-12T05:32:21.979615+00:00 · methodology

0 comments
read the original abstract

We are given an undirected weighted graph $G$ with $n$ vertices and $m$ edges, edge weights in $[1, W]$, and a designated source vertex $s$. We design a single source dual fault tolerant distance oracle for $G$. Given a destination vertex $t$ and a set $F$ of at most two faulty edges, the oracle returns a $(1 + O(\epsilon))$-approximation of the weight of the shortest path from the source $s$ to $t$ avoiding $F$. Our oracle uses $\tilde{O}(n\sqrt{n})$ space and has $\tilde{O}(1)$ query time. Prior to our result, single source single fault tolerant oracles were known to return a $(1+\epsilon)$ approximation of the weight of the shortest path using $\tilde{O}(n)$ space and $O(1)$ query time. However, extending these approaches to multiple faults remained an open problem. Indeed, all $(1+\epsilon)$-approximate distance oracles that handle multiple faults require $\Omega(n^2)$ space. We break this bound by presenting the first dual fault tolerant distance oracle with $o(n^2)$ space.

Figures

Figures reproduced from arXiv: 2607.02999 by Koustav Das, Manoj Gupta.

Figure 1
Figure 1. Figure 1: Netpoints originating from the vertex s are shown in red and form the set L. Netpoints originating from the vertex t are shown in blue and form the set R. A vertex may belong to both L and R. The union of these sets constitutes the set of netpoints. Definition 2.4 (Segment). A segment of a path P is any subpath between two consecutive netpoints on P. For an edge e ∈ P, define seg(e, P) as the unique segmen… view at source ↗
Figure 2
Figure 2. Figure 2: Let P be a path from s to t. Let R be a path (shown in pink) avoiding e that lies on the segment xy. Detour of R is R[w, t]. The detour of R starts on the segment xy above e at w and joins the path at z below the segment xy. Definition 2.7. (Detour of a path R) Let R be a path from s to t that avoids an edge e on the original shortest path st. Let w be the last vertex of R that also lies on PREFIX(st, e), … view at source ↗
Figure 3
Figure 3. Figure 3: Part 1: st ⋄ e avoids segment xy. Part 2: st ⋄ e intersects xy below e on segment xy. Part 3: st ⋄ e intersects xy above e on segment xy. Lemma 4.6. Let R be a node in FT(st). Let e = (u, v) be the last faulty edge on the path PR with u closer to s. Let S = seg(e, PR ). Suppose the fault tolerant path R = st ⋄ F intersects S at a vertex z below e. Assume there exists a path Q from z to t that also avoids F… view at source ↗
Figure 4
Figure 4. Figure 4: Proving |zv| ⩽ |tz|. We now show that |zv| ⩽ |tz| (See [PITH_FULL_IMAGE:figures/full_fig_p012_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: |su ⋄ e| ⩽ |st ⋄ e| For the second part of the lemma, using triangle inequality, we know that , |su ⋄ F| ⩽ |sw ⋄ F| + |wu ⋄ F| (2) = |sw ⋄ F| + |wu| (since wu has no fault) (3) Since R intersects xy above e at a vertex w |st ⋄ F| ⩽ |sw ⋄ F| + |wt ⋄ F| (4) As wu is a subpath of wt, |wu| < |wt| ⩽ |wt ⋄ F| (5) From (3) and (5), we get |su ⋄ F| < |sw ⋄ F| + |wt ⋄ F| (6) ⩽ |st ⋄ F|. (7) Using the above lemma, v… view at source ↗
Figure 6
Figure 6. Figure 6: Illustration of different types of detours in path [PITH_FULL_IMAGE:figures/full_fig_p015_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Different ways st ⋄ F can intersect. Let v ∈ V(F) ∪ {t}. We want to find how many times QUERYDUAL(v, ·) will be called. We claim that this can be called at most 4 times. Indeed as explained during the discussion of QUERYDUAL, every time QUERYDUAL(v, ·) is called, we are moving to a segment child of FT(sv). Since the height of FT(sv) is 3, the total number of calls to QUERYDUAL with v as a first parameter c… view at source ↗
Figure 8
Figure 8. Figure 8: st ⋄ F does not intersect pq and the detour starts from xy containing e ′ , the path PXj avoids the entire fault set F. Let r be the vertex in {u, u ′ } that is closest to z (See [PITH_FULL_IMAGE:figures/full_fig_p022_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: st ⋄ F intersects pq above e ′ . This case mirrors the above case. While processing Ri, we constructed a 2-decomposable detour child in Yj of Ri such that the detour of PYj starts as high as possible on pq and whose detour length is at most (1 + ε) times that of the detour of R. The remaining steps are similar to (β1) above – the only difference is that w lies on the segment pq instead of segment xy. Hence… view at source ↗
Figure 10
Figure 10. Figure 10: st ⋄ F intersects pq below e ′ . Let e ′ = (u ′ , v ′ ), where v ′ lies closer to t on PRi . In Line 5 of QUERYDETOUR, we set PATH = |PRi [v ′ , t]| + QUERYDUAL(v ′ , ROOT(FT(sv′ ))) = |PRi [v ′ , z]| + |PRi [z, t]| + QUERYDUAL(v ′ , ROOT(FT(sv′ ))) 23 [PITH_FULL_IMAGE:figures/full_fig_p023_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: st ⋄ F when intersect st ⋄ e on the segment pq containing the edge e ′ Proof. Assume for contradiction that R intersects st ⋄ e at z above the second faulty edge e ′ (see Figure 11a) . Then there are two different shortest paths from s to z avoiding F = {e, e ′ }. One is (st ⋄ e)[s, z] and the other is R[s, z], a contradiction since all shortest paths, even avoiding two edges, are unique. Now, if R inters… view at source ↗
Figure 12
Figure 12. Figure 12: e2 lies on the (st ⋄ e)[v ′ , t] Assume for contradiction that the edge e2 lies on the subpath (st ⋄ e)[v ′ , t] (See [PITH_FULL_IMAGE:figures/full_fig_p026_12.png] view at source ↗
Figure 13
Figure 13. Figure 13: 3 edge fault case path in the figure). If e1 were absent, the path from z to s along st would suffice to reach s. However, the presence of e1 introduces significant complications. By our assumption, |sz ⋄ F| ≫ |st ⋄ F|, so this detour offers no advantage. In fact, in this configuration, it is crucial to find a detour that starts between e2 and e3 on the st path. However, identifying such a detour is far f… view at source ↗
Figure 14
Figure 14. Figure 14: Illustration of subpath decomposition of [PITH_FULL_IMAGE:figures/full_fig_p030_14.png] view at source ↗
Figure 15
Figure 15. Figure 15: The segment endpoints x and y lie in different decomposed paths Qi and Qj, respectively. Since there are log1+ϵ n segments, there can be at most 2 log1+ϵ n segment endpoints. Hence, the total time required for this operation is O(log1+ϵ n). C Proof of the Section 7 We analyze the case when R avoids the entire segment xy. In Line 4 of QUERYDUAL(t, ROOT(FT(st))), we move to the segment child X , which corre… view at source ↗

discussion (0)

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