# New Algorithms and Hardness Results for Connected Clustering

arXiv: https://arxiv.org/abs/2511.19085 · HTML: https://mlsanity.com/paper/2511.19085/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Nov 2025.

## Built on by (most cited first, 1 of 1)

- [Connected Subspace Clustering: Hardness, a Scalable Heuristic, and an Application to Sea Level Geodesy](https://mlsanity.com/paper/2608.14215/) (2026)

## Abstract (arXiv)

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 Omega(n1- ε)-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 Omega(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) objective. 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 + ε).