Approximation Algorithms for Graph Clustering Problems with Clusters of Bounded Size
Victor P. Il’ev, Svetlana Il’eva, Alexander V. Kononov · Journal of Applied and Industrial Mathematics · 2024
In the cluster editing problem, one has to partition the set of vertices of a graph into pairwise disjoint subsets (called clusters) minimizing the number of edges between clusters and the number of missing edges within clusters. We consider a version of the problem in which cluster sizes are bounded from above by a positive integer $$ s $$ . This problem is NP-hard for any fixed $$ s \geqslant 3 $$ . We propose polynomial-time approximation algorithms for this version of the problem. Their performance guarantees equal $$ 5/3 $$ for the case $$ s = 3 $$ and $$ 2 $$ for $$ s = 4 $$ . We also show that the cluster editing problem is APX-hard for the case of $$ s = 3 $$ .