{"id":"dc7fb206-0b66-4eb5-a1dd-147490003689","arxiv_id":"2411.18312","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Undirected 3-fault replacement paths are computed in O~(n^3) time, nearly matching the O(n^3) output size.","lead":"A new algorithm computes replacement distances after any three edge failures in undirected weighted graphs in nearly cubic time, matching the output size. It also shows the two-fault version is conditionally hard, making the cubic algorithms essentially optimal.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 7.11's interval-shrinking proof is unsupported: F_i∩A can have more than two intervals, so the O~(n) bound per (d1,d3) pair for the all-three-on-st case is not established.","rationale":"The most load-bearing step is not the uniqueness assumption (which can be addressed by standard symbolic perturbation, though the paper should state this), but Lemma 7.11. That lemma is the only place where the all-three-on-st case—the hardest of the three main cases—is shown to run in O~(n) per (d1,d3) pair. The proof's central claim that F_i∩(E(i-1)_1∪E(i-1)_2) has at most two intervals rests on an unproven assertion that some gap edge is not in F_i. Shortest snake paths can cover the gap, yielding three intervals; the algorithm then cannot maintain its invariant, and the 5/8 shrinking factor is unsupported. This is not a matter of disagreeing with consensus; it is an internal gap in the proof of the main theorem. The reader flagged Lemma 7.11 as 'asserted rather than fully derived,' so there is partial agreement, but the chosen weakest_assumption (determinism) is not the primary risk. A small brute-force search can settle whether the claim is actually false; if it is, the time bound may need a different argument. The paper's incremental DSO and offline-dynamic reduction are valuable and appear reusable, but the 3FRP result is conditional on fixing this proof.","tokens_in":38175,"tokens_out":25299,"duration_ms":198241,"concrete_test":"Run a brute-force enumeration of small undirected graphs (st path of 8–16 edges, detour edges with random or symbolic weights) and simulate Lemma 7.11 exactly: at each stage compute the true shortest snake path (by Dijkstra over snake-type candidates) and record F_i∩(E(i-1)_1∪E(i-1)_2). If any iteration yields more than two disjoint intervals, the lemma's time analysis is refuted. A single such instance settles the concern.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"In Lemma 7.11 (Section 7.2), the algorithm maintains E(i)_1 ∪ E(i)_2 = D ∩ (π1∩...∩πi) and claims this set has at most two intervals, because \"there is at least an edge between E(i-1)_1 and E(i-1)_2 that is not in F\" (where F = π_i ∩ D). This premise is unjustified: E(i-1)_1 and E(i-1)_2 are defined from F_{i-1}, but π_i is a new shortest snake path that can use edges in the gap between them, so F may cover the entire gap. For instance, with D=[0,100], stage 1 could yield E1_1=[0,10] and E1_2=[20,30] (gap (10,20)); stage 2 cuts E1_1 at e3=5, and π3 could have F=[0,4]∪[8,22], giving F∩A = [0,4]∪[8,10]∪[20,22] — three intervals, all avoiding the failed edges e1=50, e2=80, e3=5. Then the algorithm's two-interval bookkeeping loses the third interval, and the invariant that every d2 is eventually avoided by some πk can fail. The shrinking bound S(i+1)≤5/8 S(i) depends critically on the at-most-two-intervals claim. Without a correct proof of this step, Theorem 7.1, and hence Theorem 1.1, is not established.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper claims a deterministic O~(n^3)-time algorithm for undirected 3FRP in real-weighted graphs, together with extensions to fFRP for all f >= 3 and to 2-fault single-source replacement paths, plus an APSP-hardness result for undirected 2FRP. The main technical contribution is an incremental 1-failure distance sensitivity oracle with O~(n^2) worst-case update time, which is then converted into an offline fully dynamic DSO via a proposed binary range tree reduction. The algorithm splits the 3FRP query into cases according to how many failed edges lie on the original s-t shortest path, using the incremental DSO, a binary partition of the shortest path, and a range-tree oracle for snake paths. The hardness reduction for 2FRP is self-contained and reduces APSP to 2FRP by attaching zero-weight paths and weighted matchings.","tokens_in":38487,"tokens_out":14249,"duration_ms":136382,"significance":"If the main theorem is correct, it closes the undirected 3FRP gap and gives almost optimal O~(n^f) algorithms for all f >= 3, since the output size is Theta(n^f). The incremental DSO with O~(n^2) update time is a potentially reusable primitive, and the offline dynamic DSO reduction, if made fully rigorous, would be a useful tool beyond this paper. The 2FRP hardness reduction is clean and convincing. The paper is ambitious and contains several genuinely useful constructions and reductions. However, a number of load-bearing points are not sufficiently supported as written, so the central claim cannot currently be regarded as established.","major_comments":[{"comment":"The paper states that all algorithms are deterministic, but the unique shortest path assumption is justified only by adding small random variables to the edge weights ([10]). This is a genuine mismatch: the divergence/convergence arguments, Theorem 2.1, Theorem 2.2, and the weak-point arguments in Section 4 all rely on uniqueness of shortest paths in every subgraph. If the tie-breaking is randomized, the theorem should state a randomized bound; if determinism is claimed, a deterministic symbolic tie-breaking scheme must be specified and proved to preserve the distances and the structural lemmas. As written, the deterministic guarantee of Theorem 1.1 is not supported by the stated assumptions.","section":"Section 2.1, Theorem 1.1"},{"comment":"The interval-shrinking proof is not sufficient. In Stage i the proof asserts that F cap (E(i-1)_1 union E(i-1)_2) consists of at most two intervals because \"there is at least an edge between E(i-1)_1 and E(i-1)_2 that is not in F\". This premise is not proved: e_i is the middle edge of E(i-1)_1 and lies inside one of the two current components, not necessarily between them, and the proof does not establish an invariant that the two components are separated by some edge that every subsequent pi_j avoids. If that separating edge is not identified, a single interval of F could intersect both E(i-1)_1 and E(i-1)_2 while another interval of F contributes a third piece, breaking the two-interval bookkeeping. The bound S(i+1) <= 5/8 S(i) depends critically on the two-interval claim, and hence the O(log n) stage bound for each (d1,d3) pair, and with it Theorem 7.1, is not established. This step needs either a rigorous invariant or a different shrinking argument.","section":"Section 7.2, Lemma 7.11"},{"comment":"The proof of the offline dynamic DSO construction does not justify the claimed O~(n^3) total time. In the binary range tree, moving from a parent node to a child adds all edges that are present throughout the child interval but not throughout the parent interval; across the whole tree the total number of such edge insertions can be Omega(m log T) = Omega(n^2 log n), and each incremental DSO update costs Omega~(n^2), giving Omega~(n^4) rather than O~(n^3). The proof of Theorem 2.5 should either be replaced by a correct invocation of the Peng-Rubinstein reduction (Theorem 2.4) with explicit per-update accounting, or the statement should be proved with a different argument. Since Sections 5, 6 and 9 explicitly rely on Theorem 2.5, this is a load-bearing issue.","section":"Section 2.5, Theorem 2.5"}],"minor_comments":[{"comment":"In the displayed lower bound for the fourth value, both terms in the first minimum are written as pi_{Hi,1-...}; the intended expression from Lemma 6.11 is a minimum over Hi,0-d1-d3 and Hi,1-d2-d3, so the subscripts should be corrected.","section":"Section 6.4, proof of Theorem 6.13"},{"comment":"The case where both d1 and d2 lie on the shortest path tree but the queried vertex t is not in the subtree of the first failed edge is not explicitly discussed; the argument should state that such a failed edge is not on pi(s,t) and hence does not affect the distance.","section":"Section 9, correctness proof"},{"comment":"The update algorithm states that shortest path trees are reconstructed after inserting e, but it does not specify how this is done within the O~(n^2) update bound; the intended method via checking min{old distances} for every pair should be stated explicitly so the time bound is verifiable.","section":"Section 4.3"},{"comment":"The notation d^+_1 appears in the proof of Lemma 6.2 where d^+_2 is intended; this typo makes the displayed path construction slightly confusing.","section":"Section 6.1"}],"recommendation":"major_revision","confidential_remarks":"The paper addresses a significant open problem and contains several interesting ideas, but the deterministic claim, the Theorem 2.5 reduction proof, and especially Lemma 7.11 need substantial correction before the main result can be trusted. The 2FRP hardness result appears solid and could be published separately even if the algorithmic sections need more work."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper has a solid incremental DSO and a clean APSP-hardness proof for undirected 2FRP, but the main claim — 3FRP in O~(n^3) — rests on a gap in Lemma 7.11 that I don't think is fixable by tweaking constants.\n\nWhat's genuinely new: the incremental DSO in Section 4, with O~(n^2) worst-case update, is a nice piece of work. The case analysis for the update is detailed and mostly plausible, and the reduction to an offline dynamic DSO via Theorem 2.5 is useful. The 2FRP hardness reduction in Section 8 is straightforward and correct. The 2-fault SSRP application is also a nice bonus.\n\nThe problem is Section 7.2. Lemma 7.11 drives the all-three-failures-on-st case. Its shrinking argument assumes that when you take the new snake path π_i and intersect it with D, the intersection with the two tracked intervals E(i-1)_1 and E(i-1)_2 has at most two components. The stated justification is that there is at least one edge in the gap between E(i-1)_1 and E(i-1)_2 not in F = π_i ∩ D. That is not something the algorithm controls. A later π_i can run through that gap. Concretely, if E1 = [0,10] and E2 = [20,30], and π_3 intersects D as [0,4] ∪ [8,22], then F ∩ (E1∪E2) = [0,4] ∪ [8,10] ∪ [20,22] — three pieces, not two. The algorithm then keeps only the two largest, so E(i)_1 ∪ E(i)_2 no longer equals D ∩ (π_1 ∩ ... ∩ π_i), and the invariant that every d2 is eventually avoided breaks. The 5/8 shrink bound collapses. Without that, Theorem 7.1 does not go through, and neither does Theorem 1.1.\n\nThere is also the determinism issue: Section 2.1 breaks ties with random weights while the paper insists the algorithms are deterministic. That is probably patchable with symbolic perturbation, but as written it's an inconsistency.\n\nThe paper deserves a serious referee. The DSO work and the lower bound are worth publishing separately even if the 3FRP proof needs major repair. But the current version should not be accepted as is. If I were the editor, I'd send it out and let the referees chase the gap, with the expectation of a major revision. I wouldn't cite the 3FRP result until Lemma 7.11 is fixed.","headline":"Good incremental DSO and a clean lower bound, but the main 3FRP theorem rests on an unsupported interval-shrinking claim in Lemma 7.11.","tokens_in":39025,"tokens_out":4803,"would_cite":false,"duration_ms":42209,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q25","05C85","68W40"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims that undirected 3-fault replacement paths can be computed deterministically in near-cubic time, nearly matching the cubic output size.","keywords":["f-fault replacement path","distance sensitivity oracle","incremental DSO","offline dynamic DSO","undirected weighted graphs","APSP-hardness","single-source replacement path","near-cubic time"],"falsifier":"Run the described algorithm on all undirected weighted graphs up to seven vertices, including graphs with deliberately tied shortest paths, and compare every reported $\\pi_{G-\\{d_1,d_2,d_3\\}}(s,t)$ against brute-force deletion of all edge triples; any mismatch in such a small graph would show the uniqueness assumption cannot simply be dropped. Separately, timing the worst-case edge insertion cases from Section 4.3.1 would test the claimed $\\tilde{O}(n^2)$ update bound.","tokens_in":37974,"feed_emoji":"🛣️","tokens_out":5079,"duration_ms":42251,"temperature":0.7,"pith_summary":"This paper claims that the 3-fault replacement path problem in undirected, real-weighted graphs can be solved deterministically in $\\tilde{O}(n^3)$ time for $n$ vertices. The output of the problem has $\\Theta(n^3)$ distances, so the running time would be optimal up to polylogarithmic factors. If the main theorem is correct, then for every fixed $f \\ge 3$ edge failures, the $f$-fault version in undirected graphs can be solved in $\\tilde{O}(n^f)$ time, again nearly matching output size. The paper also gives a 2-fault single-source replacement path algorithm in $\\tilde{O}(n^3)$ time and proves a conditional lower bound showing that undirected 2FRP has no truly subcubic algorithm under the APSP-hardness conjecture.","feed_headline":"3-fault replacement paths now run in nearly cubic time","feed_subtitle":"That would make f-fault distances near-optimal for every f, with a reusable incremental oracle.","key_machinery":"The load-bearing mechanism is an incremental distance sensitivity oracle that, after each edge insertion, maintains for every pair $u,v$ the shortest path tree, an LCA structure, and stored detours $\\omega_{G-(u\\oplus i)(v\\ominus j)}(u,v)$ for intervals whose offsets from $u$ and $v$ are powers of two. Detours are kept in proper form, meaning a shortest path, one edge, and another shortest path, so they can be transformed and compared in $\\tilde{O}(1)$ time. Inserting an edge $e$ updates all affected detours through a six-case analysis of where the new shortest path diverges and converges relative to the queried interval. The second ingredient is a binary range tree on $st$: two failed edges on $st$ are separated at some level of this tree, and the replacement distance is the minimum of four DSO queries on graphs that keep only the left or right half of the interval. Three failed edges on $st$ are handled by range-to-range oracles together with a staged search in which the candidate edge set $D \\cap (\\pi_1 \\cap \\cdots \\cap \\pi_i)$ shrinks by a constant factor at each stage.","core_discovery":"The central claim, stated as Theorem 1.1, is that every replacement distance $|\\pi_{G-\\{d_1,d_2,d_3\\}}(s,t)|$ for all triples of failed edges can be produced in $\\tilde{O}(n^3)$ time. The argument splits by how many of the failed edges lie on the original shortest path $st$: one failed edge is handled through an incremental 1-failure distance sensitivity oracle, two failed edges reduce to a constant number of DSO queries over a binary partition of $st$, and three failed edges are answered by range-tree oracles plus a shrinking-interval search that keeps the amortized cost per triple constant. The paper further shows that, assuming the APSP conjecture, no truly subcubic algorithm for undirected 2FRP exists, and that 2-fault single-source replacement paths can be solved in $\\tilde{O}(n^3)$ time.","pith_inferences":["A natural next target is whether the same incremental-DSO template extends to directed graphs, but the paper's structural lemmas use undirectedness heavily, so directed 3FRP would require new arguments.","If the deterministic tie-breaking gap is closed, the framework would give deterministic offline dynamic distance sensitivity oracles for other distance queries under edge insertions and deletions with total near-cubic work.","The 2FRP hardness gadget encodes all-pairs distances using zero-weight paths and matchings, which suggests that any improvement below cubic for two faults in undirected graphs would refute the APSP conjecture rather than merely improve on this algorithm."],"forward_implications":["For every fixed $f \\ge 3$, $f$-fault replacement paths in undirected graphs can be solved in $\\tilde{O}(n^f)$ time, which is within polylogarithmic factors of the $\\Theta(n^f)$ output size.","The 2-fault single-source replacement path problem in undirected graphs can be solved in $\\tilde{O}(n^3)$ time, and the extension gives $\\tilde{O}(n^{f+1})$ time for all $f \\ge 2$.","Assuming the APSP conjecture, undirected 2FRP cannot be solved in truly subcubic time, so the cubic barrier for two edge faults is conditionally optimal.","The incremental DSO and the offline-dynamic conversion are reusable tools: a 1-failure DSO with $\\tilde{O}(n^3)$ preprocessing, $\\tilde{O}(n^2)$ worst-case update time, $\\tilde{O}(n^2)$ space, and $\\tilde{O}(1)$ query time."],"supporting_citations":[{"why":"Supplies the directed 2FRP algorithm and the reduction from fFRP to (f-1)FRP that the paper extends to undirected graphs.","marker":"[30]"},{"why":"Supplies the static 1-failure DSO used to initialize the incremental oracle and to answer replacement-path queries.","marker":"[5]"},{"why":"Supplies the 1-replacement-path structure theorem used to bound the number of second failures.","marker":"[11]"},{"why":"Provides the reduction from an incremental worst-case DSO to an offline fully dynamic DSO used throughout the construction.","marker":"[26]"},{"why":"Gives the near-linear time 1FRP algorithm in undirected graphs that serves as the baseline the paper builds on.","marker":"[25]"},{"why":"Supplies the binary partition and dual-failure DSO ideas adapted to separate two failed edges on the original shortest path.","marker":"[17]"},{"why":"Establishes the APSP-hardness equivalence used for the conditional lower bound for undirected 2FRP.","marker":"[31]"},{"why":"Provides the path-concatenation structure theorem that lets each replacement path be represented as a shortest path, one edge, and a shortest path.","marker":"[7]"},{"why":"Gives the bound that the union of all 1-fault replacement paths has O(n) edges, which controls the number of possible second failures.","marker":"[6]"},{"why":"Supplies the LCA data structure used to check whether two paths intersect in O(1) time during detour transformation.","marker":"[3]"}],"fun_headline_variants":["Nearly cubic time for 3-fault replacement paths","3-fault distances now near-optimal for every f","Almost optimal 3-fault replacement paths","Near-cubic 3FRP: optimal for all failure sets","3-fault replacement paths in nearly cubic time"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The paper assumes every subgraph has unique shortest paths, and all structural lemmas and update-case arguments rely on that uniqueness; without a deterministic tie-breaking scheme, the stated deterministic bound is not fully supported.","fun_headline_variants_meta":{"raw":{"variants":["Nearly cubic time for 3-fault replacement paths","3-fault distances now near-optimal for every f","Almost optimal 3-fault replacement paths","Near-cubic 3FRP: optimal for all failure sets","3-fault replacement paths in nearly cubic time"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000597,"raw_usage":{"total_tokens":2933,"prompt_tokens":1228,"completion_tokens":1705,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":844,"completion_tokens_details":{"reasoning_tokens":1628}},"tokens_in":844,"tokens_out":1705,"duration_ms":12588,"temperature":1.0,"reasoning_tokens":1628,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T11:20:53.058412+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the described algorithm on all undirected weighted graphs up to seven vertices, including graphs with deliberately tied shortest paths, and compare every reported $\\pi_{G-\\{d_1,d_2,d_3\\}}(s,t)$ against brute-force deletion of all edge triples; any mismatch in such a small graph would show the uniqueness assumption cannot simply be dropped. Separately, timing the worst-case edge insertion cases from Section 4.3.1 would test the claimed $\\tilde{O}(n^2)$ update bound.","supporting_citations":[{"cited_title":"Williams, E","cited_arxiv_id":null,"evidence_quote":"Supplies the directed 2FRP algorithm and the reduction from fFRP to (f-1)FRP that the paper extends to undirected graphs."},{"cited_title":"A nearly optimal oracl e for avoiding failed vertices and edges","cited_arxiv_id":null,"evidence_quote":"Supplies the static 1-failure DSO used to initialize the incremental oracle and to answer replacement-path queries."},{"cited_title":"Oracles for distances avoiding a failed node or link","cited_arxiv_id":null,"evidence_quote":"Supplies the 1-replacement-path structure theorem used to bound the number of second failures."},{"cited_title":"Fully-dynamic-to- incremental reductions with known deletion order (e.g","cited_arxiv_id":null,"evidence_quote":"Provides the reduction from an incremental worst-case DSO to an offline fully dynamic DSO used throughout the construction."},{"cited_title":"A faster computation of the most vital edge of a shortest path","cited_arxiv_id":null,"evidence_quote":"Gives the near-linear time 1FRP algorithm in undirected graphs that serves as the baseline the paper builds on."},{"cited_title":"Dual-failure distance and con nectivity oracles","cited_arxiv_id":null,"evidence_quote":"Supplies the binary partition and dual-failure DSO ideas adapted to separate two failed edges on the original shortest path."},{"cited_title":"Ryan Williams","cited_arxiv_id":null,"evidence_quote":"Establishes the APSP-hardness equivalence used for the conditional lower bound for undirected 2FRP."},{"cited_title":"Restoration by path concatenation: fast recovery of MPLS paths","cited_arxiv_id":null,"evidence_quote":"Provides the path-concatenation structure theorem that lets each replacement path be represented as a shortest path, one edge, and a shortest path."},{"cited_title":"Preserving Distances in Very Faulty Graphs","cited_arxiv_id":"1703.10293","evidence_quote":"Gives the bound that the union of all 1-fault replacement paths has O(n) edges, which controls the number of possible second failures."},{"cited_title":"Bender and Martín Farach-Colton","cited_arxiv_id":null,"evidence_quote":"Supplies the LCA data structure used to check whether two paths intersect in O(1) time during detour transformation."}],"review_version":1}