Clustering Complexity and an Approximation Algorithm for a Version of the Cluster Editing Problem

In graph clustering problems, one has to partition the vertex set of a given undirected graph into pairwise disjoint subsets (clusters). Vertices of the graph correspond to some objects, edges connect the pairs of similar objects. In cluster editing (CE) problems the goal is to find a nearest to a given graph \(G=(V,E)\) cluster graph, i.e., a graph on the same vertex set V each connected component of which is a complete graph. The distance between graphs is understood as the number of their non-coinciding edges. The distance between a graph G and a nearest to G cluster graph is called clustering complexity of G. We consider a version of CE problem in which the size of each cluster is bounded from above by a positive integer s. This problem is NP-hard for any fixed \(s \geqslant 3\) . In 2015, Puleo and Milenkovic proposed a 6-approximation algorithm for this problem. For the version of the problem with \(s=5\) we propose a polynomial-time approximation algorithm with better performance guarantee and prove an upper bound on clustering complexity of a graph that is better than earlier known one.