pith. machine review for the scientific record. sign in

arxiv: 2605.02114 · v1 · submitted 2026-05-04 · 💻 cs.DS

Recognition: 2 theorem links

Undirected Replacement Paths: Dual Fault Reduces to Single Source

Jakob Nogler , Virginia Vassilevska Williams
Authors on Pith no claims yet

Pith reviewed 2026-05-08 18:42 UTC · model grok-4.3

classification 💻 cs.DS
keywords replacement pathsfault toleranceundirected graphsalgorithmic reductionsfine-grained complexitysingle source distances
0
0 comments X

The pith

A tight reduction shows that undirected 2-fault replacement paths are no harder than single-source replacement paths.

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

The paper establishes a reduction from the undirected two-fault replacement paths problem to the single-source replacement paths problem. This shows that handling two simultaneous edge failures is not computationally harder than handling one failure from a single source, contrary to previous intuition. The reduction is weight-preserving, which means the fastest algorithms known for SSRP can now be used directly for 2-FRP in undirected graphs. It also provides matching conditional lower bounds based on fine-grained complexity assumptions.

Core claim

The central discovery is a tight, weight-preserving reduction from undirected 2-FRP to undirected SSRP. This allows the best-known algorithms for SSRP to be applied to 2-FRP, yielding improved runtimes such as Õ(M n^ω) for bounded integer weights, n³/2^Ω(√log n) for polynomial weights, and Õ(m√n + n²) combinatorial time for unweighted graphs. The paper complements this with tight lower bounds under fine-grained hypotheses.

What carries the argument

The key machinery is a weight-preserving graph transformation that reduces queries about distances under any two edge failures to queries about single-edge-failure distances from a single source in a modified graph.

If this is right

  • The reduction yields the first Õ(M n^ω) time algorithm for 2-FRP with weights in [1,M]
  • It gives n³/2^Ω(√log n) time for 2-FRP with poly(n) weights
  • Combinatorial Õ(m n^{1/2} + n²) time for unweighted 2-FRP
  • Matching lower bounds under fine-grained hypotheses

Where Pith is reading between the lines

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

  • The prior intuition that 2-FRP is harder than SSRP does not hold in undirected graphs
  • The equivalence allows transferring all future improvements in SSRP algorithms directly to 2-FRP

Load-bearing premise

The graph modification in the reduction must accurately encode every possible pair of edge failures as some single edge failure in the new graph without changing the relevant distances.

What would settle it

A specific undirected graph and pair of edges where the distance under two failures computed directly differs from the distance obtained by applying the SSRP algorithm to the reduced instance.

Figures

Figures reproduced from arXiv: 2605.02114 by Jakob Nogler, Virginia Vassilevska Williams.

