Abstract: In the cluster editing problem, one has to partition the set of vertices of a graph into 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 > 3. We propose polynomial-time approximation algorithms for this version of the problem. Their performance guarantees are better than earlier known bounds for the cases s = 3 and s = 4. We also show that the cluster editing problem is APX-complete for the case s = 3 even if the maximum degree of the graphs is bounded by 4.

Cite: Kononov A.V. , Ильев В.П.
On cluster editing problem with clusters of small sizes
XIV International Conference Optimization and Applications 18-22 Sep 2023