2026-07-20T11:16:38Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23480 2025-10-02T12:56:23Z ddc:004 open_access

Approximating Dasgupta Cost in Sublinear Time from a Few Random Seeds Kapralov, Michael Kumar, Akash Lattanzi, Silvio Mousavifar, Aida Wrzos-Kaminska, Weronika Sublinear algorithms Hierarchical Clustering Dasgupta’s Cost Testing graph cluster structure has been a central object of study in property testing since the foundational work of Goldreich and Ron [STOC'96] on expansion testing, i.e. the problem of distinguishing between a single cluster (an expander) and a graph that is far from a single cluster. More generally, a (k, ε)-clusterable graph G is a graph whose vertex set admits a partition into k induced expanders, each with outer conductance bounded by ε. A recent line of work initiated by Czumaj, Peng and Sohler [STOC'15] has shown how to test whether a graph is close to (k, ε)-clusterable, and to locally determine which cluster a given vertex belongs to with misclassification rate ≈ ε, but no sublinear time algorithms for learning the structure of inter-cluster connections are known. As a simple example, can one locally distinguish between the "cluster graph" forming a line and a clique? In this paper, we consider the problem of testing the hierarchical cluster structure of (k, ε)-clusterable graphs in sublinear time. Our measure of hierarchical clusterability is the well-established Dasgupta cost, and our main result is an algorithm that approximates Dasgupta cost of a (k, ε)-clusterable graph in sublinear time, using a small number of randomly chosen seed vertices for which cluster labels are known. Our main result is an O(√{log k}) approximation to Dasgupta cost of G in ≈ n^{1/2+O(ε)} time using ≈ n^{1/3} seeds, effectively giving a sublinear time simulation of the algorithm of Charikar and Chatziafratis [SODA'17] on clusterable graphs. To the best of our knowledge, ours is the first result on approximating the hierarchical clustering properties of such graphs in sublinear time. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Michael Kapralov and Akash Kumar and Silvio Lattanzi and Aida Mousavifar and Weronika Wrzos-Kaminska 2025 Is Part Of LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2025.103 urn:nbn:de:0030-drops-234804 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.103 eng https://creativecommons.org/licenses/by/4.0/legalcode