Figure 1
Figure 1. Figure 1: Some visualizations of the introduced notation when computing 𝑑G\𝑒,𝑒′(𝑠, 𝑡). 2 Overview In this section, we give a brief overview of the reduction. The overview is composed of two parts: one for the case where both failed edges 𝑒 and 𝑒 ′ are on the shortest path 𝜋G(𝑠, 𝑡) (i.e., Main Theorem 1) and one for the case when only 𝑒 is on 𝜋G(𝑠, 𝑡) (i.e., Main Theorem 2). The notation should be clear from the cont… view at source ↗
Figure 2
Figure 2. Figure 2: This figure shows how T is split into T1 and T2. A simple showcase. As a (not too involved) example of how these observations are applied, we showcase the computations performed to determine 𝑑G\𝑒,𝑒′(𝑠, 𝑡) for all 𝑒, 𝑒′ such that 𝑒 ∈ 𝜋G(𝑠, 𝑡), 𝑒 ′ ∉ 𝑇G(𝑠), and 𝑒 ′ ∉ 𝐸G(𝑇G(𝑠, 𝑒), 𝑉(G) \ 𝑇G(𝑠, 𝑒)). Consider such arbitrary 𝑒, 𝑒′ . Note that since 𝑒 ′ ∉ 𝑇G(𝑠), we have 𝑇G\𝑒 ′(𝑠) = 𝑇G(𝑠). In particular, 𝑇G\𝑒 ′(𝑠,… view at source ↗
Figure 3
Figure 3. Figure 3: Visual representation of the cases in Equation (6). The red dashed line corresponds to the domain of 𝑥, and the blue dashed line corresponds to the domain of 𝑒. Correctness: We begin by proving that 𝑤1 and 𝑤2 are indeed valid short-cut weights. To this end, note that for every 𝑥 ∈ G1 we have 𝑑G˜ \𝜋G(𝑠,𝑐) (𝑠, 𝑥) ≥ 𝑑G˜ (𝑠, 𝑥) ≥ 𝑑G(𝑠, 𝑥) = 𝑑G1 (𝑠, 𝑥). This, combined with 𝑤𝑠(𝑥) ≥ 𝑑G(𝑠, 𝑥) = 𝑑G1 (𝑠, 𝑥) yields t… view at source ↗
Figure 4
Figure 4. Figure 4: The figure illustrates how the graph A is constructed. The construction of B is symmetric w.r.t. {𝑎, 𝑏}. Finally, for every 𝑥 ∈ 𝑋 and 𝑒 ∈ 𝐹 we compute the desired values as: 𝑑G˜ \𝑒 (𝑠, 𝑥) =    𝑑G˜ (𝑠, 𝑥) 𝑥 ∉ 𝐻 (7a) 𝑑G˜ (𝑠, 𝑥) 𝑥 ∈ 𝐻 and 𝑒 ∉ H, (7b) 𝑑H˜ \𝑒 (𝑠, 𝑥) 𝑥 ∈ 𝐻 and 𝑒 ∈ H. (7c) Correctness: First, we need to prove that we can indeed apply Theorem 4.3. To this end, we need to show that 𝑤 ′ 𝑠 a… view at source ↗
Figure 5
Figure 5. Figure 5: The first figure illustrates an example of G. Edge 𝑒 is highlighted in red, while all other edges in 𝑇G(𝑠) are shown in bold black. The set of nodes 𝐴 is indicated by the red shaded area. The subsequent three figures (from left to right) display in green all edges 𝑒 ′ corresponding to cases (i), (ii), and (iii). For the edge 𝑒 ′ ∉ 𝜋G(𝑠, 𝑡), we distinguish three possible placements w.r.t. 𝑠: (i) 𝑒 ′ ∈ 𝐸G(𝐴,… view at source ↗
Figure 6
Figure 6. Figure 6: An example of the construction of G for the Sparse ( √ 𝑛, 𝑛, 𝑛)-Triangle Detection Problem. Lemma 6.1. Given an instance of Sparse ( √ 𝑛, 𝑛, 𝑛)-Triangle Detection, we can construct an undirected, unweighted graph G with 𝒪(𝑛) vertices and 𝒪(𝑚) edges in time 𝒪(𝑛 + 𝑚) such that the triangle problem can be solved by reading 𝒪(√ 𝑛) outputs of a 2-FRP computation on G. Furthermore, if the objective is the minimu… view at source ↗
read the original abstract

Given a graph and two fixed vertices $s$ and $t$, the Replacement Path Problem (RP) is to compute for every edge $e$, the distance between $s$ and $t$ when $e$ is removed. There are two natural extensions to RP: (1) Single Source Replacement Paths (SSRP): Given a graph $G$ and a source node $s$, compute for every vertex $v$ and every edge $e$ the $s$-$v$ distance in $G \setminus \{e\}$. That is, we do not fix the target anymore. (2) $2$-Fault Replacement Paths (2-FRP): Given a graph $G$ and two nodes $s$ and $t$, compute for every pair of edges $e, e'$ the $s$-$t$ distance in $G \setminus \{e, e'\}$. That is, we consider two failures instead of one. Previously, there was no known reduction between SSRP and 2-FRP. It seemed plausible that 2-FRP would be computationally harder because there are no settings where 2-FRP admits a faster algorithm than SSRP. In directed unweighted graphs there is a provable gap in complexity, and in undirected graphs many of the known 2-FRP algorithms in a variety of settings are much slower than those for SSRP in the same setting. The main contribution of this paper is a tight reduction from undirected $2$-FRP to undirected SSRP, showing that contrary to prior intuition, 2-FRP is not harder than SSRP. As our reduction is weight-preserving, we obtain the first algorithms for $2$-FRP that match the best-known runtimes for SSRP: (1) $\tilde{O}(M n^{\omega})$ for weights in $[1, M]$ [GVW19], improving upon $O(Mn^{2.87})$ [CZ24]; (2) $n^3/2^{\Omega(\sqrt{\log n})}$ for weights in $[1, \text{poly}(n)]$ [GVW19], improving over the previous $n^3\text{polylog}(n)$ running time [VWWX22]; (3) $\tilde{O}(mn^{1/2}+n^{2})$ combinatorial time for unweighted graphs [CC19], and more generally for rational weights in $[1, 2]$ [CM20], improving upon $\tilde{O}(n^{3-1/18})$ [CZ24]. We complement these upper bounds with tight lower bounds under fine-grained hypotheses.

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

0 major / 2 minor

Summary. The paper claims a tight, weight-preserving reduction from undirected 2-Fault Replacement Paths (2-FRP) to undirected Single-Source Replacement Paths (SSRP). This allows direct transfer of the best-known SSRP algorithms to 2-FRP, yielding improved runtimes such as Õ(M n^ω) for integer weights in [1,M], n^3/2^Ω(√log n) for polynomial weights, and Õ(m n^{1/2} + n^2) combinatorial time for unweighted/rational-[1,2] graphs. The result is complemented by matching conditional lower bounds under fine-grained hypotheses, showing 2-FRP is not harder than SSRP in undirected graphs.

Significance. If the reduction holds, the result is significant: it resolves an open question on the relative complexity of these problems by establishing equivalence (rather than a strict gap) in the undirected setting, contrary to intuition from directed graphs and prior 2-FRP algorithms. The weight-preserving property ensures exact distances are recovered without distortion, enabling the first matching upper bounds. Credit is due for the constructive mapping and the complementary lower bounds that establish tightness.

minor comments (2)
  1. Abstract: the listed SSRP runtimes (e.g., [GVW19], [CC19]) are cited without a one-sentence reminder of the precise SSRP problem variant they solve; adding this would help readers immediately see the transfer.
  2. The lower-bound section would benefit from an explicit statement of the fine-grained hypothesis used (e.g., APSP or 3SUM) and a short table comparing the new 2-FRP lower bounds to the SSRP ones they match.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the paper and for recommending acceptance. We appreciate the recognition of the significance of establishing equivalence between undirected 2-FRP and SSRP via a weight-preserving reduction.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper's central contribution is an explicit, weight-preserving constructive reduction that maps any undirected 2-FRP instance to one or more undirected SSRP instances via a direct graph transformation. This equivalence is defined by the construction itself and does not rely on fitted parameters, self-referential definitions of distances, or load-bearing self-citations; the prior SSRP algorithms cited (e.g., GVW19) are external results whose runtimes are transferred only after the reduction is established. Lower bounds are complemented under standard fine-grained hypotheses and do not form part of the derivation chain for the upper bounds. The derivation is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper's central claim rests on a novel reduction construction in the standard model of undirected graphs with edge weights. No free parameters are introduced, and the axioms are the standard ones for shortest path problems.

axioms (1)
  • standard math Undirected graphs with non-negative edge weights admit shortest path computations via standard algorithms.
    The paper builds on existing shortest path and replacement path techniques in this model.

pith-pipeline@v0.9.0 · 5798 in / 1428 out tokens · 73417 ms · 2026-05-08T18:42:14.748703+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

23 extracted references · 21 canonical work pages

  1. [1]

    The time complexity of fully sparse matrix multiplication

    ABFK24 Amir Abboud, Karl Bringmann, Nick Fischer, and Marvin K¨unnemann. The time complexity of fully sparse matrix multiplication. InProceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, V A, USA, January 7-10, 2024, pages 4670–4703. SIAM,

    2024

  2. [2]

    doi: 10.1145/383962.383980

    Association for Computing Machinery. doi: 10.1145/383962.383980. 4 BCFS21 Davide Bil`o, Sarel Cohen, Tobias Friedrich, and Martin Schirneck. Near-optimal deterministic single-source distance sensitivity oracles. In Petra Mutzel, Rasmus Pagh, and Grzegorz Herman, editors,29th Annual European Symposium on Algorithms, ESA 2021, Lisbon, Portugal (Virtual Conf...

    work page doi:10.1145/383962.383980 2021

  3. [3]

    2 BCG+ 18 Davide Bil `o, Keerti Choudhary, Luciano Gual `a, Stefano Leucci, Merav Parter, and Guido Proietti

    URL: https://doi.org/10.4230/LIPIcs.ESA.2021.18, doi:10.4230/LIPICS.ESA.2021.18. 2 BCG+ 18 Davide Bil `o, Keerti Choudhary, Luciano Gual `a, Stefano Leucci, Merav Parter, and Guido Proietti. Efficient oracles and routing schemes for replacement paths. In Rolf Niedermeier and Brigitte Vall ´ee, editors,35th Symposium on Theoretical Aspects of Computer Scie...

    work page doi:10.4230/lipics.esa.2021.18 2021

  4. [4]

    2 BCHR20 Surender Baswana, Keerti Choudhary, Moazzam Hussain, and Liam Roditty

    URL: https: //doi.org/10.4230/LIPIcs.STACS.2018.13,doi:10.4230/LIPICS.STACS.2018.13. 2 BCHR20 Surender Baswana, Keerti Choudhary, Moazzam Hussain, and Liam Roditty. Approximate single-source fault tolerant shortest path.ACM Trans. Algorithms, 16(4):44:1–44:22, 2020.doi:10.1145/3397532. 2 Ber10 Aaron Bernstein. A nearly optimal algorithm for approximating ...

    work page doi:10.4230/lipics.stacs.2018.13 2018

  5. [5]

    1 BF00 Michael A

    doi: 10.1137/1.9781611973075.61. 1 BF00 Michael A. Bender and Martin Farach-Colton. The LCA problem revisited. In Gaston H. Gonnet, Daniel Panario, and Alfredo Viola, editors,LATIN 2000: Theoretical Informatics, 4th Latin American Symposium, Punta del Este, Uruguay, April 10-14, 2000, Proceedings, volume 1776 ofLecture Notes in Computer Science, pages 88–...

    work page doi:10.1137/1.9781611973075.61 2000

  6. [6]

    LATIN 2000: Theoretical Informatics

    doi:10.1007/10719839\_9. 8 BFC04 Michael A. Bender and Mart´ın Farach-Colton. The level ancestor problem simplified.Theor. Comput. Sci., 321(1):5–12, June 2004.doi:10.1016/j.tcs.2003.05.002. 8 BG04 Amit Bhosle and Teofilo Gonzalez. Replacement paths for pairs of shortest path edges in directed graphs. InProc. 16th IASTED International Conference on Parall...

    work page doi:10.1007/10719839 2004

  7. [7]

    Approximate shortest paths avoiding a failed vertex: Near optimal data structures for undirected unweighted graphs.Algorithmica, 66(1):18–50, 2013

    URL: https://doi.org/10.1007/ s00453-012-9621-y,doi:10.1007/S00453-012-9621-Y. 2 BLM12 Surender Baswana, Utkarsh Lath, and Anuradha S. Mehta. Single source distance oracle for planar digraphs avoiding a failed node or link. InProceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’12, page 223–232, USA,

    work page doi:10.1007/s00453-012-9621-y

  8. [8]

    Finding level-ancestors in trees

    doi:10.1016/S0022-0000(05)80002-9. 8 BW84 Thomas H. Byers and Michael S. Waterman. Determining all optimal and near-optimal solutions when solving shortest path problems by dynamic programming.Operations Research, 32(6):1381–1384,

    work page doi:10.1016/s0022-0000(05)80002-9

  9. [9]

    1 BW25 Greg Bodwin and Lily Wang

    URL: http: //www.jstor.org/stable/170956. 1 BW25 Greg Bodwin and Lily Wang. Improved shortest path restoration lemmas for multiple edge failures: Trade-offs between fault-tolerance and subpaths. In Yossi Azar and Debmalya Panigrahi, editors,Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025, New Orleans, LA, USA, January 1...

    work page doi:10.1137/1.9781611978322.179 2025

  10. [10]

    1, 2, 3 CDWX25 Shucheng Chi, Ran Duan, Benyu Wang, and Tianle Xie

    doi:10.1137/1.9781611975482.126. 1, 2, 3 CDWX25 Shucheng Chi, Ran Duan, Benyu Wang, and Tianle Xie. Undirected 3-fault replacement path in nearly cubic time. In Keren Censor-Hillel, Fabrizio Grandoni, Jo¨el Ouaknine, and Gabriele Puppis, editors,52nd International Colloquium on Automata, Languages, and Programming, ICALP 2025, July 8-11, 2025, Aarhus, Den...

    work page doi:10.1137/1.9781611975482.126 2025

  11. [12]

    Arya and D

    URL: https://doi.org/10.4230/LIPIcs. ICALP.2020.81,doi:10.4230/LIPICS.ICALP.2020.81. 2, 3, 6 CZ24a Shiri Chechik and Tianyi Zhang. Faster algorithms for dual-failure replacement paths. In Karl Bringmann, Martin Grohe, Gabriele Puppis, and Ola Svensson, editors,51st International Colloquium on Automata, Languages, and Programming, ICALP 2024, Tallinn, Esto...

    work page doi:10.4230/lipics 2020

  12. [13]

    2, 3 CZ24b Shiri Chechik and Tianyi Zhang

    URL: https://doi.org/10.4230/LIPIcs.ICALP.2024.41, doi:10.4230/LIPICS.ICALP.2024.41. 2, 3 CZ24b Shiri Chechik and Tianyi Zhang. Nearly optimal approximate dual-failure replacement paths. In David P . Woodruff, editor,Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, V A, USA, January 7-10, 2024, pages 2568–2596. SIA...

    work page doi:10.4230/lipics.icalp.2024.41 2024

  13. [14]

    8 GL09 Zvi Gotthilf and Moshe Lewenstein

    URL: https: //doi.org/10.1007/BFb0028247,doi:10.1007/BFB0028247. 8 GL09 Zvi Gotthilf and Moshe Lewenstein. Improved algorithms for the k simple shortest paths and the replacement paths problems.Inf. Process. Lett., 109(7):352–355, March 2009.doi:10.1016/j.ipl.2008.12.015. 1 GPVX21 Yuzhou Gu, Adam Polak, Virginia Vassilevska Williams, and Yinzhan Xu. Faste...

    work page doi:10.1007/bfb0028247 2009

  14. [15]

    Faster Monotone Min-Plus Product, Range Mode, and Single Source Replacement Paths , booktitle =

    URL:https://doi.org/10.4230/LIPIcs.ICALP.2021.75,doi:10.4230/LIPICS.ICALP.2021.75. 2 GV12 Fabrizio Grandoni and Virginia Vassilevska Williams. Improved distance sensitivity oracles via fast single-source replacement paths. In53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pages 748–757...

    work page doi:10.4230/lipics.icalp.2021.75 2021

  15. [16]

    2 HLNV17 Monika Henzinger, Andrea Lincoln, Stefan Neumann, and Virginia Vassilevska Williams

    URL: https://doi.org/10.4230/LIPIcs.ESA.2024.65, doi:10.4230/LIPICS.ESA.2024.65. 2 HLNV17 Monika Henzinger, Andrea Lincoln, Stefan Neumann, and Virginia Vassilevska Williams. Conditional Hardness for Sensitivity Problems. In Christos H. Papadimitriou, editor,8th Innovations in Theoretical Computer Science Conference (ITCS 2017), volume 67 ofLeibniz Intern...

    work page doi:10.4230/lipics.esa.2024.65 2024

  16. [17]

    Conditional Hardness for Sensitivity Problems

    Schloss Dagstuhl – Leibniz-Zentrum f¨ur Informatik. URL: https://drops.dagstuhl. de/entities/document/10.4230/LIPIcs.ITCS.2017.26,doi:10.4230/LIPIcs.ITCS.2017.26. 2, 4 HS01 J. Hershberger and S. Suri. Vickrey prices and shortest paths: What is an edge worth? InProceedings of the 42nd IEEE Symposium on Foundations of Computer Science, FOCS ’01, page 252, USA,

    work page doi:10.4230/lipics.itcs.2017.26 2017

  17. [18]

    1 HSB07 John Hershberger, Subhash Suri, and Amit M

    IEEE Computer Society. 1 HSB07 John Hershberger, Subhash Suri, and Amit M. Bhosle. On the difficulty of some shortest path problems.ACM Trans. Algorithms, 3(1):5:1–5:15, 2007.doi:10.1145/1219944.1219951. 1 KKP93 David R. Karger, Daphne Koller, and Steven J. Phillips. Finding the hidden path: Time bounds for all-pairs shortest paths.SIAM J. Comput., 22(6):...

    work page doi:10.1145/1219944.1219951 2007

  18. [19]

    1 MMG89 K

    URL: http://www.jstor.org/ stable/2629357. 1 MMG89 K. Malik, A. K. Mittal, and S. K. Gupta. The k most vital arcs in the shortest path problem.Oper. Res. Lett., 8(4):223–227, August 1989.doi:10.1016/0167-6377(89)90065-5. 1, 19 NPW01 Enrico Nardelli, Guido Proietti, and Peter Widmayer. A faster computation of the most vital edge of a shortest path. Inf. Pr...

    work page doi:10.1016/0167-6377(89)90065-5 1989

  19. [20]

    URL: https://www.sciencedirect.com/science/article/pii/S089982569990790X, doi:10.1006/game.1999

    work page doi:10.1006/game.1999 1999

  20. [21]

    1 28 Undirected Replacement Paths: Dual Fault Reduces to Single Source RV12 Liam Roditty and Virginia Vassilevska Williams

    Society for Industrial and Applied Mathematics. 1 28 Undirected Replacement Paths: Dual Fault Reduces to Single Source RV12 Liam Roditty and Virginia Vassilevska Williams. Subquadratic time approximation algorithms for the girth. In Yuval Rabani, editor,Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Jap...

    2012

  21. [22]

    Ryan , year =

    1 VW18 Virginia Vassilevska Williams and R. Ryan Williams. Subcubic equivalences between path, matrix, and triangle problems.J. ACM, 65(5):27:1–27:38, 2018.doi:10.1145/3186893. 1, 2 VWX22 Virginia Vassilevska Williams, Eyob Woldeghebriel, and Yinzhan Xu. Algorithms and lower bounds for replacement paths under multiple edge failure. In2022 IEEE 63rd Annual...

    work page doi:10.1145/3186893 2018

  22. [23]

    Ryan Williams , title =

    doi:10.1137/15M1024524. 2, 3 WY13 Oren Weimann and Raphael Yuster. Replacement paths and distance sensitivity oracles via fast matrix multiplication. ACM Trans. Algorithms, 9(2):14:1–14:13, 2013.doi:10.1145/2438645.2438646. 1 Yen71 Jin Y. Yen. Finding the k shortest loopless paths in a network.Management Science, 17(11):712–716,

    work page doi:10.1137/15m1024524 2013

  23. [24]

    URL: http://www.jstor.org/stable/2629312. 1

    work page arXiv