A Simple and Efficient Algorithm for Finding Minimum Spanning Tree Replacement Edges

David A. Bader; Paul Burkhardt

REVIEW 3 major objections 4 minor 21 references

A Simple and Efficient Algorithm for Finding Minimum Spanning Tree Replacement Edges

T0 review · 3 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

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

Pith's one-line read Given an MST and its sorted non-tree edges, this paper claims to compute all minimum-cost replacement edges in $O(m+n)$ time and $O(m+n)$ space.

desk verdict Clean and plausible O(m+n) algorithm for MST replacement edges, but the proof of the linear bound needs real revisions before the claim is rigorous. read the letter →

arxiv 1908.03473 v4 pith:ZWA22RE6 submitted 2019-08-09 cs.DS

David A. Bader , Paul Burkhardt This is my paper · ORCID

classification cs.DS

keywords minimumspanningtreereplacementedgesmostvitaledgelineartimealgorithmdisjointsetunionfundamentalcycledynamicgraphspathcompression

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper establishes that, given a minimum spanning tree (MST) of an undirected weighted graph and its non-tree edges sorted by weight, every minimum-cost replacement edge can be computed in $O(m+n)$ time and $O(m+n)$ space. The previous deterministic bound for this problem was $O(m\alpha(m,n))$. The algorithm roots the MST, labels vertices with depth-first intervals, scans non-tree edges from lightest to heaviest, and walks each fundamental cycle upward while compressing already-solved subpaths with disjoint-set links, so each tree edge is inspected at most once. It also derives the most vital edge in linear time from the replacement table. This matters for network repair: after a single road or link fails, the cheapest reconnection is one table lookup.

What carries the argument

The mechanism is a rooted MST with depth-first-search IN/OUT intervals plus the cycle walker PathLabel. Interval containment tests whether one endpoint is an ancestor of the other and decides which branch of the fundamental cycle to walk, so the least common ancestor is detected without being computed. For each scanned non-tree edge, the walker travels from descendant to ancestor and, whenever a tree edge receives a replacement, it calls a link operation that unites that vertex's disjoint set with its parent's set, compressing the path so later cycles jump over assigned edges. Because the MST is the union tree and is known in advance, the paper invokes a linear-time special case of disjoint set union; that special case is what turns the amortized $O(m)$ find operations into a hard $O(m+n)$ bound.

What would settle it

Count the find and link operations on a worst-case-looking family, such as a path MST with many long, overlapping fundamental cycles; if the total number of operations exceeds $c(m+n)$ for every fixed constant $c$ as $n$ grows, the linear-time claim fails. A simpler check is to compare the implemented algorithm's running time against the previous near-linear algorithm on such inputs and look for superlinear growth.

Watch

Extended reading notes

Core claim

The central claim is that the replacement edge for each MST edge is the lightest non-tree edge whose fundamental cycle contains that edge, and processing non-tree edges in increasing weight lets all replacements be assigned on first encounter. The first time a tree edge is visited in a cycle walk, the non-tree edge driving that cycle is stored as its replacement; the walk moves from descendant to ancestor and uses the DFS interval bounds to stop exactly at the least common ancestor without computing it. According to the Cut Property, the lightest crossing edge in the cut defined by removing a tree edge is precisely the minimum replacement. Path compression through disjoint-set links ensures no tree edge is revisited after its replacement is fixed. The paper proves correctness by induction on the cycle walks and analyzes the find/link count to obtain the linear bound.

Load-bearing premise

The $O(m+n)$ bound rests on the paper's invocation of a known linear-time special case of disjoint set union in which the union tree is fixed in advance; if that special-case bound does not apply to the actual sequence of cycle walks, the same algorithm with ordinary union-find runs in $O(m\alpha(m,n))$.

Editorial extensions

If this is right

