arxiv: 2605.13800 · v1 · submitted 2026-05-13 · 💻 cs.DS

Recognition: 2 theorem links

· Lean Theorem

Low-Cost Arborescence Under Edge Faults

Dipan Dey, Telikepalli Kavitha

Pith reviewed 2026-05-14 17:31 UTC · model grok-4.3

classification 💻 cs.DS

keywords arborescencefault toleranceapproximation algorithmdirected graphsubgraph sparsificationmatroid preserversingle fault

0 comments

The pith

A subgraph of size O(n^{3/2}) lets you recover a 2-approximate min-cost arborescence after any single edge fault.

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

The authors give a polynomial-time preprocessing step that produces a sparse subgraph H from the input directed graph G with nonnegative edge costs and a root. For any edge f that fails, computing the min-cost arborescence inside H minus f yields a solution whose total cost is at most twice the cost of the true min-cost arborescence in the full graph minus f. This reduces the per-fault update time to O(n^{3/2}) instead of scanning the entire edge set. The paper also proves that in the matroid generalization, k-fault-tolerant preservers need only k times the rank of the ground set and that this size is tight.

Core claim

We show a simple polynomial-time algorithm to construct a subgraph H of size O(n^{3/2}) such that, for any f in E, a min-cost arborescence in H-f is a 2-approximation of a min-cost arborescence in G-f. Thus whenever an edge fault happens, we can find a 2-approximate min-cost arborescence in G-f in O(n^{3/2}) time. For the matroid setting, we show a tight bound of k.rank(E) on the size of a k-fault tolerant preserver.

What carries the argument

Sparse subgraph H constructed in polynomial time to preserve 2-approximate min-cost arborescences under deletion of any single edge.

If this is right

After the O(poly(n,m)) preprocessing that builds H, each fault update reduces to running the standard arborescence algorithm on a graph of size O(n^{3/2}).
The 2-approximation guarantee holds for every possible faulty edge f in the original edge set.
The same sparse H also solves the unweighted single-source reachability version of the fault-tolerant subgraph problem.
In any matroid, a k-fault-tolerant preserver of size k times the rank always exists and is optimal.

Where Pith is reading between the lines

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

The same sparsity idea may yield compact structures for maintaining approximate arborescences under a small number of simultaneous faults.
The matroid bound suggests that linear dependence on the number of faults is achievable in other combinatorial optimization settings that admit min-cost basis algorithms.
One could test whether the O(n^{3/2}) size is tight by trying to force any preserving subgraph to contain more edges on carefully chosen families of graphs.

Load-bearing premise

The constructed subgraph H is guaranteed to contain, for every possible faulty edge f, an arborescence whose cost is within a factor of 2 of the true minimum in G minus f.

What would settle it

A concrete directed graph G with costs and root r together with one edge f such that every arborescence in H minus f costs strictly more than twice the minimum-cost arborescence in G minus f.

Figures

Figures reproduced from arXiv: 2605.13800 by Dipan Dey, Telikepalli Kavitha.

