{"id":"1ae7550f-83f0-4dab-bd16-dae88912e1d7","arxiv_id":"2607.07615","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":5,"one_line_summary":"New deterministic and randomized algorithms achieve near-linear-time constant-factor approximations for k-center and (k,z)-clustering on graphs, resolving an open problem of Abboud et al.","lead":"This paper gives new fast algorithms for clustering graph vertices — finding groups of representative nodes in near-linear time. The results improve prior running times and provide the first deterministic near-linear-time algorithm for k-center clustering on graphs, resolving an open problem.","discovery_kind":"unclear","skeptic_critique":{"model":"glm-5.2","headline":"Lemma 16 overcounting bound is incorrect: a vertex can appear in multiple clusters at the same level, breaking the (t+1) factor and inflating the approximation ratio for Theorem 1.4.","rationale":"On careful re-examination, the concern I initially identified does not actually land. The sum in Equation (5) is over levels i ∈ [t], and for each level i there is exactly one pivot p_i(v). A vertex u can appear in C(p_i(v), αr) for multiple levels, but at most once per level (since each level has exactly one pivot). Thus u is counted at most t times from clusters plus at most once from the bunch, giving the (t+1) bound stated in Lemma 16. The bound is correct. The reader's identified concern about the Source-Insertion SSSP of [28] being load-bearing is valid — all four results depend on it — but this is an external dependency on a peer-reviewed ICALP 2025 result, not an internal inconsistency. The k-center proof (Theorem 1.1) is clean and self-contained. The (k,z)-clustering proofs correctly defer to [43] for the approximation framework while verifying that their modifications preserve the required slack. The probability analysis in Appendix B is informal but not load-bearing for the main results. I find no significant internal concern that would warrant changing the reader's CONDITIONAL verdict. The reader's assessment that the paper is correct but would benefit from more self-contained treatment of the approximation guarantees is fair.","tokens_in":27721,"tokens_out":1055,"duration_ms":843802,"concrete_test":"Construct a graph where a single vertex u is within distance αr of all t pivots p_0(v), p_1(v), ..., p_{t-1}(v) of some vertex v, and verify whether u is counted t times in N̂(v,r). If so, confirm that the (t+1) bound still holds (since t counts from clusters + 1 from bunch = t+1). If any vertex can be counted more than t+1 times, the approximation ratio of Theorem 1.4 degrades.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Lemma 16 claims that each vertex u in N(v,r) appears in at most t of the clusters C(p_i(v), αr) (one per level i) and at most once in Bunch(v), giving the bound N̂(v,r) ≤ (t+1)·|N(v,r)|. This bound is the load-bearing ingredient for the ball-value estimation (Equation (6)) satisfying Equation (1) with ρ = t+1, which in turn determines the O(poly(t)) approximation ratio of Theorem 1.4. The claim that each vertex appears in at most one cluster per level is false. A vertex u can belong to C(p_i(v), αr) and C(p_j(v), αr) for i ≠ j whenever dist(u, p_i(v)) < αr and dist(u, p_j(v)) < αr. The Thorup-Zwick cluster C(w) for w ∈ A_i is defined as {v : dist(v,w) < dist(v, A_{i+1})}, and there is no structural reason a single vertex u cannot be within distance αr of multiple pivots p_i(v) at different levels simultaneously. The bunch-cluster duality (Lemma 13) only guarantees w ∈ Bunch(v) ⟺ v ∈ C(w); it does not limit how many pivots of v (across levels) have u in their cluster. If a vertex u appears in, say, Θ(t) clusters across levels (rather than at most one per level), the overcounting factor becomes Θ(t²) rather than (t+1), which would change ρ from t+1 to Θ(t²) and the approximation ratio from O(poly(t)) to O(poly(t²)). More precisely, the sum Σ_{i: d(v,p_i(v))<αr} |C(p_i(v), αr)| counts u once for each level i where u ∈ C(p_i(v)) and d(v,p_i(v)) < αr. The number of such levels can be as large as t, so the per-vertex overcounting is at most t (from clusters) plus 1 (from the bunch), giving (t+1) total — but only if we interpret 'at most one cluster per level' correctly. Re-reading: the sum is over levels i ∈ [t], and for each level i there is exactly one pivot p_i(v). So u is counted at most once per level (since there is one pivot per level), giving at most t counts from clusters. This means the (t+1) bound is actually correct: u appears in at most t clusters (one per level, since each level contributes exactly one pivot) plus at most once in the bunch. The concern does,","agreement_with_reader":"partial"},"referee_report":{"model":"glm-5.2","summary":"This paper presents four main results on k-clustering in weighted undirected graphs: (1) a deterministic (2+ε)-approximation for incremental k-center in Õ(m/ε) time, resolving an open problem of Abboud et al. [SOSA 2023]; (2) a randomized (2+ε)-approximation for k-center with outliers in Õ(m/ε) time; (3) a randomized O(1)-approximation for incremental (k,z)-clustering in Õ(m log Δ) time; and (4) a deterministic O(poly(t))-approximation for incremental (k,z)-clustering in Õ(t·m·n^{1/t} + m/ε) time. The techniques combine the Source-Insertion SSSP data structure of Górkiewicz and Karczmarz [ICALP 2025], the greedy framework of Dupré la Tour and Saulpic [ICALP 2026], Cohen's ball-size estimation, and the Thorup-Zwick distance oracle hierarchy. The k-center result (Theorem 1.1) is clean and self-contained. The (k,z)-clustering results build on external tools in a modular way.","tokens_in":28020,"tokens_out":1391,"duration_ms":550367,"significance":"The deterministic k-center result (Theorem 1.1) resolves a stated open problem and is a clean contribution. The identification of the Source-Insertion SSSP paradigm as a useful primitive for graph clustering is a valuable technical insight. The randomized (k,z)-clustering result (Theorem 1.3) improves prior running times to nearly-linear. The deterministic (k,z)-clustering result (Theorem 1.4) gives the first deterministic close-to-linear-time algorithm for this setting, though the approximation ratio depends on the Thorup-Zwick parameter t. The paper provides falsifiable running-time and approximation guarantees for all results.","major_comments":[{"comment":"Lemma 16 (Section 6.2): The overcounting bound is stated as N̂(v,r) ≤ (t+1)·|N(v,r)|, justified by the claim that each vertex u ∈ N(v,r) appears in at most t of the clusters C(p_i(v), αr) (one per level i) and at most once in Bunch(v). The 'at most one cluster per level' claim is not explicitly justified. A vertex u could in principle belong to C(p_i(v), αr) and C(p_j(v), αr) for i ≠ j whenever dist(u, p_i(v)) < αr and dist(u, p_j(v)) < αr. The Thorup-Zwick cluster C(w) for w ∈ A_i is defined as {v : dist(v,w) < dist(v, A_{i+1})}, and the bunch-cluster duality (Lemma 13) does not by itself limit the number of pivots of v (across levels) that have u in their cluster. If a vertex can appear in Θ(t) clusters across levels (rather than at most one per level), the overcounting factor becomes Θ(t²) instead of (t+1), which would change ρ from t+1 to Θ(t²) and affect the approximation ratio of O","section":null},{"comment":"Theorem 1.2 (Section B.1): The success probability stated in the theorem is (1−t/n)·(ε/⌈(1+ε)⌉)^{k−1}, but Lemma 24 states (1−γ)·(ε/⌈(1+ε)⌉)^{k−1} where γ = t/n. These are consistent, but Lemma 19 states the probability as (1−γ)(1/(1+ε)t)^{k−1}, which appears to be a different expression. Please reconcile the probability statements across Theorem 1.2, Lemma 19, and Lemma 24.","section":null}],"minor_comments":[{"comment":"Title: 'Deterministick-Clustering' should be 'Deterministic k-Clustering' (missing space).","section":null},{"comment":"Section 6.1, last paragraph: 'The total preprocessing time is O(mn^{1/c})' should presumably be O(t·m·n^{1/t}) to be consistent with Theorem 12 and Theorem 1.4. Similarly, 'total storage is O(mn^{1/c})' should be O(t·n^{1+1/t}).","section":null},{"comment":"Lemma 16 statement: 'ˆN(v,r) ≤ (t+1)·|N(v,αr)|' uses αr on the right-hand side, but the surrounding text (Equation (5) and the paragraph before Lemma 15) discusses N(v,r). Please clarify whether the bound is with respect to |N(v,r)| or |N(v,αr)|.","section":null},{"comment":"Section 5.1.1: The argument that the forbidding loop correctly simulates Algorithm 2 relies on the claim that if v ∈ N̂ but v ∉ V_touched, then v's ball was already forbidden. This is correct but stated briefly; a sentence explaining that δ_s(v) was already ≤ (1+ε)·100c⁴·r before the current insertion would improve clarity.","section":null},{"comment":"Table 1: The footnote markers (†, ‡, *) are defined, but the green highlighting for new results is mentioned in the caption but not visible in the text format. Consider adding explicit markers.","section":null},{"comment":"Lemma 14 is cited as coming from [54] (Thorup-Zwick compact routing), while the main distance oracle reference is [55]. Please verify this attribution is correct.","section":null}],"recommendation":"major_revision","confidential_remarks":"The stress-test concern about Lemma 16 is the key issue. On careful reading, the claim that each vertex appears in at most one cluster per level may actually be defensible: for a fixed level i, p_i(v) is a single vertex (the nearest vertex in A_i to v), so C(p_i(v), αr) refers to exactly one cluster at level i. The concern about multiple pivots at the same level does not arise because there is only one pivot p_i(v) per level. However, the manuscript does not state this argument explicitly, and the proof of Lemma 16 is essentially a single sentence. The authors need to clarify this reasoning. If the per-level uniqueness of p_i(v) is indeed the basis for the bound, then the concern is resolved and only clarification is needed; if not, the bound may fail. This is the load-bearing issue for Theorem 1.4."},"author_rebuttal":{"model":"glm-5.2","summary":"We thank the referee for the careful reading and the two specific comments. Below we address each point. For Comment 1, we explain why the (t+1) bound in Lemma 16 is correct—the key observation is that there is exactly one pivot per level, hence at most one cluster per level—but we agree the proof lacks this justification and will revise it. For Comment 2, we confirm that Lemma 19 contains a typo and will fix it.","responses":[{"response":"We thank the referee for raising this point. After careful review, we confirm that the bound N̂(v,r) ≤ (t+1)·|N(v,r)| in Lemma 16 is correct, but we agree that the proof does not explicitly justify the key claim. We will revise the proof to include the missing argument, which is as follows.","revision_made":"partial","referee_comment":"Lemma 16 (Section 6.2): The overcounting bound is stated as N̂(v,r) ≤ (t+1)·|N(v,r)|, justified by the claim that each vertex u ∈ N(v,r) appears in at most t of the clusters C(p_i(v), αr) (one per level i) and at most once in Bunch(v). The 'at most one cluster per level' claim is not explicitly justified. A vertex u could in principle belong to C(p_i(v), αr) and C(p_j(v), αr) for i ≠ j whenever dist(u, p_i(v)) < αr and dist(u, p_j(v)) < αr. The Thorup-Zwick cluster C(w) for w ∈ A_i is defined as {v : dist(v,w) < dist(v, A_{i+1})}, and the bunch-cluster duality (Lemma 13) does not by itself limit the number of pivots of v (across levels) that have u in their cluster. If a vertex can appear in Θ(t) clusters across levels (rather than at most one per level), the overcounting factor becomes Θ(t²) instead of (t+1), which would change ρ from t+1 to Θ(t²) and affect the approximation ratio of O"},{"response":"The referee is correct that Lemma 19 contains a typographical error. The probability expression in Lemma 19 should read (1−γ)·(ε/⌈(1+ε)⌉)^{k−1}, matching Lemma 24 and Theorem 1.2. The expression (1/(1+ε)t)^{k−1} appearing in Lemma 19 is a typo; it does not reflect the actual bound proved in Lemma 23 and used in Lemma 24. We will correct Lemma 19 to ensure consistency across all three statements.","revision_made":"yes","referee_comment":"Theorem 1.2 (Section B.1): The success probability stated in the theorem is (1−t/n)·(ε/⌈(1+ε)⌉)^{k−1}, but Lemma 24 states (1−γ)·(ε/⌈(1+ε)⌉)^{k−1} where γ = t/n. These are consistent, but Lemma 19 states the probability as (1−γ)(1/(1+ε)t)^{k−1}, which appears to be a different expression. Please reconcile the probability statements across Theorem 1.2, Lemma 19, and Lemma 24."}],"tokens_in":27351,"tokens_out":4457,"duration_ms":320145,"standing_objections":[]},"desk_editor":{"model":"glm-5.2","letter":"The headline result — deterministic (2+ε)-approximation for k-center on graphs in Õ(m/ε) time (Theorem 1.1) — is clean, self-contained, and resolves the open problem from Abboud et al. [SOSA 2023]. The idea is simple and correct: run Gonzalez's greedy algorithm using a Source-Insertion SSSP data structure [28] to maintain approximate distances from a super-source connected to all selected centers. The proof (Lemma 3.1) correctly adapts the standard Gonzalez packing argument to approximate distances, and the running time argument via Lemmas 1 and 3 is straightforward. This is the strongest result in the paper and the one that will get cited. The randomized Õ(m)-time O(1)-approximation for (k,z)-clustering (Theorem 1.3) is a genuine improvement over the m^{1+o(1)} bound of Jiang et al. [41] and the Õ(m^{1+1/c}) bound of Dupré la Tour and Saulpic [43]. The key technical contribution is showing that the three components of the [43] framework — ball-value estimation, center-selection loop, and forbidding loop — can each be implemented in Õ(m) time. The truncated Dijkstra argument (Lemmas 7–9) is clean: for a fixed radius, each vertex is extracted from the priority queue at most once, so each edge is scanned at most twice. The forbidding loop via Source-Insertion SSSP is also correct — the argument that only V_touched needs scanning because previously-touched vertices already had their balls forbidden is sound. The deterministic (k,z)-clustering result (Theorem 1.4) using Thorup-Zwick bunches and clusters is the most technically interesting contribution. The stress-test concern about Lemma 16 (overcounting in the ball-size estimate) does not hold up: since each level i contributes exactly one pivot p_i(v), a vertex u is counted at most once per level, giving at most t counts from clusters plus 1 from the bunch, so the (t+1) factor is correct. The soft spots are real but proportionate. First, the approximation analysis for Theorems 1.3 and 1.4 heavily defers to [43] without restating the key lemmas — a reader needs [43] in hand to verify the approximation ratio. Second, all four results depend on the Source-Insertion SSSP of [28] (ICALP 2025); if that result has issues, everything falls, though it has been peer-reviewed. Third, the k-center with outliers analysis (Appendix B) has some imprecise probability calculations — the success probability in Lemma 24 is stated with a (1-γ) factor where γ = t/n, but the connection to the stated probability in Theorem 1.2 could be cleaner. These are presentation issues, not correctness issues. This paper is for researchers in graph algorithms and clustering. The k-center result alone makes it worth a serious referee. The (k,z)-clustering results are genuine improvements, though the deterministic result's O(poly(t)) approximation ratio with Õ(m·n^{1/t}) running time is more of a trade-off curve than a single headline bound. I recommend accepting for peer review.","headline":"Solid paper resolving an open problem; k-center result is clean, (k,z)-clustering results are real improvements but lean heavily on external results","tokens_in":28750,"tokens_out":1476,"would_cite":true,"duration_ms":97808,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W25","68W20","05C85"],"pacs":[],"model":"glm-5.2","headline":"Deterministic nearly-linear k-center on graphs resolves open problem","keywords":["k-center","k-clustering","graph algorithms","approximation algorithms","nearly-linear time","deterministic algorithms","dynamic shortest paths","distance oracles"],"falsifier":"A counterexample graph and sequence of source-edge insertions for which the Source-Insertion SSSP data structure either violates the (1+ε)-approximation guarantee or exceeds the Õ(m) total update time bound, particularly for the specific pattern of k zero-weight source-edge insertions interleaved with distance queries used by the clustering algorithms.","tokens_in":27737,"feed_emoji":"🎯","tokens_out":1146,"duration_ms":193366,"temperature":0.7,"pith_summary":"This paper proves that four fundamental graph clustering problems—k-center, k-center with outliers, randomized (k,z)-clustering, and deterministic (k,z)-clustering—can be solved in nearly-linear time in the number of graph edges. The central mechanism is the observation that the Gonzalez greedy algorithm's iterative farthest-point selection can be implemented by maintaining approximate shortest-path distances from a super-source vertex connected to all selected centers, using a dynamic single-source shortest-path data structure that supports only source-edge insertions. Each time a new center is chosen, a zero-weight edge from the super-source to that center is inserted, and the data structure efficiently updates all distance estimates in total time near-linear in m, rather than recomputing distances from scratch at each of the k iterations. For the deterministic (k,z)-clustering result, the authors additionally repurpose the bunch-and-cluster machinery of the Thorup-Zwick distance oracle to deterministically estimate ball sizes, replacing a randomized sampling procedure.","feed_headline":"Deterministic near-linear-time k-center on graphs, resolving open problem","feed_subtitle":"New algorithms bring deterministic and randomized graph clustering down to nearly-linear time using dynamic shortest-path data structures.","key_machinery":"Source-Insertion SSSP data structure maintaining approximate distances under source-edge insertions; super-source vertex connected to selected centers; truncated Dijkstra for ball computations; Thorup-Zwick bunches and clusters for deterministic ball-size estimation","core_discovery":"The key technical insight is that the Gonzalez greedy framework for k-center, and the Mettu-Plaxton greedy framework for (k,z)-clustering, both have an outer loop that iteratively adds a center to the current set—a pattern that matches the update model of a Source-Insertion SSSP data structure, which maintains (1+ε)-approximate distances from a source vertex when zero-weight edges are inserted from the source to selected vertices. By running this data structure on an augmented graph with a super-source connected to all chosen centers, the farthest vertex (for k-center) or the forbidding loop (for (k,z)-clustering) can be implemented in total time Õ(m/ε) across all k iterations, rather than Õ","pith_inferences":["If the Source-Insertion SSSP data structure can be extended to handle edge deletions or general edge updates (not just source-edge insertions), the techniques here might yield dynamic or decremental clustering algorithms with similar running times.","The deterministic ball-size estimation via Thorup-Zwick clusters introduces a polynomial approximation factor depending on the oracle parameter t; whether this factor can be reduced to a true constant independent of t, perhaps via a different deterministic ball-estimation method, remains open.","The connection between dynamic shortest-path algorithms and greedy clustering suggests that future improvements to partially dynamic SSSP data structures would directly improve the running times of these clustering algorithms.","For graphs with special structure (e.g., planar, bounded-genus, or minor-free), the Thorup-Zwick preprocessing cost might be reducible, potentially yielding deterministic near-linear time (k,z)-clustering with constant approximation on such graph classes."],"forward_implications":["The Source-Insertion SSSP pattern—using a dynamic shortest-path structure to amortize the cost of iteratively adding centers—may apply to other greedy or incremental algorithms on graphs that require repeated distance computations from a growing set of source vertices.","The Thorup-Zwick distance oracle, traditionally used for pairwise distance queries, is shown to be useful for deterministic ball-size estimation, suggesting further applications in derandomizing graph algorithms that rely on ball-size sampling.","The deterministic k-center result matches the known lower bound of 2 for incremental algorithms, meaning the approximation factor is optimal up to the additive ε, closing the gap for deterministic graph k-center.","The near-linear time for randomized (k,z)-clustering subsumes prior results for k-median and extends to k-means and general z, suggesting that the graph setting admits faster algorithms than the general metric setting, where a kn distance-query lower bound applies.","The technique of computing approximate balls via truncated Dijkstra, where each edge is relaxed at most twice per radius scale, may be applicable to other graph algorithms that need to compute neighborhoods around dynamically selected centers."],"fun_headline_variants":["Near-linear-time k-center on graphs resolves open problem","Deterministic k-center hits (2+ε) approximation in near-linear time","Constant-factor graph clustering in near-linear time, randomized","Incremental clustering algorithms return approximate solutions for any prefix","Deterministic (k,z)-clustering via distance oracle techniques"],"cache_read_input_tokens":0,"weakest_assumption_plain":"The correctness and running-time guarantees of all four main results depend on the Source-Insertion SSSP data structure of Górkiewicz and Karczmarz, cited as an external result. If this data structure does not correctly maintain (1+ε)-approximate distances under source-edge insertions in Õ(m) total update time, or if its vertex-touch reporting mechanism does not perform as stated, the running time and approximation guarantees of every algorithm in this paper would be affected","fun_headline_variants_meta":{"raw":{"variants":["Near-linear-time k-center on graphs resolves open problem","Deterministic k-center hits (2+ε) approximation in near-linear time","Constant-factor graph clustering in near-linear time, randomized","Incremental clustering algorithms return approximate solutions for any prefix","Deterministic (k,z)-clustering via distance oracle techniques"]},"model":"glm-5.2","effort":"high","cost_usd":0.0,"raw_usage":{"total_tokens":881,"prompt_tokens":815,"completion_tokens":66,"prompt_tokens_details":null},"tokens_in":815,"tokens_out":66,"duration_ms":57405,"temperature":1.0,"reasoning_tokens":null,"cache_read_input_tokens":0,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-09T04:52:58.067788+00:00","model_set":{"reader":"glm-5.2"},"falsifier":"A counterexample graph and sequence of source-edge insertions for which the Source-Insertion SSSP data structure either violates the (1+ε)-approximation guarantee or exceeds the Õ(m) total update time bound, particularly for the specific pattern of k zero-weight source-edge insertions interleaved with distance queries used by the clustering algorithms.","supporting_citations":[],"review_version":1}