After a single tree-edge failure, the minimum reconnection cost is available by one table lookup, making single-failure repair effectively immediate after the preprocessing scan.
When the MST is built by Kruskal's algorithm, the sorted edge list already exists; piping that list into this scan gives all replacement edges in linear time, an asymptotic improvement over the prior deterministic bound.
Because bridge edges have no replacement, the scan can terminate early once $n-1-k$ replacements have been found, where $k$ is the number of bridges.
The most vital edge, the tree edge whose removal raises the MST weight the most, is found in $O(n)$ after the replacement table is built, so the whole pipeline is linear.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The same interval-pruned cycle walk could be adapted to other tree-based sensitivity problems, such as finding the lightest detour edge for each arc of a shortest-path tree, where the first-scan rule may apply by analogy.
The linear-time bound is achieved only with the special-case disjoint-set-union data structure; an implementation using a generic union-find will exhibit the previous $O(m\alpha(m,n))$ behavior, so the practical win depends on that implementation detail.
For graphs with small integer edge weights, radix or bucket sorting makes the entire pipeline linear without relying on Kruskal's sorted output, extending the result to a broader input model.
The replacement table can be viewed as a static sensitivity report for the MST, suggesting a natural next step of using it in dynamic settings where tree-edge deletions arrive one at a time and comparing against incremental maintenance.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the letter

Short version: this is a legitimate attack on a classic problem, with a genuinely simple algorithm and the right kind of external dependency. The linear-time bound is plausible and probably correct, but the proof needs more work than a cosmetic fix.

What is new: processing sorted non-tree edges with DFS in/out intervals to avoid explicit LCA computation, and using Gabow-Tarjan's static union tree DSU to compress already-labeled tree edges. That combination is clean, and the walk-through example is a real help. The paper correctly identifies the prior O(m alpha(m,n)) bound and makes a fair claim of first O(m+n) with sorted edges. No circularity, no fitted parameters.

Soft spots, in proportion: Claim 2 is overstated. Path compression can jump the walk above the LCA, so the traversal does not always stop at the LCA. It stops when the interval test says the current vertex is outside the cycle, which is the right guard, but the claim should say that. Claim 4's find-counting is genuinely sloppy. It says every other find precedes a link, but line 16's find follows a link, and line 13 can be a duplicate of the previous line 16. That said, the conclusion is salvageable: each while-loop iteration either performs a link (O(n) total) or jumps to the representative of a compressed set, and that jump can happen only once per PathLabel call between links. So total iterations are O(n + m), and total finds are O(m). Claim 4 as written does not prove this, but the missing argument is not huge.

The stress-test note worries that the Gabow-Tarjan reduction is unverified because the link sequence is online and weight-dependent. I disagree. The union tree is the MST, known up front, and every link unites a vertex with its parent in that tree. That is exactly the Gabow-Tarjan special case. The paper could state the model more carefully, but this is not a hidden assumption.

Bottom line: the central idea is sound and the gaps are in the proof details, not in the algorithm itself. A serious referee should ask for a rewritten Claim 2 and a fixed Claim 4, not a new approach. The paper deserves peer review and likely publication after revision.

Referee Report

3 major / 4 minor

Summary. The paper presents Algorithm 1, which, given an MST and the non-tree edges sorted by weight, computes for every MST edge the minimum-weight replacement edge. The algorithm roots the MST, computes DFS intervals, and scans non-tree edges in increasing weight order; for each non-tree edge it walks the induced fundamental cycle with the help of disjoint-set path compression, so that tree edges whose replacement has already been found are skipped. The authors claim an O(m+n) time and O(m+n) space bound using the Gabow-Tarjan special-case disjoint-set-union data structure, and they further claim that the most vital edge can then be found in linear time. The paper is short and the algorithmic idea is appealing, but the proof as written has two localized gaps (Claim 2 and Claim 4) and the application of the Gabow-Tarjan theorem is stated too informally for the central complexity claim to be fully checkable.

Significance. If the claimed bound is correct, this is a clean improvement over Tarjan's O(m alpha(m,n)) algorithm for this problem, and it appears to be the first linear-time algorithm under the stated input model (given MST and sorted non-tree edges). The algorithm is genuinely simple and would be easy to implement, and the use of Gabow-Tarjan's linear-time special case of disjoint set union is a natural and appropriate tool. The correctness strategy is largely sound: assigning each tree edge the first non-tree edge whose cycle contains it is justified by the cut property, and the path-compression invariant correctly prevents an edge from being assigned twice. However, the proof of the O(m+n) bound is not complete as written, so the central claim needs revision before the result can be accepted.

major comments (3)

