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 intopairwise disjoint subsets (called clusters) minimizing the number of edges between clusters and thenumber of missing edges within clusters. We consider a version of the problem in which clustersizes 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 ofthe 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\) .