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. Complementing this, we show that for any ε > 0 the problem is NP-hard to approximate within $n^{1/2-ε}$ and $n^{1-ε}$, for each fixed even and odd integer s, respectively, suggesting an interesting contrast in approximability for even and odd values of s. Second, we develop new MIP-based heuristics (inspired by the approximation algorithms) that perform extremely 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.
Citation
Submitted