[Section 3.2, Claim 2] Claim 2 states that the traversal 'stops at the LCA.' This is not accurate when path compression jumps to a representative above the LCA. Because an earlier cycle may have compressed the entire path from a vertex to an ancestor above the LCA, a single find(v) can return a representative r strictly above the LCA of the current non-tree edge. The example in Section 3.1 only illustrates a jump exactly to the LCA. The claim should be weakened and made precise: the traversal stops at the LCA or at a representative above it, and in the latter case the loop terminates in the same iteration because the updated k1/k2 value makes the loop condition false; consequently no edge above the LCA is assigned a replacement. This correction is needed because Claim 3 and Theorem 1 rely on the claim that only cycle edges are traversed and assigned.
[Section 3.3, Claim 4] The find-counting proof in Claim 4 is incomplete and slightly misstated. The text says there are 'at most two find operations at the start and end of each of the two PathLabel calls,' but lines 13 and 16 of Algorithm 1 execute in every iteration of the while loop, not only at the start and end. The missing argument is that after the first iteration of any PathLabel call, v is always a set representative (because line 16 sets v to the result of find(v), which is a set label), so every subsequent iteration satisfies find(v)=v and therefore performs a link. Hence each PathLabel call has at most one iteration without a link; with two calls per non-tree edge, the number of non-link iterations is O(m), the number of link iterations is O(n), and the total number of find operations is O(m+n). The current proof does not contain this argument, so the O(m+n) bound of Theorem 2 is not yet supported.
[Section 3.3, Theorem 2] The linear-time bound depends entirely on the Gabow-Tarjan special-case disjoint-set-union theorem [6,7], but the paper never states the precise hypotheses of that theorem. The theorem applies to an online sequence of finds and link operations in which each link(v) links a set root v to parent(v) in a known union tree. The manuscript should state these hypotheses explicitly and then verify that Algorithm 1 satisfies them: the union tree is the rooted MST, and by the test on line 12, link(v) is called only when v is a set root. Without this verification, the central O(m+n) claim is conditional on an external result in a way that the reader cannot check from the manuscript.

minor comments (4)

[Abstract and Section 1] The phrase 'worse-case' should be 'worst-case.'
[Section 3.1] The walk-through refers to MST edges e1,e2,e3,e4,e5,e7,e9, but Figure 3 does not label the edges with these names. Please label the figure or add a table so the example is self-contained.
[Section 2, Related Work] The novelty claim ('first to find all replacement edges in O(m+n) time' under the sorted-edges model) should be re-verified carefully against the literature; the related-work section cites Pettie's sub-inverse-Ackermann algorithm but does not explicitly rule out any prior linear-time algorithm for this specific input model.
[Algorithm 1, line 2] The ancestor test on line 2 uses IN[s] < IN[t] < OUT[s]. The surrounding text correctly explains that this is equivalent to the full interval-containment condition because IN[t] < OUT[t] always holds; a brief remark to this effect would improve readability.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the algorithm's derivation is self-contained apart from standard cut-property and an external Gabow-Tarjan DSU theorem.

full rationale

The paper derives the replacement-edge assignment from the cut property and the ordering of sorted non-tree edges: the first non-tree edge inducing a fundamental cycle containing an MST edge is, by Claim 1 and the Cut Property [3], that edge's minimum replacement. This is a direct application of an external textbook result, not an input defined in terms of the output. The only load-bearing external ingredient for the O(m+n) time bound is the Gabow-Tarjan special-case disjoint set union theorem [6,7], which is a published result by other authors and is explicitly identified as applicable because the union tree is known in advance and equals the MST. No fitted parameter is renamed as a prediction, and no claimed result is equivalent by construction to its assumptions. The skeptical objection that Claim 4's find-counting may not fully establish the Gabow-Tarjan preconditions, or that the linear-time bound is conditional on that theorem, is a correctness or completeness concern, not a circularity concern. Consequently no specific circular step can be exhibited.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The central claim rests on standard graph theory (cut property, DFS intervals) and on the external Gabow-Tarjan DSU theorem. No free parameters or invented entities are introduced.

assumptions (4)

standard math Cut property: for any cut, the lightest edge crossing it belongs to some MST; hence the first non-tree edge in sorted order whose fundamental cycle contains a tree edge is that tree edge's replacement.
Invoked in Section 3 introduction and Claim 1 to justify replacement assignment.
standard math Gabow-Tarjan linear-time disjoint set union special case applies to the sequence of link operations generated by Algorithm 1, where the union tree is the MST.
Relied on in Section 3 and Claim 4 for O(m+n); without it standard union-find gives O(m alpha(m,n)).
standard math DFS interval ancestry: u is an ancestor of v iff IN[u] < IN[v] < OUT[u].
Used in PathLabel to detect ancestor/descendant relationships and to stop traversal at the LCA without computing it.
domain assumption Non-tree edges are provided sorted by weight; sorting them would cost O(m log m) in general.
Stated in the abstract and Section 1 as an input condition; the linear-time claim is conditional on this.

