Approximation algorithms for graph clustering problems with clusters of bounded size

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.$ Illustr. 5, bibliogr. 20.