{"id":"ff058e92-7780-4876-a970-1ea97fe99108","arxiv_id":"2607.25238","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A matroid-intersection implementation that updates a directed minimum spanning tree by repeatedly exchanging edges along negative-cost cycles in an auxiliary graph.","lead":"This paper implements an algorithm that maintains a directed minimum spanning tree (DMST) when edge weights, deletions, or insertions change. It uses weighted matroid intersection: keep an auxiliary graph, find negative-cost cycles, and swap tree edges until no improving cycle remains.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Algorithm 5's in-loop sequential exchange can undo improvements for negative dicycles with n≥2, leaving the main iteration guarantee unproven.","rationale":"The reader's weakest assumption—that the sequential update in Algorithm 5 is equivalent to the simultaneous exchange T△C0—is exactly the load-bearing concern I identify. The matroid-theoretic foundation (Corollary 2 and Theorem 1) is standard and correctly invoked; the failure is in the implementation of the exchange. The paper neither proves an ordering on the loop nor provides a simultaneous update rule, and the f-bijection alternative in Section 4 is unproven. Since the main iteration's progress guarantee depends on correctly performing T△C0, the central claim does not hold as presented. The experiments, lacking error bars and instance counts, do not resolve the issue because random graphs may not expose multi-exchange dicycles or because the shipped code may diverge from the pseudocode. My recommendation is unchanged: the preprint should be rejected as presented, though a corrected and proven atomic update could salvage the contribution.","tokens_in":12142,"tokens_out":10668,"duration_ms":97413,"concrete_test":"Construct a small digraph G and a spanning tree T such that D(T) contains a simple negative dicycle of length 4, e.g., C0 = {y1,x1,y2,x2,y1} with h_{x1}=h_{y2}, h_{x2}=h_{y1}, and no proper negative sub-dicycle. Run Algorithm 5 exactly as pseudocoded (using the dicycle order y1,x1,y2,x2) and also compute the simultaneous exchange T' = (T \\ {y1,y2}) ∪ {x1,x2}. Compare the resulting tree, its weight, and w(T) after the loop. If the sequential version does not equal T' or its weight is not strictly less, the concern is confirmed.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central algorithmic step is the exchange T' = T △ C0 for a simple negative dicycle C0. Algorithm 5 applies this exchange node-by-node inside a 'foreach v∈C0' loop. For C0 = {y1,x1,y2,x2,...,yn,xn,y1}, processing in the natural order y1,x1,y2,x2,... causes the following: when x1 is processed, it replaces the current incoming edge of h_{y2}, namely y2, in T. Later, when the loop reaches y2, y2 is now a non-tree edge (v∈A\\T), so the same branch re-executes: it replaces the current incoming edge of h_{y2}—which is now x1—with y2, undoing the improvement. This happens for every y_{i+1} processed after its replacing x_i. Any iteration order that places a tree edge after the non-tree edge that replaced it has the same failure. For n=1 the exchange is atomic and correct; for n≥2 it generally collapses. The only alternative offered, the bijection f in Section 4, is asserted without proof and does not repair the in-loop T updates. Since simple negative dicycles with n≥2 are generic, the paper's guarantee that each iteration yields a strictly cheaper tree does not follow from the presented algorithm.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper proposes a matroid-intersection-based algorithm for updating a directed minimum spanning tree (DMST) under weight changes, edge deletions, and edge insertions. Given an initial arborescence T, the algorithm constructs the exchange graph D(T), detects simple negative dicycles, and exchanges tree and non-tree edges to decrease the total weight. The paper claims each iteration yields a strictly cheaper arborescence and that the process terminates in at most w(T)-w(T_o) iterations. It also provides pseudocode, complexity bounds, and Python experiments comparing against NetworkX's Edmonds implementation and measuring dynamic-operation speedups.","tokens_in":12371,"tokens_out":23776,"duration_ms":239572,"significance":"If correct, the paper would offer an independent matroid-intersection route to dynamic DMST maintenance with a clean optimality certificate and substantial practical speedups. The theoretical reduction is standard: Theorem 1 and Corollary 2 correctly invoke the negative-dicycle optimality criterion for weighted matroid intersection, and no parameter fitting or circularity is present. The paper also ships code and reproducible experiments, which is a strength. However, the central algorithmic step as written is flawed: Algorithm 5 applies the exchange T△C0 sequentially inside a loop, and for dicycles with n≥2 this can undo the exchange and leave T unchanged. The claimed per-iteration improvement guarantee therefore does not follow from the presented algorithm, and the experimental validation does not repair this gap.","major_comments":[{"comment":"The loop at lines 4–13 of Algorithm 5 updates T inside the `foreach v in C0` loop. For C0={y1,x1,...,yn,xn,y1}, line 7 replaces the current incoming edge of h_v. After x_i is processed, y_{i+1} becomes a non-tree edge; if the loop later reaches y_{i+1}, line 6 is true and line 7 re-inserts y_{i+1}, replacing x_i again. In the natural listing order, every exchange is undone and T returns to its starting value for n≥2; the simultaneous exchange T' = T△C0 is not implemented. The paper gives no ordering argument, and the bijection f in Section 4 is asserted without proof and does not control the order of T updates. This invalidates the per-iteration improvement claim and the iteration bound w(T)-w(T_o), and it can cause non-termination.","section":"Sec. 4, Algorithm 5, lines 4–13; Eq. (2)"},{"comment":"The complexity analysis states that finding a simple negative dicycle runs in O(n^3m) because the loops at line 3 of Algorithm 4 need at most |C|/2 times. This ignores the inner loop of NegativeSubDicycle, which iterates over all nodes v∈C and performs a negative-cycle detection on D_C\\{v} each time; the cost of that detection is not specified. A complete derivation is required before the overall bound O((w(T)-w(T_o)) n^3m) can be claimed.","section":"Sec. 4.2, complexity of Algorithm 4"},{"comment":"The assertion that 'If the negative cycle detection fails at finding a dicycle involving e_out, that means there is no directed spanning tree after deleting e_out' is not proved. After deleting e_out, T is not a common independent set of the modified graph, so applying the negative-dicycle criterion of Corollary 2 to D(T) requires justification. The authors should prove that a replacement arborescence exists iff a dicycle involving e_out appears in the updated exchange graph, and that the first exchange yields a valid tree.","section":"Sec. 4.1, edge-deletion paragraph"}],"minor_comments":[{"comment":"The displayed composition of T' by sub-trees 'x_n ∪ H1, x_1 ∪ H2, ..., x_{n-1}∪H_n' appears index-shifted relative to the relation h_{x_i}=h_{y_{i+1}}; please verify the indices.","section":"Sec. 3.2, after Eq. (2)"},{"comment":"The sentence 'The root vertex r does not have to be the same for all independent sets of I2' is confusing, since the root is fixed for the DMST problem; rephrase.","section":"Sec. 2, partition matroid definition"},{"comment":"The cyclic-detection complexity relies on Tarjan's subtree disassembly; cite a published version or give enough detail to verify the stated bound.","section":"Sec. 4.2, Tarjan reference [37]"},{"comment":"The experimental section reports averages without standard deviations or instance counts; error bars would help assess the claimed speedups.","section":"Sec. 5"},{"comment":"Typos: 'constrast' (Introduction), 'dicyle' (Sec. 3.2), 'overal' (Sec. 5.1); a final proofread is needed.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The reader's report is essentially correct about Algorithm 5. The manuscript is not circular and the matroid-intersection framework is standard, so I do not see grounds for outright rejection if the authors fix the exchange step and re-run the experiments. However, the corrected pseudocode needs a formal proof that it implements the simultaneous exchange T△C0, and the edge-deletion claim in Section 4.1 needs a rigorous justification. Without those fixes, the central contribution would not be acceptable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nHere's my take on arXiv:2607.25238. The paper's theoretical base is solid: weighted matroid intersection with negative-dicycle detection is a standard and correct way to characterize optimality for directed spanning trees, and the authors properly credit Brezovec et al. and Fujishige for Theorem 1 and Corollary 2. What's new is the engineering—maintaining the auxiliary graph under weight changes, deletions, and insertions, plus the subroutine that distills a negative dicycle into a simple one so that the exchange yields a valid tree. That's a legitimate contribution, though modest.\n\nThe central problem is Algorithm 5. The pseudocode updates T inside the loop over the dicycle's nodes. For a simple negative dicycle with n≥2 exchanges, e.g. {y1,x1,y2,x2,...,yn,xn}, processing in the listed order does: when x_i is processed, it replaces the current incoming edge y_{i+1}; later, when the loop reaches y_{i+1}, that edge is now non-tree, so the same branch executes and swaps it back in for x_i. The improvement is undone. This isn't a subtle point—it's visible in the pseudocode, and no proof of an ordering or simultaneous update is offered. The bijection f in Section 4 describes how the auxiliary graph's I2-arcs transform, but it does not justify the in-loop mutation of T. So the paper's guarantee that each iteration strictly decreases weight does not follow.\n\nOn the experimental side, the results are suggestive but underreported: no instance counts, no error bars, no comparison with the existing dynamic DMST algorithm (Pollatos et al.), and the GitHub link is not verified. The worst-case complexity is pseudopolynomial and higher than Edmonds' algorithm, so the practical claim rests entirely on the experiments.\n\nThat said, the paper is not incoherent. The underlying theory is sound, the authors are honest about what comes from the literature, and the flaw is fixable—swap all tree edges out first, then add the non-tree edges, or simply compute T' = T △ C0 atomically. With that corrected and proven, the engineering could be useful for dynamic DMST maintenance.\n\nWho benefits? Researchers working on matroid-based arborescence algorithms would find the auxiliary graph construction and the simple-negative-dicycle routine worth reading. I'd send this to peer review, but the reviewers should be asked to verify Algorithm 5 explicitly. A desk reject would be premature, because the core idea is right and the bug is repairable.\n\nBest.","headline":"Correctly applies known matroid-intersection theory to DMST, but Algorithm 5's sequential exchange can undo itself for n≥2 dicycles—the main convergence claim doesn't hold as written.","tokens_in":12888,"tokens_out":5297,"would_cite":false,"duration_ms":51072,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C20","05B35","90C27"],"pacs":[],"model":"deepseek-v4-flash","headline":"Negative cycles in an auxiliary graph drive any arborescence to the optimal one","keywords":["directed spanning tree","arborescence","matroid intersection","dynamic graph algorithm","negative cycle detection","auxiliary graph","edge weight update","combinatorial optimization"],"falsifier":"Run Algorithm 5 on a small digraph whose simple negative dicycle C0 contains at least two non-tree edges (n ≥ 2) and verify whether the weight of T strictly decreases after the foreach loop completes; if any such instance yields no decrease or a higher weight, the 'each iteration is guaranteed to yield an improved solution' claim is false. A direct trace with C0 = {y1,x1,y2,x2,y1} shows that the second branch may delete x1 and reinsert y2, producing T′ = T rather than T △ C0.","tokens_in":11978,"feed_emoji":"🧭","tokens_out":5192,"duration_ms":40972,"temperature":0.7,"pith_summary":"The paper sets out to show that a directed minimum spanning tree (DMST) can be maintained and optimized through the weighted matroid intersection algorithm, without recomputing from scratch with the standard contract-and-expand approach. Its central claim is that a subgraph is a DMST exactly when it is a common independent set of two matroids with no negative-cost directed cycle in a derived auxiliary graph. On this basis, the paper builds an iterative update: find a simple negative dicycle, swap the tree and non-tree edges along it via symmetric difference, and repeat; each swap strictly lowers the total weight, and the process terminates at an optimal tree. The same auxiliary graph makes edge insertions and deletions local operations, and the experiments show this is substantially faster than recomputing a DMST. Why it matters: dynamic arborescence maintenance appears in network optimization and hardware design, and a matroid-based alternative may be simpler to implement and adapt.","feed_headline":"Negative cycles guide any tree to the minimum directed spanning tree","feed_subtitle":"Weight changes, deletions, and insertions are handled locally, so the tree can be updated without recomputing from scratch.","key_machinery":"The auxiliary graph D(T) — a bipartite digraph whose nodes are the edges of G — is the central object. I1-arcs (y, x) say that replacing tree edge y by non-tree edge x keeps the underlying undirected graph acyclic; I2-arcs (x, y) say the same replacement keeps the indegree constraint of the partition matroid. The cost function l turns the optimality question into a negative-dicycle detection problem on this graph. The algorithm's engine is the simple negative dicycle: a negative dicycle containing no negative sub-dicycle, which Theorem 1 guarantees can be exchanged via symmetric difference to produce a cheaper arborescence. The paper's update loop maintains D(T) by recomputing I1-arcs with l","core_discovery":"Corollary 2 is the load-bearing statement: a subgraph T of a weighted digraph is a directed minimum spanning tree rooted at r if and only if T belongs to both the graphic matroid and the partition matroid, has |V|−1 edges, and the auxiliary graph D(T) — whose arcs encode which single-edge exchanges preserve matroid independence — contains no negative dicycle under the cost l(e) = −w(e) for e∈T and l(e)=w(e) for e∉T. Starting from any arborescence, the paper's algorithm detects a simple negative dicycle (one with no negative sub-dicycle), forms T′ = T △ C0, and, by Theorem 1(iii), T′ is again a directed spanning tree with strictly smaller weight. Repeating this exchange yields a strictly decr","pith_inferences":["If the simultaneous-exchange correctness is fixed or proven, the approach could serve as a local-search oracle for any arborescence problem, including variants with degree or color constraints, since matroid intersection handles these constraints naturally.","The auxiliary graph structure suggests a sensitivity analysis tool: the cost of the dicycle through a non-tree edge measures how much its weight must change before it enters the optimal tree — a quantity that contract-and-expand algorithms do not expose directly.","Because the auxiliary graph is bipartite, negative-dicycle detection might be accelerated with specialized bipartite shortest-path algorithms, potentially improving the worst-case bound in practice.","The experimental methodology could be extended to include adversarial or structured graphs, not just random graphs, to stress-test the sequential-update loop, especially cases with long dicycles containing several exchanges."],"forward_implications":["If a given tree T has no negative dicycle in D(T), then T is already a DMST; otherwise any simple negative dicycle gives a concrete set of edge exchanges that strictly decreases the total weight.","Repeatedly applying the exchange converges to a DMST, generating a sequence of arborescences of strictly decreasing cost, which can be stopped early as an anytime algorithm.","Edge deletion of a tree edge can be handled by setting its weight to infinity and running the same update; deletion of a non-tree edge leaves the DMST unchanged.","Edge insertion reduces to adding the new node to D(T), computing its I1-arcs via LCA, its I2-arcs from the head's tree edge, and testing for a negative dicycle through it.","The dynamic experiments report average time gains around 50% for deletions and over 75% for insertions on random dense and sparse graphs compared to recomputing the DMST statically."],"fun_headline_variants":["Negative cycles steer trees to optimality fast","Matroid intersection finds new MST via dicycles","Quick tree updates from negative-cycle swaps","Directed trees: beat weight changes with negative dicycles"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"Algorithm 5's pseudocode updates the tree edge-by-edge inside the loop over the dicycle, and the paper assumes this sequential update is equivalent to the simultaneous exchange T′ = T △ C0; if a dicycle contains two or more exchanges, the loop can undo an earlier swap, so the claimed guarantee that every iteration improves the solution may fail without an ordering proof.","fun_headline_variants_meta":{"raw":{"variants":["Negative cycles steer trees to optimality fast","Matroid intersection finds new MST via dicycles","Quick tree updates from negative-cycle swaps","Directed trees: beat weight changes with negative dicycles"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000124,"raw_usage":{"total_tokens":893,"prompt_tokens":650,"completion_tokens":243,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":394,"completion_tokens_details":{"reasoning_tokens":184}},"tokens_in":394,"tokens_out":243,"duration_ms":3353,"temperature":1.0,"reasoning_tokens":184,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-01T03:02:46.021065+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run Algorithm 5 on a small digraph whose simple negative dicycle C0 contains at least two non-tree edges (n ≥ 2) and verify whether the weight of T strictly decreases after the foreach loop completes; if any such instance yields no decrease or a higher weight, the 'each iteration is guaranteed to yield an improved solution' claim is false. A direct trace with C0 = {y1,x1,y2,x2,y1} shows that the second branch may delete x1 and reinsert y2, producing T′ = T rather than T △ C0.","supporting_citations":[],"review_version":1}