{"id":"30c192c8-59b9-4f0f-befd-0f56239983ab","arxiv_id":"2607.20211","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Four fully dynamic parallel GPU algorithms maintain a rooted spanning forest under batch edge updates, achieving up to 900x speedup over static GPU BFS.","lead":"This paper presents four parallel GPU algorithms that update a rooted spanning tree when edges are inserted or deleted in batches, instead of rebuilding the tree from scratch. It reports throughput of 2 million insertions and 1.4 million deletions per second on real-world graphs, which could make dynamic network analysis much faster on GPUs.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Algorithm 1's deletion path processes non-tree edges as if they were tree edges, detaching vertices for 60–70% of a delete batch; Theorem 1's proof only covers tree-edge deletion.","rationale":"The reader correctly identifies the Euler-tour interval condition in Algorithm 3 as underproved, and that is a genuine weakness because all four algorithms depend on it. However, the more immediately falsifiable concern is Algorithm 1's deletion loop, which is both concrete and load-bearing: the problem definition allows arbitrary batches, the experimental protocol deliberately includes non-tree edges in deletion batches, and the pseudocode applies a tree-edge operation to every edge in B. This invalidates Theorem 1's correctness argument as written. The issue is addressable with a one-line guard (iterate only over B ∩ E(F)), so the conditional verdict remains appropriate rather than escalating to rejection. If the published implementation already contains such a guard, the pseudocode and proof must be corrected; if it does not, the deletion experiments are not evidence for the claimed correctness. Thus I keep the reader's CONDITIONAL verdict but shift the primary concern from Algorithm 3's interval condition to Algorithm 1's deletion handling.","tokens_in":13884,"tokens_out":10823,"duration_ms":104122,"concrete_test":"Run the public code on a triangle 1-2, 2-3, 3-1 with forest F = {(1,2), (2,3)} rooted at 1. Delete only the non-tree edge (1,3) and inspect parent[3] (or parent[1], depending on edge order). The correct result is an unchanged forest with root 1 and parent[3]=2. If parent[3] becomes 3 or parent[1] becomes 1 (when 3 is the first endpoint), the implementation matches the buggy pseudocode. Alternatively, add an assertion at Line 5 that (u,v) is an edge of F and run any deletion batch with non-tree edges; the assertion will fail immediately.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim includes fully dynamic deletion on arbitrary edge batches. Algorithm 1, Lines 4–6, iterates over every edge (u,v) in the deletion batch B and unconditionally executes parent[u] = u, with the comment 'Let v be the parent of u.' This is only valid if (u,v) is a tree edge. However, Section V-A states that delete batches intentionally mix tree edges (30–40%) with non-tree edges (60–70%). For a non-tree edge, v is not parent[u], yet the pseudocode still detaches u from its tree, creating a spurious root and fragmenting the forest. The proof of Theorem 1 only considers deletion of tree edges and computes key edges as M = (E(G) − E(F)) − B, so it does not repair the artificial components created by Line 5. The accompanying text says 'for each tree edge in B, the forest F is updated,' but the pseudocode lacks the required tree-edge guard. If the public implementation follows the pseudocode, deletion batches containing non-tree edges will corrupt the forest; if it contains a guard, the pseudocode and proof omit it. This is a load-bearing gap in the deletion correctness argument, independent of the underproved Euler-tour interval condition in Algorithm 3.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper defines the D-RSF problem (batch insertion/deletion of edges in an undirected graph while maintaining a rooted spanning forest) and presents four GPU parallel algorithms: SG-ET, SG-BC, HS-ET, and HS-BC. The generic algorithm (Algorithm 1) repairs the existing forest by computing oriented replacement edges using either a supergraph or hooking-shortcutting, then reverses paths using either an Euler-tour or broadcasting subroutine. The authors claim depth bounds O(log n + log^2 k) and O(log^2 n), O(V+E) space for the ET variants, and report throughputs of 2 million insertions and 1.4 million deletions per second on an A100, with up to 900x/500x speedups over static GPU BFS.","tokens_in":14220,"tokens_out":10599,"duration_ms":112138,"significance":"If the correctness and complexity claims held, this would be a useful systems contribution: it appears to be among the first GPU implementations of batch-dynamic spanning-forest maintenance, the implementation is publicly available, and the evaluation is reasonably broad (13 graphs, several batch sizes, comparisons against static BFS and PR-RST). The algorithms are parameter-free and the engineering story (repair instead of recompute) is coherent. However, the manuscript currently does not deliver the formal guarantees it advertises: the deletion loop in the pseudocode is incorrect as written, and the proofs of path reversal and of the main depth theorems are incomplete. These are load-bearing for the central claims, so the paper cannot be accepted in its present form.","major_comments":[{"comment":"The deletion loop iterates over every edge (u,v) in B and unconditionally executes parent[u]=u. Section V-A states that delete batches deliberately contain 60-70% non-tree edges. For a non-tree edge, v is not parent[u], so line 5 turns u into an artificial root and fragments F beyond the actual tree-edge deletions. The proof of Theorem 1 only treats tree-edge deletion, and Line 3 already removes these non-tree edges from the key-edge set M, so the algorithm never repairs the artificial components. Please add a tree-edge guard in the pseudocode and proof, or explain why line 5 is safe. This is load-bearing for the full-dynamic deletion claim.","section":"Algorithm 1, Lines 4-5; Theorem 1; Section V-A"},{"comment":"The correctness proof of the Euler-tour path reversal is a hand-wave. It uses first[x_i], first[u_i], last[x_i], last[v_i], while Algorithm 3 defines start/finish, and no connection between the two notations is given. The statement Path(x_i,y_i)=U intersection V is asserted without proof. In a rooted Euler tour the interval condition can be made correct, but the paper must prove it for leaves, roots, and intermediate vertices, and must also argue that the parallel loop at Lines 13-17 reverses exactly the edges on the path and no others. All four algorithms depend on REVERSEPATHS, so this is central.","section":"Lemma 4; Algorithm 3"},{"comment":"Theorems 3 and 4, which state the depth and work guarantees for all four algorithms, are presented with no proofs. Theorem 2 also states the O(log n) depth and O(n) work of Algorithm 3 without proof. These theorems support Table I and the abstract's complexity claims. Please provide proofs or at least a detailed derivation showing how the subroutines' depths compose for each of the four algorithms.","section":"Theorems 2-4; Section IV"},{"comment":"The supergraph method relies on the assertion that 'eventually no two pairs in the hash table have same key, due to race conditions.' This is an unverified concurrency assumption. Since an arbitrary representative edge between the same pair of trees is sufficient for connectivity, the assumption may be acceptable, but it should be stated explicitly and justified, or the implementation should use deterministic duplicate elimination so correctness does not rest on undefined GPU write races.","section":"Section III-A; hash-table construction"}],"minor_comments":[{"comment":"Reference [10] is cited as 'HDT', but the reference list entry is Acar et al., 'Parallel batch-dynamic graph connectivity'. The Holm-de Lichtenberg-Thorup paper is not cited. Please fix the attribution.","section":"Table I; References"},{"comment":"Notation is inconsistent: the proof uses first/last, while the algorithm uses start/finish. Also, 'firstEdge' and 'lastEdge' are not formally defined. Please align the notation and define the Euler-tour edge ordering used.","section":"Lemma 4; Algorithm 3"},{"comment":"There are numbering inconsistencies: Section V-C refers to Figure 5 for runtime, but Figure 5 appears after the discussion of speedups; check all figure references. Also, Section V-B states 'by by Cong et al.' - typo.","section":"Figure/table numbering"},{"comment":"The strict vs. non-strict inequalities in the interval test should be explained. In particular, the condition excludes the root r, which is correct for path reversal, but the lemma statement and proof should make this precise.","section":"Algorithm 3, Line 15"},{"comment":"The sentence describing the composition of delete batches could be clarified: it should say explicitly that the remaining 60-70% are non-tree edges, and explain how this interacts with the pseudocode of Algorithm 1.","section":"Section V-A"}],"recommendation":"major_revision","confidential_remarks":"To the editor: The paper has a serious pseudocode bug in the deletion case and lacks proofs for several theorems; however, these are fixable within the manuscript's scope. The experimental results appear promising, but I did not re-run the code. The novelty claim ('first GPU dynamic spanning forest') may merit a closer scope check, and the related-work table misattributes HDT to reference [10]. I recommend major revision rather than rejection, contingent on the authors fixing the deletion guard and providing rigorous proofs for the path-reversal and depth claims."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper is the first serious attempt at GPU batch-dynamic rooted spanning forest maintenance, and it ships code and large speedups. But the deletion algorithm as written has a load-bearing correctness gap: it detaches vertices for every edge in the delete batch, while the proof only covers tree edges. That needs to be settled before the headline numbers can be trusted.\n\nWhat is actually new: combining supergraph/Hooking-Shortcutting for oriented replacement edges with Broadcasting/Euler-tour path reversal on GPU. The Euler-tour path-reversal subroutine is a real design change from prior multicore work. The experiments cover 13 graphs up to ~1B edges, compare against static BFS and a ported PR-RST, and the HS/SG tradeoff analysis in Section V-D is sensible. Public code helps.\n\nSoft spots, in proportion:\n1. Algorithm 1, Lines 4-6, executes parent[u] = u for every (u,v) in B. If (u,v) is non-tree, v is not parent[u], and u gets detached from its tree. Their delete batches deliberately contain 60-70% non-tree edges (Section V-A), so this is not a corner case. Theorem 1's proof only considers tree-edge deletion. Either the code has a tree-edge guard the paper fails to show, or the algorithm corrupts the forest. This is the main blocker.\n2. Lemma 4's proof is a single paragraph with inconsistent first/last vs start/finish notation and does not rigorously show the interval condition matches path membership. The interval test in Algorithm 3 is central, so this needs a real proof.\n3. Theorems 3 and 4 state depth/work bounds without proof. They may be right, but \"we analyze\" followed by a statement with no argument is not enough.\n4. The hash-table race condition in Section III-A is hand-waved (\"eventually no two pairs have same key\"). Unspecified races are a red flag for GPU code.\n5. Experiments compare only against static baselines and report no variance bars. Given 25 runs, showing distributions or at least min/max would strengthen the claims. The speedups over static recomputation are expected, but the trend across batch sizes is still informative.\n\nBottom line: the core idea is plausible and likely salvageable, but as submitted the deletion correctness is not established. This deserves a serious referee, but the authors need to fix the pseudocode/proof mismatch, prove the interval condition, and provide proofs for the complexity theorems. I would not cite it in its current form.","headline":"First serious GPU batch-dynamic rooted spanning forest work with strong speedups, but the deletion pseudocode detaches vertices for non-tree edges while the proof only covers tree edges; that gap needs to be fixed before the results can be trusted.","tokens_in":14650,"tokens_out":2678,"would_cite":false,"duration_ms":25462,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Four GPU algorithms update a rooted spanning forest under batch edge changes without rebuilding it.","keywords":["dynamic spanning tree","GPU algorithm","batch updates","rooted spanning forest","Euler tour","hooking and shortcutting","supergraph","path reversal"],"falsifier":"Run Algorithm 3 on a small rooted tree with a known path and check whether the set of flipped parent edges exactly matches that path — any mismatch, such as flipping an off-path vertex or missing an on-path vertex, would show the interval condition is unsound. A broader test applies the full pipeline to a random graph with a batch of deletions and compares the resulting forest against a static spanning-tree computation on the updated graph.","tokens_in":13814,"feed_emoji":"🌲","tokens_out":4671,"duration_ms":43245,"temperature":0.7,"pith_summary":"The paper tries to establish that a rooted spanning forest can be maintained dynamically on a GPU: when a batch of edges is inserted or deleted, the forest is repaired locally rather than recomputed from scratch. It splits the repair into two subtasks — finding oriented replacement edges that reconnect the forest, and reversing the orientation of selected tree paths to accept those edges — and gives four parallel algorithms, each pairing a method for one subtask with a method for the other. If correct, an update that would cost a full graph traversal becomes a polylogarithmic-depth pass, and experiments on large real-world graphs report millions of updates per second, with speedups of hundreds to thousands over static GPU BFS.","feed_headline":"GPU updates spanning forests up to 900x faster than BFS","feed_subtitle":"Four dynamic algorithms repair the forest after edge insertions or deletions, reaching 2M updates per second on an A100.","key_machinery":"The load-bearing mechanism is the interval test in Algorithm 3: using Euler-tour start and finish times, a vertex u is judged to lie on the path from x to the tree's root r exactly when start[r] < start[u] ≤ start[x] and finish[r] > finish[u] ≥ finish[x]. This test lets all affected paths be reversed in parallel, and its correctness determines whether parent pointers are flipped correctly. The supporting machinery is the generic split into oriented replacement edges (via a supergraph of connected components or via hooking-shortcutting on component representatives) and path reversal (via broadcasting or the Euler tour).","core_discovery":"On its own terms, the paper claims that fully dynamic batch updates to a rooted spanning forest are practical on GPUs. The central idea is a generic algorithm that, after a batch update, finds a set of oriented replacement edges that reconnect the forest's components, then reverses the parent-child orientation along selected paths so the new edges can be attached without creating cycles. Two techniques are offered for each subtask: Supergraph and Hooking-Shortcutting for finding replacement edges, and Broadcasting and an Euler-Tour-based method for path reversal. The paper proves depth bounds — O(log n + log^2 k) for the Supergraph variants and O(log^2 n) for the Hooking-Shortcutting variant","pith_inferences":["The Euler-tour interval test is essentially an ancestor query; if it holds, it could be reused in other parallel path-reversal tasks, such as batch operations on link-cut trees or dynamic tree data structures.","The paper compares only against static baselines, so a head-to-head with a GPU-adapted hierarchical dynamic-connectivity algorithm would sharpen the practical claims.","Because deletions require scanning all non-tree edges to form the key-edge set, deletion cost scales with edge density; an extension that restricts the scan to components that actually split could improve dense-graph performance."],"forward_implications":["Batch updates to a spanning forest become polylogarithmic in depth, independent of the graph's diameter, so deep and large graphs can be updated quickly on GPUs.","The Euler-tour path-reversal variant uses O(V+E) space, whereas broadcasting needs O(V log V), making the Euler variant more practical for memory-bound GPUs.","The same pipeline can maintain connected components under dynamic insertions and deletions, not just spanning forests, as the paper notes.","The reported speedups suggest that dynamic repair, rather than static recomputation, is a viable strategy for evolving graphs with frequent small-to-moderate batch updates."],"fun_headline_variants":["2M insertions, 1.4M deletions/sec on GPU","GPU dynamic spanning forest: batch updates, no rebuild","Fully dynamic rooted spanning trees, now GPU-accelerated","No rebuild: GPU updates rooted spanning trees in batches","GPU maintains spanning forests under dynamic edge updates"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"Everything hinges on the interval test — the claim that comparing Euler-tour start and finish times correctly identifies exactly which vertices lie on each path to the root; if the test is wrong for a single vertex, the parent flips can create a cycle or disconnect the forest.","fun_headline_variants_meta":{"raw":{"variants":["2M insertions, 1.4M deletions/sec on GPU","GPU dynamic spanning forest: batch updates, no rebuild","Fully dynamic rooted spanning trees, now GPU-accelerated","No rebuild: GPU updates rooted spanning trees in batches","GPU maintains spanning forests under dynamic edge updates"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.002333,"raw_usage":{"total_tokens":8794,"prompt_tokens":674,"completion_tokens":8120,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":418,"completion_tokens_details":{"reasoning_tokens":8040}},"tokens_in":418,"tokens_out":8120,"duration_ms":54696,"temperature":1.0,"reasoning_tokens":8040,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-01T10:27:50.500212+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run Algorithm 3 on a small rooted tree with a known path and check whether the set of flipped parent edges exactly matches that path — any mismatch, such as flipping an off-path vertex or missing an on-path vertex, would show the interval condition is unsound. A broader test applies the full pipeline to a random graph with a batch of deletions and compares the resulting forest against a static spanning-tree computation on the updated graph.","supporting_citations":[],"review_version":1}