{"id":"7614cc72-5588-404a-ba78-733c7932fe8c","arxiv_id":"2506.18384","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A set of sequential, parallel, and batch-parallel algorithms that explicitly maintain the single-linkage dendrogram of a dynamic forest, with update costs O(h), O(h log(1+n/h)), or O(c log(1+n/c)).","lead":"This paper gives the first algorithms for updating a single-linkage dendrogram, the tree of cluster merges, when edges are added to or removed from the underlying minimum spanning forest. The update cost scales with the height of the dendrogram or with the number of actual changes, and the paper fills the theoretical gap between maintaining a spanning tree and maintaining the actual cluster tree.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"PWS query in §4.1 can skip the connecting vertices between path-decomposition clusters, so it may return the wrong predecessor; Theorem 1.2's output-sensitive merge is therefore not established as written.","rationale":"The reader correctly identified the PWS machinery as the weakest assumption behind the output-sensitive result, but the concern can be sharpened: the problem is not only that the implementation is sketched, but that the sketched search procedure ignores a class of vertices that the manuscript itself says are absent from cluster paths. If that gap is real, the central near-optimal insertion bound does not follow. I am not raising a consensus disagreement or an ad hominem point; this is an internal correctness question about Section 4.1. I also considered the false inequality h >= log^2 n and the unproven batch-deletion concurrency claim, but those are secondary: the first is likely a typo for h >= log n, which holds for binary dendrograms, and the second affects only Theorem 1.5. The PWS issue, by contrast, underpins both Theorem 1.2 and Theorem 1.4, and it is concretely testable. If the concrete test shows PWS can be made correct by including connecting vertices within the same O(log n) query bound, the conditional verdict can stand with a request for a full proof; if it cannot, the output-sensitive results are unproven and the paper's strongest new claim is compromised.","tokens_in":24712,"tokens_out":37533,"duration_ms":403308,"concrete_test":"Build a minimal RC-tree path decomposition of a monotone spine whose cluster paths have weight ranges, say, [1,3] and [7,9], with a connecting vertex of weight 5 between them. Run the §4.1 PWS algorithm for a query weight w=6; if it returns 3 instead of 5, the described implementation is wrong. More generally, implement PWS exactly as written and fuzz it against a brute-force predecessor query on random monotone paths in an RC tree, including cases where the true predecessor is a connecting vertex between two path-decomposition clusters; report any mismatch. A single mismatch falsifies the O(log n) PWS claim as stated, and a corrected implementation must explicitly handle connecting vertices or store ranges that include them.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Theorem 1.2 rests entirely on the output-sensitive spine merge, and that merge rests on the path weight search (PWS) query of §4.1. The PWS implementation is not just sketched; it appears to be internally inconsistent with the paper's own path median query. A path decomposition returns binary clusters whose cluster paths are disjoint, and the path median query explicitly counts 'the number of clusters in the path decomposition plus one' because the vertices connecting consecutive clusters are not part of any cluster path. The PWS query, however, treats the cluster weight ranges as an ordered sequence covering the whole path: if w falls between two ranges it returns the maximum of the lower range, and otherwise it descends into the cluster whose range contains w. If the true predecessor of w is a connecting vertex, whose weight lies in the gap between two cluster-path ranges, this procedure returns a lower-weight node or descends into the wrong cluster. In the spine merge, a PWS query must return exactly the node whose parent changes; a wrong predecessor produces incorrect parent pointers and breaks the claimed c-charge. The sequential analysis also asserts that each RC-tree node is visited at most twice without accounting for these gap vertices. Thus the O(c log(1+n/c)) insertion bound, and the parallel output-sensitive work bound in Theorem 1.4, are not supported by the text as it stands.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the fully-dynamic maintenance of single-linkage dendrograms (SLDs) over a dynamic forest. The authors propose an insertion algorithm in O(h) time and a deletion algorithm in O(h log(1+n/h)) time, where h is the dendrogram height; parallel and batch-parallel versions with poly-logarithmic depth; and an output-sensitive insertion algorithm in O(c log(1+n/c)) time, where c is the number of parent-pointer changes. The algorithms are based on the spine-merge technique of Dhulipala et al. and on rake-compress (RC) trees, and the paper also introduces path weight search and path median queries on RC trees. The claimed results, if correct, would be the first explicit SLD maintenance algorithms asymptotically faster than static recomputation, and they are connected to dynamic Cartesian tree maintenance.","tokens_in":24965,"tokens_out":11617,"duration_ms":126126,"significance":"The problem is well motivated and the paper fills a genuine gap between dynamic minimum spanning forest maintenance and explicit dendrogram maintenance. The height-bounded and output-sensitive bounds are natural and, if established, would be significant contributions to dynamic hierarchical clustering and to the toolbox of parallel dynamic tree queries. The paper relies on prior peer-reviewed techniques (spine-merge in [19], RC trees in [2,5,7]) in a non-circular way, and the proposed PWS and path median queries are interesting primitives in their own right. However, the correctness of the output-sensitive bounds rests on a PWS implementation that is internally inconsistent with the paper's own path median accounting, and the batch-deletion correctness argument is asserted rather than proved. These issues affect the central claims, so the current version is not yet publishable as is.","major_comments":[{"comment":"The PWS query is internally inconsistent with the path median query. The path median query explicitly adds \"the number of clusters in the path decomposition plus one\" because the vertices connecting consecutive clusters are not part of any cluster path, but the PWS implementation states that the cluster paths are \"disjoint and whose union forms the entire path\" and treats the cluster weight ranges as an ordered sequence covering the whole path. If the queried weight w falls in the gap occupied by such a connector vertex and that connector has weight less than w, the procedure returns the maximum of the lower cluster range rather than the connector vertex, which is the true predecessor. The output-sensitive spine merge in Section 4.2 uses PWS to identify exactly the node whose parent changes, so a wrong predecessor produces incorrect parent pointers and invalidates the charge of one PWS query per structural change. Consequently, Theorem 1.2 and the sequential part of Theorem 1.4 are not established as written. The query can likely be repaired by including connector vertices as singleton ranges, but that repair must be given explicitly.","section":"Section 4.1, Definition 4.1 and implementation"},{"comment":"The batch deletion algorithm is asserted correct because \"multiple parent changes to any node all result in the same value,\" but no proof of this confluence property is provided. For two deleted edges on the same root-to-leaf chain, a node's final parent is the first surviving ancestor after skipping both deleted edges; independent concurrent runs of the single-edge Delete procedure on the original dendrogram, each filtering to one side of its own cut, do not obviously compute this value, and the result can depend on the order in which writes to a shared parent pointer are applied. Since Theorem 1.5's batch deletion bound depends on running the single-deletion procedure concurrently for all deleted edges, this is a load-bearing correctness gap that needs either a formal argument or a redesigned batch procedure.","section":"Section 3.3, Batch Deletions"},{"comment":"The algorithms assume that the characteristic edges e*_u and e*_v, the minimum-rank edges incident to the relevant endpoints, can be identified without cost, but no data structure is specified for maintaining these values under edge deletions. If the deleted edge was the minimum-rank incident edge of one of its endpoints, the new minimum can be found by scanning the adjacency list in worst-case time proportional to the degree, which can be Theta(n) and would violate the stated O(h) and O(c log(1+n/c)) bounds. The paper should specify how these characteristic edges are maintained under the dynamic updates and account for the maintenance cost in Theorems 1.1 and 1.2. A per-vertex heap would likely suffice, but this needs to be stated.","section":"Section 3.1, Algorithm 2 and Section 4.2"}],"minor_comments":[{"comment":"The sentence \"As h >= log^2 n\" is false in general: a full binary dendrogram with n leaves has h >= ceil(log_2 n), not h >= log^2 n. The subsequent asymptotic accounting for the insertion algorithm works with h >= log n, so the inequality should be corrected.","section":"Section 3.1"},{"comment":"There are typos: \"PSW queries\" in Section 4.2 should read \"PWS queries,\" and \"resursion tree\" in Section 4.3 should read \"recursion tree.\"","section":"Section 4.2 and 4.3"},{"comment":"The statement that a path decomposition's cluster paths \"forms exactly the path between u and v\" should be reconciled with the connector-vertex accounting in Definition 4.2; as written, the two passages contradict each other.","section":"Section 2.4"},{"comment":"The proof should state whether \"height h\" counts internal nodes or edges on the spine, since the constructed star of h+1 vertices has an internal-node SLD path of h nodes and the merged tree has 2h+1 internal nodes; the lower bound argument is clear either way, but the presentation would benefit from consistent convention.","section":"Section 5, proof of Theorem 5.1"}],"recommendation":"major_revision","confidential_remarks":"The paper addresses a significant gap and the main ideas are promising, but the output-sensitive results currently rest on a PWS query that is inconsistent with the path median query, and the batch deletion correctness argument is missing. These are fixable with a careful revision: incorporate connector vertices into the path decomposition for PWS, give a formal confluence argument for batch deletions or redesign the algorithm, and specify the min-rank-edge maintenance. I would not reject the paper on these grounds, but the claims in Theorems 1.2, 1.4, and 1.5 should not be accepted in their current form."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things you should know. First, this is the first paper I've seen that explicitly maintains the single-linkage dendrogram under edge insertions and deletions, and the height-bounded machinery (Theorems 1.1, 1.3, 1.5) looks like a real step forward. Second, the output-sensitive section has a load-bearing bug: the path weight search query in Section 4.1 does not handle the vertices connecting consecutive path-decomposition clusters, so it can return the wrong predecessor. That undermines Theorems 1.2 and 1.4 as written.\n\nThe good parts are real. The problem is genuinely new; prior work stops at dynamic MSF and threshold queries. Using the spine-merge from Dhulipala et al. for insertions and framing deletion as unmerging a spine is clean. The parallel RC-tree extraction of spines and the batch star-merge are nice, and the worst-case O(log n) leaf updates for Cartesian trees improves on Demaine et al.'s amortized bound. The paper leans heavily on [19] and RC-tree papers, but those are peer-reviewed building blocks, not the target result, so there is no circularity.\n\nThe soft spots. The PWS issue is real. The path median query in the same section explicitly says the total path length must include \"the number of clusters plus one\" because connecting vertices are not part of any cluster path. The PWS query, by contrast, treats the cluster weight ranges as partitioning the whole path. If w falls into a gap, the procedure returns the max of the lower range or descends into the wrong cluster. In the spine merge, PWS must return exactly the node whose parent changes, so the c-charge collapses. The \"each node visited at most twice\" claim in Section 4.2 is asserted without formal accounting, and the gap vertices make it suspect. Also, the batch deletion correctness claim (\"multiple parent changes to any node all result in the same value\") is stated without proof; concurrent unmerges could interact. Finally, Section 3.1 says h >= log^2 n, which is false for balanced dendrograms. This one is minor because the O(log n) RC-tree update cost is absorbed for all h >= 1, so it just needs rewording.\n\nNet: the height-bounded and batch algorithms are likely correct and form a solid contribution. The output-sensitive results are not established as written. This paper deserves a serious referee, but the referee should push for a corrected PWS implementation and a real proof of the batch-deletion claim, or the output-sensitive theorems should be downgraded to conjectures. I'd take it for peer review, not desk reject.","headline":"First explicit fully-dynamic SLD maintenance with credible height-bounded bounds, but the output-sensitive section rests on a PWS query that, as written, skips connecting vertices and can return the wrong node.","tokens_in":25487,"tokens_out":5156,"would_cite":true,"duration_ms":47969,"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":"This paper gives the first fully-dynamic algorithms that maintain a single-linkage dendrogram explicitly, with update costs $O(h)$ for insertions, $O(h \\log(1+n/h))$ for deletions, and $O(c \\log(1+n/c))$ for output-sensitive insertions…","keywords":["single-linkage clustering","hierarchical agglomerative clustering","fully-dynamic algorithms","dendrogram maintenance","rake-compress trees","output-sensitive algorithms","parallel algorithms","minimum spanning forest"],"falsifier":"Run the output-sensitive insertion on a rake-compress tree representing a path-shaped dendrogram, issue the $c$ path weight search queries in increasing weight order, and count the total number of RC-tree nodes visited; any execution visiting more than $O(c \\log(1+n/c))$ nodes would refute the charging claim in Section 4.2. Alternatively, construct a single increasing-weight path whose RC-tree path decomposition contains a cluster weight range that overlaps the threshold without containing it, and check whether the PWS query still returns the correct node in $O(\\log n)$ time; a wrong answer or a linear scan would falsify the query implementation.","tokens_in":24516,"feed_emoji":"🌳","tokens_out":9948,"duration_ms":87182,"temperature":0.7,"pith_summary":"Single-linkage clustering builds a dendrogram—a binary tree recording which clusters merge and at what edge weight—and this paper asks whether that tree can be maintained cheaply when the underlying data changes through edge insertions and deletions. Prior dynamic work maintained only a minimum spanning forest, which answers \"are these points in the same cluster at threshold $\\tau$\" queries but does not explicitly give the dendrogram. The paper claims that the dendrogram can be updated in $O(h)$ time per insertion and $O(h \\log(1+n/h))$ per deletion, where $h$ is the height of the dendrogram, and that insertions can be processed in $O(c \\log(1+n/c))$ time, where $c$ is the number of parent-pointer changes the update causes. It also gives parallel and batch-parallel versions with polylogarithmic depth and work equal to or near these sequential bounds. Since $h \\leq n-1$, this makes every single update asymptotically cheaper than recomputing the dendrogram from scratch, and much cheaper when the dendrogram is shallow.","feed_headline":"Single-linkage tree updates beat recomputing from scratch","feed_subtitle":"New dynamic algorithms keep cluster dendrograms current in time set by tree height, with parallel and batch speedups.","key_machinery":"The spine of an edge in a dendrogram is the node-to-root path starting at that edge's node, and along any spine edge ranks increase monotonically; merging two dendrograms therefore reduces to merging two sorted spines. The update algorithms maintain the dendrogram together with a rake-compress tree—a dynamic tree built from repeated rounds of contraction, supporting links, cuts, connectivity queries, and path decompositions in $O(\\log n)$ time. On top of that base, the paper introduces path weight search (PWS), which returns the maximum-weight node on an increasing-weight path below a threshold, and path median queries, so a merge can jump directly to the next node whose parent pointer changes instead of walking the whole spine. The mechanism that makes the output-sensitive bound work is charging: each PWS query is charged to a distinct parent-pointer change, queries are issued in increasing weight order, and the downward search paths are arranged so that each RC-tree node is visited at most twice, bounding the total by the union of $c$ rootward paths.","core_discovery":"On the paper's own terms, the central discovery is that an update to the underlying forest, even though it can rearrange the whole dendrogram in the worst case, only ever forces changes along two node-to-root paths: the spines of the minimum-rank edges incident to the two endpoints. Reusing the spine-merge primitive from static dendrogram computation makes an insertion a merge of two sorted lists of length at most $h$, and a deletion an unmerge of one spine guided by connectivity queries that decide which side of the cut each node belongs to. The paper then shows that maintaining a rake-compress tree over the dendrogram, together with new path weight search queries, lets an insertion find exactly the parent pointers that must change, achieving $O(c \\log(1+n/c))$ time. The same machinery yields parallel updates whose work matches the sequential bounds and whose depth is polylogarithmic, and batch updates that process $k$ insertions or deletions in $O(kh \\log(1+n/(kh)))$ work with polylogarithmic depth. These are, to the authors' knowledge, the first explicit dendrogram maintenance algorithms that are asymptotically faster than static recomputation.","pith_inferences":["A symmetric unmerge of the alternating PWS merge likely yields an output-sensitive deletion algorithm; the paper leaves deletions only in the height-bounded $O(h \\log(1+n/h))$ form, so this is a natural next step rather than a claim the paper makes.","The output-sensitive charging argument depends only on parent-pointer changes and rootward search paths, so if the PWS implementation is validated, the same bound should transfer to any explicit binary-tree representation of a dendrogram, not just forests.","A concrete test of the unproven accounting step would be to instrument an RC tree and count node visits under increasing-weight PWS queries on adversarially shaped dendrograms; the \"each node visited at most twice\" claim should be checked before implementation effort is invested.","The Cartesian-tree equivalence suggests an unstated consequence: dynamic SLD maintenance also yields dynamic range-minimum-query structures under point updates, since the Cartesian tree of an array is exactly the SLD of the corresponding path graph."],"forward_implications":["Every single edge update is asymptotically cheaper than static recomputation: the static optimum is $\\Theta(n \\log h)$, while insertions cost $O(h)$ and deletions cost $O(h \\log(1+n/h))$, and since $h \\leq n-1$ the dynamic cost is never larger.","For shallow dendrograms of height $O(\\log n)$, insertions cost $O(\\log n)$ and deletions cost $O(\\log^2 n)$, regimes where static recomputation would be wasteful.","Combined with an existing fully-dynamic minimum spanning forest algorithm, the routines give an end-to-end fully-dynamic single-linkage clustering pipeline; combined with a batch-dynamic MSF algorithm, they give a batch-parallel pipeline with polylogarithmic depth.","Insertions are near-optimal in an output-sensitive sense: the $O(c \\log(1+n/c))$ bound is within a logarithmic factor of the $\\Omega(c)$ lower bound, and when only a constant number of parent pointers change the update costs $O(\\log n)$, matching an amortized lower bound.","Because the SLD of a path graph is a Cartesian tree, the algorithms supply worst-case $O(\\log n)$ leaf insertions and deletions in Cartesian trees, improving on prior amortized bounds, and enable cluster-report and cluster-size queries that a bare minimum spanning forest cannot answer in low depth."],"supporting_citations":[{"why":"Supplies the spine-merge routine and the $O(n \\log h)$ static SLD algorithm whose cost every dynamic update in the paper is designed to beat; the insertion algorithm calls this merge directly.","marker":"[19]"},{"why":"Introduces rake-compress trees, the dynamic tree structure whose links, cuts, connectivity queries, and path decompositions carry all update algorithms.","marker":"[3, 4]"},{"why":"Provides the detailed mechanics of path decompositions in RC trees that the parallel spine extraction and batch updates rely on.","marker":"[5]"},{"why":"Gives deterministic batch-parallel RC-tree operations whose work and depth bounds are used in the parallel and batch cost analyses.","marker":"[7]"},{"why":"Prior batch-dynamic minimum spanning forest algorithm that motivated the gap; it supported only threshold queries, and the new batch algorithms combine with it for end-to-end dynamic clustering.","marker":"[48]"},{"why":"Fully-dynamic minimum spanning forest algorithm whose combination with the new routines yields a fully-dynamic single-linkage clustering solution with amortized update cost.","marker":"[33]"},{"why":"Prior dynamic Cartesian tree algorithms that the paper's worst-case $O(\\log n)$ leaf-update results improve on, via the SLD/Cartesian tree equivalence.","marker":"[16]"},{"why":"Establishes the reduction of single-linkage clustering to minimum spanning forest computation that justifies modeling the input as a dynamic forest.","marker":"[29]"}],"fun_headline_variants":["First dynamic SLD updates faster than recompute","Dendrogram updates beat from-scratch recomputation","Work-efficient parallel updates for dendrograms","Dynamic dendrogram maintenance in O(h) time","Outpace static recompute: new dynamic SLD algorithms"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The results would collapse if the new path weight search and path median queries cannot actually be answered in $O(\\log n)$ time per query, or if the union of the $c$ search paths in the rake-compress tree contains more than $O(c \\log(1+n/c))$ nodes—the paper sketches that implementation in Section 4.1 and asserts the per-node-visit accounting without giving a formal charge.","fun_headline_variants_meta":{"raw":{"variants":["First dynamic SLD updates faster than recompute","Dendrogram updates beat from-scratch recomputation","Work-efficient parallel updates for dendrograms","Dynamic dendrogram maintenance in O(h) time","Outpace static recompute: new dynamic SLD algorithms"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000334,"raw_usage":{"total_tokens":1956,"prompt_tokens":1151,"completion_tokens":805,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":767,"completion_tokens_details":{"reasoning_tokens":731}},"tokens_in":767,"tokens_out":805,"duration_ms":8079,"temperature":1.0,"reasoning_tokens":731,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T18:50:57.778232+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the output-sensitive insertion on a rake-compress tree representing a path-shaped dendrogram, issue the $c$ path weight search queries in increasing weight order, and count the total number of RC-tree nodes visited; any execution visiting more than $O(c \\log(1+n/c))$ nodes would refute the charging claim in Section 4.2. Alternatively, construct a single increasing-weight path whose RC-tree path decomposition contains a cluster weight range that overlaps the threshold without containing it, and check whether the PWS query still returns the correct node in $O(\\log n)$ time; a wrong answer or a linear scan would falsify the query implementation.","supporting_citations":[{"cited_title":"Gowda, and Yan Gu","cited_arxiv_id":null,"evidence_quote":"Supplies the spine-merge routine and the $O(n \\log h)$ static SLD algorithm whose cost every dynamic update in the paper is designed to beat; the insertion algorithm calls this merge directly."},{"cited_title":"2023.Parallel Batch-Dynamic Algorithms Dynamic Trees, Graphs, and Self-Adjusting Computation","cited_arxiv_id":null,"evidence_quote":"Provides the detailed mechanics of path decompositions in RC trees that the parallel spine extraction and batch updates rely on."},{"cited_title":"Blelloch","cited_arxiv_id":null,"evidence_quote":"Gives deterministic batch-parallel RC-tree operations whose work and depth bounds are used in the parallel and batch cost analyses."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Prior batch-dynamic minimum spanning forest algorithm that motivated the gap; it supported only threshold queries, and the new batch algorithms combine with it for end-to-end dynamic clustering."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Fully-dynamic minimum spanning forest algorithm whose combination with the new routines yields a fully-dynamic single-linkage clustering solution with amortized update cost."},{"cited_title":"Demaine, Gad M","cited_arxiv_id":null,"evidence_quote":"Prior dynamic Cartesian tree algorithms that the paper's worst-case $O(\\log n)$ leaf-update results improve on, via the SLD/Cartesian tree equivalence."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes the reduction of single-linkage clustering to minimum spanning forest computation that justifies modeling the input as a dynamic forest."}],"review_version":1}