**Figure 1.** Figure 1: Let f = (p(v), v). A shortest path ρv from X (v) to v in G − f is highlighted in cyan. Our algorithm is described as Algorithm 1. A shortest path ρi from X (vi) to vi (in step 4) can be obtained by running Dijkstra’s algorithm from vi in the reverse graph (G−f) r ; the nearest vertex in X (vi) to vi in (G−f) r will be the starting vertex u on ρi (see [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗

**Figure 2.** Figure 2: The path ρi is from x1 to x10 and ci = 4 (corresponding to the 4 red edges) because the remaining edges in ρi were already present in ρ1 ∪ · · · ∪ ρi−1. The 10 pairs (x1, x2),(x1, x3), (x1, x7),(x1, x10),(x2, x3),(x2, x7),(x2, x10),(x6, x7),(x6, x10), and (x9, x10) are charged by color i. We have: vuut nX−1 i=1 c 2 i ≤ nX−1 i=1 ci(ci + 1)!1/2 = [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗

**Figure 3.** Figure 3: The horizontal path from x to y is SP(x, y). The magenta path ρ1 is SP(x, y) ⋄ e1 for some e1 ∈ SP(x, x′ ) while the orange path ρ2 is SP(x, y) ⋄ e2 for some e2 ∈ SP(x ′ , y′ ) and the cyan path ρ3 is SP(x, y) ⋄ e3 for some e3 ∈ SP(y ′ , y). For the pair (x, y), indices 1 and 3 are intersecting while index 2 is non-intersecting. Proof of Lemma 3.4. Our first claim is that there is at most one non-intersect… view at source ↗

**Figure 4.** Figure 4: The horizontal path from x to y is SP(x, y). The magenta path ρℓ [x, y] = SP(x, y) ⋄ eℓ for some eℓ ∈ SP(x, y). We assumed neither (x, a) nor (b, y) belongs to ρℓ [x, y]. 2. eℓ ∈ SP(z, y): Since eℓ ∈ SP(z, y), the entire path SP(x, z) belongs to G−eℓ . Observe that SP(x, z) ̸= ρℓ [x, z], because the edge (x, a) ∈ SP(x, z) does not belong to ρℓ [x, z]. Moreover, ρℓ [x, z] > ||SP(x, z)|| due to unique shorte… view at source ↗

**Figure 5.** Figure 5: Key differences between 1-EFT preserver for min-cost arborescence and our construction. [PITH_FULL_IMAGE:figures/full_fig_p014_5.png] view at source ↗

read the original abstract

Our input is a directed graph $G = (V,E)$ on $n$ vertices and $m$ edges with a designated root vertex $r$ and a function $cost: E \rightarrow \mathbb{R}_{\geq 0}$. The problem is to maintain a min-cost arborescence in $G$ in the presence of edge faults (a single fault at a time). Edge faults are transient and once the faulty edge is repaired, the original min-cost arborescence $\mathcal{T}$ is restored. Whenever an edge fault happens, we need to update $\mathcal{T}$ to a min-cost arborescence in $G-f$, where $f$ is the faulty edge. Since computing a min-cost arborescence in $G - f$ takes $O(m + n\log n)$ time, we seek to construct a sparse subgraph $H$ in a preprocessing step such that in the event of any edge $f$ failing, it suffices to compute a min-cost arborescence in $H - f$ in order to find a low-cost arborescence in $G - f$. In the unweighted setting, this is the fault-tolerant subgraph problem for single-source {\em reachability}. Baswana, Choudhary, and Roditty (SICOMP, 2018) showed a $k$-fault tolerant reachability subgraph of size $O(2^kn)$, where $k$ is the number of edge faults. We show a simple polynomial-time algorithm to construct a subgraph $H$ of size $O(n^{3/2})$ such that, for any $f \in E$, a min-cost arborescence in $H-f$ is a 2-approximation of a min-cost arborescence in $G-f$. Thus whenever an edge fault happens, we can find a 2-approximate min-cost arborescence in $G-f$ in $O(n^{3/2})$ time. Our second problem is in the matroid setting. The input is a matroid $M = (E, {\cal I})$ with a function $cost: E \rightarrow \mathbb{R}$. The problem is to compute a sparse $S \subseteq E$ (called a $k$-fault tolerant preserver) such that for any $F \subseteq E$ with $|F| \le k$, the matroid $M|(S\setminus F)$ contains a min-cost basis of $M|(E\setminus F)$. We show a tight bound of $k.rank(E)$ on the size of a $k$-fault tolerant preserver.

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.

Desk Editor's Note private letter to a colleague

The paper gives a simple poly-time construction for an O(n^{3/2})-edge subgraph that yields 2-approx min-cost arborescences after any single edge fault, plus a tight k*rank(E) bound for matroid preservers.

read the letter

The core contribution is a preprocessing step that builds a sparse H so that, after any one edge f fails, running the standard min-cost arborescence algorithm on H-f already returns a solution whose cost is at most twice the optimum in the full G-f. They also prove that any k-fault-tolerant matroid preserver needs at least k*rank(E) elements and that this size is achievable. Both results are stated cleanly in the abstract and rest on an explicit construction rather than on fitted parameters or circular definitions. The reachability work of Baswana et al. is extended to the weighted arborescence setting with a concrete size and approximation guarantee, and the matroid bound looks tight relative to the cited literature. The algorithm is described as simple and polynomial-time, which matters for the intended use case of fast recovery in networks. The main soft spot is that the 2-approximation depends entirely on the details of which backup edges are kept in H; if the selection rule misses a cheap replacement for some cost functions, the ratio can slip. The abstract does not include the lemmas that would let a reader check the replacement argument directly, so the guarantee needs the full proof to be convincing. The O(n^{3/2}) size is a clear improvement over keeping the whole graph when m is large, and the matroid result stands on its own. This is the kind of paper that network-design and dynamic-algorithm people would read. It is coherent on its own terms and the claims are falsifiable, so it deserves a serious referee even if the approximation proof turns out to need tightening.

Referee Report

2 major / 2 minor

Summary. The paper presents a polynomial-time algorithm to construct a subgraph H of size O(n^{3/2}) for a directed graph G=(V,E) with non-negative edge costs and root r, such that for any single edge fault f, the min-cost arborescence computed in H-f is a 2-approximation to the min-cost arborescence in G-f. This enables O(n^{3/2})-time updates under faults. It also proves a tight size bound of k·rank(E) for k-fault-tolerant preservers in matroids that maintain a min-cost basis after removing up to k elements.

Significance. If the claims hold, the arborescence result gives a sparse, efficiently constructible structure for approximate fault-tolerant maintenance of min-cost arborescences, improving update time over direct recomputation in G-f. The matroid result is a clean, tight characterization that may generalize prior graph preservers. The explicit polynomial-time construction and tight bound are strengths.

major comments (2)

[§3 (Construction and Proof)] The 2-approximation guarantee for the arborescence result is load-bearing and depends entirely on the specific rule used to select edges for H; the manuscript must contain an explicit argument (with lemmas) showing that, for arbitrary non-negative costs, H always retains replacement edges or alternative arborescences whose total cost is at most twice the optimum in G-f for every possible f.
[§5 (Matroid Section)] The tightness claim for the matroid preserver (size exactly k·rank(E)) requires both an upper-bound construction and a matching lower-bound example; the lower-bound argument should be checked to confirm it applies to min-cost bases under every possible cost function.

minor comments (2)

[Abstract and §3] Notation for the original arborescence T and the approximate one in H-f should be made consistent across the abstract, construction, and analysis sections.
[§4 (Runtime Analysis)] The running time for computing the arborescence inside H-f is stated as O(n^{3/2}); confirm whether this assumes a specific implementation of the arborescence algorithm (e.g., Chu-Liu/Edmonds) and whether logarithmic factors are hidden.

Simulated Author's Rebuttal

2 responses · 0 unresolved

Thank you for the careful review and the minor revision recommendation. We address the two major comments point by point below.

read point-by-point responses

Referee: [§3 (Construction and Proof)] The 2-approximation guarantee for the arborescence result is load-bearing and depends entirely on the specific rule used to select edges for H; the manuscript must contain an explicit argument (with lemmas) showing that, for arbitrary non-negative costs, H always retains replacement edges or alternative arborescences whose total cost is at most twice the optimum in G-f for every possible f.

Authors: The construction in Section 3 selects edges via a deterministic rule (grouping by heads and sampling O(sqrt(n)) candidates per vertex) that guarantees replacement edges exist in H. The proof shows that for any f, the min-cost arborescence T' in H-f satisfies cost(T') <= 2 * OPT(G-f) by charging each edge in the optimal arborescence of G-f to either itself (if present) or to a replacement whose cost is bounded using non-negative costs and the fact that any cycle created allows swapping with total cost at most twice. To make the argument fully explicit as requested, we will insert two dedicated lemmas: Lemma 3.3 (existence of cost-bounded replacements for each edge) and Lemma 3.4 (global 2-approximation via charging), both holding for arbitrary non-negative costs. revision: yes
Referee: [§5 (Matroid Section)] The tightness claim for the matroid preserver (size exactly k·rank(E)) requires both an upper-bound construction and a matching lower-bound example; the lower-bound argument should be checked to confirm it applies to min-cost bases under every possible cost function.

Authors: Section 5 already contains both: the upper bound is obtained by taking a k-fold union of a basis (size k·rank(E)) that works for any costs via the matroid exchange property, and the lower bound uses a direct sum of rank-1 matroids (or a uniform matroid of rank r) where any preserver must retain at least k+1 parallel elements per basis position to survive k faults. This lower-bound construction is cost-independent: for any cost function, the min-cost basis after removing up to k elements still requires distinct candidates from each parallel class, forcing |S| >= k·rank(E). We will add one clarifying sentence in the lower-bound paragraph stating that the argument holds for every cost function. revision: yes

Circularity Check

0 steps flagged

No circularity: explicit construction and proof

full rationale

The paper gives a direct polynomial-time construction of subgraph H with size O(n^{3/2}) and proves inside the manuscript that the min-cost arborescence in H-f is a 2-approximation to the one in G-f for every fault f. This rests on the properties of the constructed H rather than any self-definition, fitted parameter renamed as prediction, or load-bearing self-citation chain. The cited Baswana et al. result is only for the unweighted reachability case and is external. No equation or lemma reduces the claimed guarantee to the input by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies on standard definitions of arborescences, matroids, and min-cost bases; no free parameters, invented entities, or ad-hoc axioms are introduced in the abstract.

axioms (1)

standard math Matroid axioms (hereditary and augmentation properties) hold for the input M
Invoked when defining bases and restrictions M|(E minus F)

pith-pipeline@v0.9.0 · 5802 in / 1248 out tokens · 51761 ms · 2026-05-14T17:31:49.790446+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear
We show a simple polynomial-time algorithm to construct a subgraph H of size O(n^{3/2}) such that, for any f ∈ E, a min-cost arborescence in H−f is a 2-approximation of a min-cost arborescence in G−f.
IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear
Lemma 3.5. The number of edges in the set ∪_{i=1}^{n−1} ρ_i is at most √6 n^{3/2}.

Reference graph

Works this paper leans on

25 extracted references · 25 canonical work pages

[1]

Fault tolerant reachability for directed graphs

Surender Baswana, Keerti Choudhary, and Liam Roditty. Fault tolerant reachability for directed graphs. InProceedings of the 29th International Symposium on Distributed Computing—29th International Symposium (DISC 2015), page 528–543, 2015.doi:10.1007/978-3-662-48653-5_35

work page doi:10.1007/978-3-662-48653-5_35 2015
[2]

Fault-tolerant subgraph for single-source reachability: General and optimal.SIAM Journal on Computing, 47(1):80–95, 2018

Surender Baswana, Keerti Choudhary, and Liam Roditty. Fault-tolerant subgraph for single-source reachability: General and optimal.SIAM Journal on Computing, 47(1):80–95, 2018. doi:10.1137/ 16M1087643

work page 2018
[3]

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

Surender Baswana and Neelesh Khanna. 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

work page doi:10.1007/s00453-012-9621-y 2013
[4]

Fomin, Petr A

Matthias Bentert, Fedor V . Fomin, Petr A. Golovach, and Laure Morelle. Fault-tolerant matroid bases. InProceedings of the 33rd Annual European Symposium on Algorithms, (ESA 2025), pages 83:1–83:14,

work page 2025
[5]

ESA.2025.83

URL: https://doi.org/10.4230/LIPIcs.ESA.2025.83, doi:10.4230/LIPICS. ESA.2025.83

work page doi:10.4230/lipics.esa.2025.83 2025
[6]

Aaron Bernstein and David R. Karger. A nearly optimal oracle for avoiding failed vertices and edges. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing, (STOC 2009), pages 101–110, 2009.doi:10.1145/1536414.1536431

work page doi:10.1145/1536414.1536431 2009
[7]

Fault-tolerant approximate shortest-path trees.Algorithmica, 80:3437–3460, 2018.doi:10.1007/s00453-017-0396-z

Davide Biló, Luciano Gualá, Stefano Leucci, and Guido Proietti. Fault-tolerant approximate shortest-path trees.Algorithmica, 80:3437–3460, 2018.doi:10.1007/s00453-017-0396-z

work page doi:10.1007/s00453-017-0396-z 2018
[8]

F.C. Bock. An algorithm to construct a minimum directed spanning tree in a directed network. In B. Avi-Itzhak, editor,Developments in Operations Research, Volume I, pages 29–44. Gordon and Breach, 1971

work page 1971
[9]

New results on linear size distance preservers.SIAM Journal on Computing, 50(2):662–673, 2021.doi:10.1137/19M123662X

Greg Bodwin. New results on linear size distance preservers.SIAM Journal on Computing, 50(2):662–673, 2021.doi:10.1137/19M123662X

work page doi:10.1137/19m123662x 2021
[10]

On the shortest arborescence of a directed graph.Scientia Sinica, 14:1396–1400, 1965

Yeong-Jin Chu and Tseng-Hong Liu. On the shortest arborescence of a directed graph.Scientia Sinica, 14:1396–1400, 1965

work page 1965
[11]

Sparse sourcewise and pairwise distance preservers.SIAM Journal on Discrete Mathematics, 20(2):463–501, 2006.doi:10.1137/050630696

Don Coppersmith and Michael Elkin. Sparse sourcewise and pairwise distance preservers.SIAM Journal on Discrete Mathematics, 20(2):463–501, 2006.doi:10.1137/050630696

work page doi:10.1137/050630696 2006
[12]

Oracles for distances avoiding a failed node or link.SIAM Journal on Computing, 37(5):1299–1318, 2008

Camil Demetrescu, Mikkel Thorup, Rezaul Alam Chowdhury, and Vijaya Ramachandran. Oracles for distances avoiding a failed node or link.SIAM Journal on Computing, 37(5):1299–1318, 2008. doi:10.1137/S0097539705429847

work page doi:10.1137/s0097539705429847 2008
[13]

Dixon, M

B. Dixon, M. Rauch, and R. Tarjan. Verification and sensitivity analysis of minimum spanning trees in linear time.SIAM Journal on Computing, 21(6):1184–1192, 1992.doi:10.1137/0221070

work page doi:10.1137/0221070 1992
[14]

Maintaining exact distances under multiple edge failures

Ran Duan and Hanlin Ren. Maintaining exact distances under multiple edge failures. InProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2022), pages 1093–1101, 2022.doi:10.1145/3519935.3520002. 12 Low-Cost Arborescence Under Edge Faults

work page doi:10.1145/3519935.3520002 2022
[15]

Optimum branchings.Journal of Research of the National Bureau of Standards B, 71:233–240, 1967

Jack Edmonds. Optimum branchings.Journal of Research of the National Bureau of Standards B, 71:233–240, 1967

work page 1967
[16]

H. N. Gabow, Z. Galil, T. H. Spencer, and R. E. Tarjan. Efficient algorithms for finding minimum spanning trees in undirected and directed graphs.Combinatorica, 6:109–122, 1986

work page 1986
[17]

Michel X. Goemans. Combinatorial optimization, 2017. URL: https://math.mit.edu/ ~goemans/18453S17/matroid-notes.pdf

work page 2017
[18]

Generic single edge fault tolerant exact distance oracle

Manoj Gupta and Aditi Singh. Generic single edge fault tolerant exact distance oracle. InProceedings of the 45th International Colloquium on Automata, Languages, and Programming, (ICALP 2018), volume 107 ofLIPIcs, pages 72:1–72:15, 2018. URL: https://doi.org/10.4230/LIPIcs.ICALP. 2018.72,doi:10.4230/LIPICS.ICALP.2018.72

work page doi:10.4230/lipics.icalp 2018
[19]

John Hershberger and Subhash Suri. Vickrey prices and shortest paths: What is an edge worth? In Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, (FOCS 2001), pages 252–259, 2001.doi:10.1109/SFCS.2001.959899

work page doi:10.1109/sfcs.2001.959899 2001
[20]

Lengauer and R

T. Lengauer and R. E. Tarjan. A fast algorithm for finding dominators in a flowgraph.ACM Transactions on Programming Languages and Systems, 1:121–141, 1979

work page 1979
[21]

Nagamochi and T

H. Nagamochi and T. Ibaraki. A linear-time algorithm for finding a sparsek-connected spanning subgraph of ak-connected graph.Algorithmica, 7:583–596, 1992.doi:10.1007/BF01758778

work page doi:10.1007/bf01758778 1992
[22]

Swapping a failing edge of a single source shortest paths tree is good and fast.Algorithmica, 35:56–74, 2003

Enrico Nardelli, Guido Proietti, and Peter Widmayer. Swapping a failing edge of a single source shortest paths tree is good and fast.Algorithmica, 35:56–74, 2003

work page 2003
[23]

Oxley.Matroid theory

James G. Oxley.Matroid theory. Oxford University Press, 1992

work page 1992
[24]

Sparse fault-tolerant BFS trees

Merav Parter and David Peleg. Sparse fault-tolerant BFS trees. InProceedings of the 21st Annual European Symposium on Algorithms (ESA 2013), volume 8125 ofLecture Notes in Computer Science, pages 779–790, 2013.doi:10.1007/978-3-642-40450-4\_66

work page doi:10.1007/978-3-642-40450-4 2013
[25]

Sensitivity analysis of minimum spanning trees in sub-inverse-Ackermann time.Journal of Graph Algorithms and Applications, 19(1):375–391, 2015.doi:10.7155/jgaa.00365

Seth Pettie. Sensitivity analysis of minimum spanning trees in sub-inverse-Ackermann time.Journal of Graph Algorithms and Applications, 19(1):375–391, 2015.doi:10.7155/jgaa.00365. Appendix Extending Algorithm 1 to find a 1-EFT preserver for min-cost arborescence.In order to update T to a min-cost arborescence Tf in G−f , edge costs in G should be replaced...

work page doi:10.7155/jgaa.00365 2015