2026-09-21T02:53:46Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27271 2026-09-05T20:17:26Z ddc:004 open_access

New Algorithms and Hardness Results for Connected Clustering Eube, Jan Röglin, Heiko Clustering Connectivity constraints Approximation algorithms Hardness of approximation Connected clustering denotes a family of constrained clustering problems in which we are given a distance metric and an undirected connectivity graph G that can be completely unrelated to the metric. The aim is to partition the n vertices into a given number k of clusters such that every cluster forms a connected subgraph of G and a given clustering objective gets minimized. The constraint that the clusters are connected has applications in many different fields, like for example community detection and geodesy. So far, k-center and k-median have been studied in this setting. It has been shown that connected k-median is Ω(n^{1- ε})-hard to approximate which also carries over to the connected k-means problem, while for connected k-center it remained an open question whether one can find a constant approximation in polynomial time. We answer this question by providing an Ω(log^*(k))-hardness result for the problem. Given these hardness results, we study the problems on graphs with bounded treewidth. We provide exact algorithms that run in polynomial time if the treewidth w is a constant. Furthermore, we obtain constant approximation algorithms that run in FPT time with respect to the parameter max(w,k). Additionally, we consider the min-sum-radii (MSR) and min-sum-diameter (MSD) objectives. We prove that on general graphs, connected MSR can be approximated with an approximation factor of (3 + ε) and connected MSD with an approximation factor of (4 + ε). The latter also directly improves the best known approximation guarantee for unconstrained MSD from (6 + ε) to (4 + ε). We complement this with a reduction showing that connected MSR is NP-hard to approximate with an approximation factor smaller than (4/3). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jan Eube and Heiko Röglin 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.135 urn:nbn:de:0030-drops-272713 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.135 eng https://creativecommons.org/licenses/by/4.0/legalcode