Approximate algorithms for graph clustering problem

In the paper, the graph clustering problem is studied. For the version of the problem when the number of clusters does not exceed $3$, we develop three approximate algorithms. The first algorithm uses as a procedure the known Coleman–Saunderson–Wirth algorithm which approximately solves the similar problem when the number of clusters does not exceed $2$, and repeatedly applies a local search. On the contrary, our second algorithm is based on an original idea and does not use a local search at all. The main difference between these algorithms is the following. The first algorithm looks over all vertices of a given graph, for each vertex forms the cluster involving this vertex and all its neighbors and on the rest of the vertices forms one or two clusters using the Coleman–Saunderson–Wirth algorithm. The second algorithm looks over all ordered pairs of vertices of a given graph and for every pair forms two clusters at once, each of which contains only one vertex of this pair with some of its neighbors, placing the rest of the vertices to the third cluster (the third cluster may be empty). Finally, the third algorithm applies the local search only once to the feasible solution returned by the second one. A priori performance guarantees of all approximate algorithms are obtained, the best is equal to $(6-12/n)$ for the second and the third algorithms, where $n$ is the number of vertices of a given graph. Also, experimental comparing of the developed algorithms was carried out. Experimental testing show that running time of our second and third algorithms is essentially less than running time of the first algorithm. At the same time the third algorithm demonstrated the best results in sense of accuracy of the solutions. Thus, the third algorithm has the best characterstics both from point of view of theoretical analysis and experimental study.