how reviews work

0 comments

Cite this review

Pith. "Pith review of A Simple and Efficient Algorithm for Finding Minimum Spanning Tree Replacement Edges." pith.science (2026). https://pith.science/paper/ZWA22RE6

@misc{pith2026190803473,
  author       = {Pith},
  title        = {Pith review of: A Simple and Efficient Algorithm for Finding Minimum Spanning Tree Replacement Edges},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ZWA22RE6}},
  note         = {Machine review of arXiv:1908.03473}
}

abstract

Given an undirected, weighted graph, the minimum spanning tree (MST) is a tree that connects all of the vertices of the graph with minimum sum of edge weights. In real world applications, network designers often seek to quickly find a replacement edge for each edge in the MST. For example, when a traffic accident closes a road in a transportation network, or a line goes down in a communication network, the replacement edge may reconnect the MST at lowest cost. In the paper, we consider the case of finding the lowest cost replacement edge for each edge of the MST. A previous algorithm by Tarjan takes $O(m \alpha(m, n))$ time and space, where $\alpha(m, n)$ is the inverse Ackermann's function. Given the MST and sorted non-tree edges, our algorithm is the first practical algorithm that runs in $O(m+n)$ time and $O(m+n)$ space to find all replacement edges. Additionally, since the most vital edge is the tree edge whose removal causes the highest cost, our algorithm finds it in linear time.

Figures

Figures reproduced from arXiv: 1908.03473 by the authors.

