New Algorithms and Hardness Results for Connected Clustering
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908671618842624 |
|---|---|
| author | Eube, Jan Röglin, Heiko |
| author_facet | Eube, Jan Röglin, Heiko |
| contents | 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) 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 + ε)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_19085 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | New Algorithms and Hardness Results for Connected Clustering Eube, Jan Röglin, Heiko Data Structures and Algorithms 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) 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 + ε)$. |
| title | New Algorithms and Hardness Results for Connected Clustering |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2511.19085 |