2026-07-20T11:15:24Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20161 2024-07-02T07:52:49Z ddc:004 open_access

It’s Hard to HAC Average Linkage! Bateni, MohammadHossein Dhulipala, Laxman Gowda, Kishen N. Hershkowitz, D. Ellis Jayaram, Rajesh Łącki, Jakub Clustering Hierarchical Graph Clustering HAC Fine-Grained Complexity Parallel Algorithms CC Average linkage Hierarchical Agglomerative Clustering (HAC) is an extensively studied and applied method for hierarchical clustering. Recent applications to massive datasets have driven significant interest in near-linear-time and efficient parallel algorithms for average linkage HAC. We provide hardness results that rule out such algorithms. On the sequential side, we establish a runtime lower bound of n^{3/2-ε} on n node graphs for sequential combinatorial algorithms under standard fine-grained complexity assumptions. This essentially matches the best-known running time for average linkage HAC. On the parallel side, we prove that average linkage HAC likely cannot be parallelized even on simple graphs by showing that it is CC-hard on trees of diameter 4. On the possibility side, we demonstrate that average linkage HAC can be efficiently parallelized (i.e., it is in NC) on paths and can be solved in near-linear time when the height of the output cluster hierarchy is small. Schloss Dagstuhl – Leibniz-Zentrum für Informatik MohammadHossein Bateni and Laxman Dhulipala and Kishen N. Gowda and D. Ellis Hershkowitz and Rajesh Jayaram and Jakub Łącki 2024 Is Part Of LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2024.18 urn:nbn:de:0030-drops-201613 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.18 eng https://creativecommons.org/licenses/by/4.0/legalcode