New Algorithms and Hardness Results for Connected Clustering

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 Ω(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 Ω(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+ϵ).