Partitioning a Graph into Low-Diameter Clusters

This paper studies the problems of partitioning the vertices of a graph $G=(V,E)$ into (or covering with) a minimum number of low-diameter clusters from the lenses of approximation algorithms and integer programming. Here, the low-diameter criterion is formalized by an s-club, which is a subset of vertices whose induced subgraph has diameter at most s. For these problems, we give $\tilde{O}(n^{1/2})$-approximation algorithms for any even integer s, generalizing a previous algorithm for the case $s=2$. (The $\tilde{O}(·)$ notation suppresses logarithmic factors and $n≔|V|$.) Complementing this, we show that for any $\epsilon >0$ the problem is NP-hard to approximate within $n^{1/2-\epsilon }$ and $n^{1-\epsilon }$, for each fixed even and odd integer s, respectively, suggesting a contrast in approximability for even and odd values of s. Second, we develop new MIP-based heuristics (inspired by the approximation algorithms) that perform well in practice, solving more than half of previous benchmark instances in less than one second. To handle the remaining instances, we propose a MIP formulation with an exponentially large class of cut-like inequalities that we solve with a branch-and-cut algorithm. With it, we tackle more benchmark instances than previous approaches and in less time.

History: Accepted by Alice E. Smith, Russel Bent / Network Optimization: Algorithms & Applications.

Funding: This work was supported by the National Science Foundation [Grants 1942065 and 2318790].

Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2025.1448) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2025.1448). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/.