2026-08-25T17:34:08Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27222 2026-08-25T13:18:18Z ddc:004 open_access

Sublinear Algorithms for Estimating Single-Linkage Clustering Costs Peng, Pan Sohler, Christian Xu, Yi Sublinear Algorithms Single-linkage Clustering Approximation Algorithms Minimum Spanning Tree Single-linkage clustering (SLC) is a fundamental method for hierarchical data analysis. In the distance setting, a k-clustering produced by SLC can be obtained by computing a minimum spanning tree (MST) and deleting its k-1 heaviest edges. This naturally induces a cost profile for the SLC hierarchy: for each k ∈ [n], we define cost_k to be the weight of the resulting k-component spanning forest, equivalently, the minimum total weight of any spanning forest with exactly k connected components. The corresponding SLC cost profile is (cost_1,…,cost_n), and the scalar quantity cost(G) = ∑_{k=1}^n cost_k is the area under this profile. We study the problem of approximating these quantities in sublinear time. We assume that the input is a weighted graph G of average degree d with edge weights in {1,… ,W}, accessed through adjacency-list queries; missing edges are treated as having infinite distance. Our main result is a sampling-based algorithm that outputs a succinct sketch of the entire SLC cost profile in the distance setting. The algorithm runs in Õ(d√W/ε³) time and returns a sketch from which one can derive estimates (cost̂_1,…,cost̂_n) satisfying ∑_{k=1}^n |cost̂_k-cost_k| ≤ ε cost(G). Thus, we obtain an 𝓁₁ approximation to the full profile whose error is at most an ε-fraction of the area under the true profile. In particular, this yields a (1±ε)-approximation to cost(G) within the same running time. We also prove a nearly matching lower bound of Ω(d√W/ε²) queries for estimating cost(G). We further extend our results to the similarity setting, where SLC is defined via a maximum spanning tree. In this case, we obtain algorithms with running time Õ(dW/ε³) for both the profile and the total cost, together with a nearly matching lower bound of Ω(dW/ε²) queries. These bounds reveal a genuine separation between the distance and similarity settings. Finally, we extend our algorithms to metric spaces, where we obtain Õ(n/ε⁷)-query algorithms for both distance and similarity metrics, and we complement our theory with experimental validation. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Pan Peng and Christian Sohler and Yi Xu 2026 Is Part Of LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2026.86 urn:nbn:de:0030-drops-272227 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.86 eng https://creativecommons.org/licenses/by/4.0/legalcode