**Figure 2.** The PathLabel algorithm detects when vertex [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗

**Figure 3.** An example graph on 8 vertices (a, . . . , h) and 13 weighted edges (label/weight in blue). The MST root vertex c and MST edges are highlighted by thicker lines. The MST edges are e1, e2, e3, e4, e5, e7, e9 and say the root of the MST tree is vertex c. In the 6 [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

21 extracted references · 21 canonical work pages

[1]

Cattaneo, P

G. Cattaneo, P. Faruolo, U. Ferraro Petrillo, and G.F. Italiano. Maintaining dynamic minimum spanning trees: An experimental study. Discrete Applied Mathematics, 158(5):404–425, 2010

work page 2010
[2]

Chin and D

F. Chin and D. Houck. Algorithms for updating minimal spanning trees. Journal of Computer and System Sciences , 16(3):333 – 344, 1978

work page 1978
[3]

T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms, 3rd Edition. MIT Press, Inc., Cambridge, MA, 2009

work page 2009
[4]

Das and M.C

B. Das and M.C. Loui. Reconstructing a minimum spanning tree after deletion of any node. Algorithmica, 31(4):530–547, 2001

work page 2001
[5]

Frederickson

G.N. Frederickson. Data structures for on-line updating of minimum spanning trees, with applications. SIAM Journal on Computing , 14(4):781–798, 1985

work page 1985
[6]

Gabow and R.E

H.N. Gabow and R.E. Tarjan. A linear-time algorithm for a special case of disjoint set union. In Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing , STOC ’83, pages 246–251, New York, NY, USA, 1983. ACM

work page 1983
[7]

Gabow and R.E

H.N. Gabow and R.E. Tarjan. A linear-time algorithm for a special case of disjoint set union. Journal of Computer and System Sciences , 30(2):209 – 221, 1985

work page 1985
[8]

Henzinger and V

M. Henzinger and V. King. Maintaining minimum spanning trees in dynamic graphs. In Proc. of the 24th International Colloquium on Automata, Languages and Programming (ICALP) , pages 594–604, 1997. 10

work page 1997

Show all 21 references

[9]

J. Holm, K. de Lichtenberg, and M. Thorup. Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. J. ACM , 48(4):723760, July 2001

2001
[10]

Hsu, R.-H

L.-H. Hsu, R.-H. Jan, Y.-C. Lee, C.-N. Hung, and M.-S. Chern. Finding the most vital edge with respect to minimum spanning tree in weighted graphs. Information Processing Letters, 39(5):277 – 281, 1991

1991
[11]

Iwano and N

K. Iwano and N. Katoh. Eﬃcient algorithms for ﬁnding the most vital edge of a minimum spanning tree. Information Processing Letters, 48(5):211–213, 1993

1993
[12]

Karger, P.N

D.R. Karger, P.N. Klein, and R.E. Tarjan. A randomized linear-time algorithm to ﬁnd mini- mum spanning trees. J. ACM, 42(2):321–328, 1995

1995
[13]

Katajainen and J.L

J. Katajainen and J.L. Tr¨ aﬀ. Simple parallel algorithms for the replacement edge problem and related problems on minimum spanning trees. Technical Report DIKU-94/18, Department of Computer Science, University of Copenhagen, 1994

1994
[14]

Kooshesh and R.R

A.A. Kooshesh and R.R. Crawford. Yet another eﬃcient algorithm for replacing the edges of a minimum spanning tree. In Proceedings of the 1996 ACM 24th Annual Conference on Computer Science, CSC ’96, pages 76–78, New York, NY, USA, 1996. ACM

1996
[15]

Kruskal, Jr

J.B. Kruskal, Jr. On the shortest spanning subtree of a graph and the traveling salesman problem. Proc. Amer. Math. Soc., 7:48–50, 1956

1956
[16]

S. Pettie. Sensitivity analysis of minimum spanning trees in sub-inverse-ackermann time. In 16th International Symposium on Algorithms and Computation (ISAAC) , volume 3827 of Lecture Notes in Computer Science , pages 964–973, Sanya, Hainan, China, 2005. Springer

2005
[17]

S. Pettie. Sensitivity analysis of minimum spanning trees in sub-inverse-ackermann time. Journal of Graph Algorithms and Applications , 19(1):375–391, 2015

2015
[18]

Spira and A

P. Spira and A. Pan. On ﬁnding and updating spanning trees and shortest paths. SIAM Journal on Computing , 4(3):375–380, 1975

1975
[19]

Suraweera, P

F. Suraweera, P. Maheshwari, and P. Battacharya. Optimal algorithms to ﬁnd the most vital edge of a minimum spanning tree. Technical Report CIT-95-21, School of Comput. and Inf. Tech., Griﬃth University, 1995

1995
[20]

R.E. Tarjan. A note on ﬁnding the bridges of a graph. Information Processing Letters , 2(6):160–161, 1974

1974
[21]

R.E. Tarjan. Applications of path compression on balanced trees. J. ACM , 26(4):690–715, October 1979. 11

1979

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [1]

Cattaneo, P

G. Cattaneo, P. Faruolo, U. Ferraro Petrillo, and G.F. Italiano. Maintaining dynamic minimum spanning trees: An experimental study. Discrete Applied Mathematics, 158(5):404–425, 2010

work page 2010

[2] [2]

Chin and D

F. Chin and D. Houck. Algorithms for updating minimal spanning trees. Journal of Computer and System Sciences , 16(3):333 – 344, 1978

work page 1978

[3] [3]

T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms, 3rd Edition. MIT Press, Inc., Cambridge, MA, 2009

work page 2009

[4] [4]

Das and M.C

B. Das and M.C. Loui. Reconstructing a minimum spanning tree after deletion of any node. Algorithmica, 31(4):530–547, 2001

work page 2001

[5] [5]

Frederickson

G.N. Frederickson. Data structures for on-line updating of minimum spanning trees, with applications. SIAM Journal on Computing , 14(4):781–798, 1985

work page 1985

[6] [6]

Gabow and R.E

H.N. Gabow and R.E. Tarjan. A linear-time algorithm for a special case of disjoint set union. In Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing , STOC ’83, pages 246–251, New York, NY, USA, 1983. ACM

work page 1983

[7] [7]

Gabow and R.E

H.N. Gabow and R.E. Tarjan. A linear-time algorithm for a special case of disjoint set union. Journal of Computer and System Sciences , 30(2):209 – 221, 1985

work page 1985

[8] [8]

Henzinger and V

M. Henzinger and V. King. Maintaining minimum spanning trees in dynamic graphs. In Proc. of the 24th International Colloquium on Automata, Languages and Programming (ICALP) , pages 594–604, 1997. 10

work page 1997