{"id":"ae532f39-31cf-485b-92e3-4278ac66c9a7","arxiv_id":"1908.03473","paper_version":4,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Presents an O(m+n) algorithm for finding all minimum spanning tree replacement edges when the MST and sorted non-tree edges are given.","lead":"The paper presents an algorithm that computes, for every edge of a minimum spanning tree, the cheapest replacement edge that reconnects the tree, in linear time once non-tree edges are sorted by weight. The previous best algorithm was nearly linear but not quite linear.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 2's O(m+n) bound is conditional on an unverified Gabow-Tarjan DSU reduction and an incomplete find-counting proof in Claim 4.","rationale":"The reader's weakest-assumption analysis correctly identifies the Gabow-Tarjan dependency as the critical point. My own read of Algorithm 1 suggests the algorithm is likely correct and the charging argument can probably be repaired, but the manuscript does not supply that argument. Since Theorem 2's linear-time claim stands or falls with Claim 4 and the external GT theorem, the appropriate verdict remains CONDITIONAL: the central idea is plausible and the correctness argument is mostly sound, but the proof of the O(m+n) bound is not fully established in the text. I agree with the reader's verdict and do not recommend changing it.","tokens_in":8532,"tokens_out":36913,"duration_ms":410538,"concrete_test":"Instrument Algorithm 1 with an explicit Gabow-Tarjan static-tree DSU and run it on all small graphs (n up to 8) plus random large graphs, logging every find and link. Verify: (i) link(v) is called only when find(v)==v, (ii) P[v] is the parent of v in the MST, and (iii) total find operations are at most 2*(number of links + 2*(m-n+1)). If any run violates these invariants, Claim 4 is false and Theorem 2's bound does not follow. Independently check the Gabow-Tarjan paper to confirm that its O(m+n) bound applies to online sequences with the union tree known in advance; if it is offline-only, the reduction is invalid.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is Theorem 2: Algorithm 1 finds all replacement edges in O(m+n) time. The only route to this bound is Claim 4, which invokes the Gabow-Tarjan linear-time disjoint-set-union special case and asserts that the cycle scans generate O(m) find operations. This is the load-bearing condition. The paper does not actually prove that the online, weight-dependent sequence of find/link calls generated by Algorithm 1 is inside the model for which Gabow-Tarjan's O(m+n) bound is stated. In particular, Claim 4's counting is incomplete: it does not show that every iteration of the while loop except at most one per PathLabel call is charged to a link, nor does it address the case where path compression jumps the walk to a representative above the LCA, which is only illustrated anecdotally in Section 3.1. If the Gabow-Tarjan bound requires the link sequence to be known in advance, or if a PathLabel call can contain more than one uncharged find, the linear-time claim fails and the best bound shown with textbook union-find is O(m alpha(m,n)). Thus the headline result is conditional on an external, nontrivial DSU theorem and on a missing charging proof; it is not self-contained as written.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":8771,"tokens_out":15279,"duration_ms":156834,"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":[{"comment":"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":"Section 3.2, Claim 2"},{"comment":"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":"Section 3.3, Claim 4"},{"comment":"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.","section":"Section 3.3, Theorem 2"}],"minor_comments":[{"comment":"The phrase 'worse-case' should be 'worst-case.'","section":"Abstract and Section 1"},{"comment":"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":"Section 3.1"},{"comment":"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.","section":"Section 2, Related Work"},{"comment":"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.","section":"Algorithm 1, line 2"}],"recommendation":"major_revision","confidential_remarks":"I found no internal counterexample to the algorithm's correctness or to the claimed asymptotic bound; the issues are in the rigor of the proof, not in the underlying idea. The most important external risk is the novelty statement: the claim that this is the first linear-time algorithm for the sorted-edges model should be checked by an editor or a referee familiar with the MST sensitivity-analysis literature. I am not aware of a prior algorithm under exactly this model, but the related-work section does not fully establish non-existence. The Gabow-Tarjan dependence is legitimate in my view, but the manuscript must state the theorem's hypotheses so the reader can verify the reduction."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nWhat 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.\n\nSoft 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.\n\nThe 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.\n\nBottom 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.","headline":"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.","tokens_in":9234,"tokens_out":4747,"would_cite":true,"duration_ms":54365,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["minimum spanning tree","replacement edges","most vital edge","linear time algorithm","disjoint set union","fundamental cycle","dynamic graphs","path compression"],"falsifier":"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.","tokens_in":8357,"feed_emoji":"🛣️","tokens_out":9735,"duration_ms":100160,"temperature":0.7,"pith_summary":"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.","feed_headline":"Every MST edge gets its cheapest replacement in O(m+n)","feed_subtitle":"One DFS pass plus path-compressed cycle scans replaces the old near-linear bound and finds the most vital edge.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the linear-time special case of disjoint set union for unions whose tree is known in advance, the operation that makes path compression linear.","marker":"[6, 7]"},{"why":"Gives the previous deterministic $O(m\\alpha(m,n))$ baseline for the replacement-edge problem that the paper aims to improve.","marker":"[21]"},{"why":"States the Cut Property used in Claim 1 to justify taking the lightest non-tree edge in a fundamental cycle as the replacement.","marker":"[3]"},{"why":"Provides the MST construction whose sorted edge order supplies the sorted non-tree-edge input the algorithm assumes.","marker":"[15]"},{"why":"Linear-time bridge detection used to terminate the scan early after all non-bridge replacements are found.","marker":"[20]"},{"why":"Supports the most-vital-edge section by showing the most vital edge lies in the MST.","marker":"[19]"}],"fun_headline_variants":["Linear-time MST replacement edges, finally practical","All MST edge replacements in O(m+n) time","First linear algorithm for MST replacement edges","MST replacement edges: O(m+n) and simplest yet","Find every MST edge's replacement in linear time"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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))$.","fun_headline_variants_meta":{"raw":{"variants":["Linear-time MST replacement edges, finally practical","All MST edge replacements in O(m+n) time","First linear algorithm for MST replacement edges","MST replacement edges: O(m+n) and simplest yet","Find every MST edge's replacement in linear time"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000165,"raw_usage":{"total_tokens":1221,"prompt_tokens":887,"completion_tokens":334,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":503,"completion_tokens_details":{"reasoning_tokens":262}},"tokens_in":503,"tokens_out":334,"duration_ms":4015,"temperature":1.0,"reasoning_tokens":262,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:13:44.068689+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the previous deterministic $O(m\\alpha(m,n))$ baseline for the replacement-edge problem that the paper aims to improve."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"States the Cut Property used in Claim 1 to justify taking the lightest non-tree edge in a fundamental cycle as the replacement."},{"cited_title":"Kruskal, Jr","cited_arxiv_id":null,"evidence_quote":"Provides the MST construction whose sorted edge order supplies the sorted non-tree-edge input the algorithm assumes."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Linear-time bridge detection used to terminate the scan early after all non-bridge replacements are found."},{"cited_title":"Suraweera, P","cited_arxiv_id":null,"evidence_quote":"Supports the most-vital-edge section by showing the most vital edge lies in the MST."}],"review_version":1}