$2$-Approximation algorithms for two graph clustering problems

We study a version of the graph $2$-clustering problem and the related semi-supervised problem. In these problems, given an undirected graph, we have to find a nearest $2$-cluster graph, i. e. a graph on the same vertex set with exactly two nonempty connected components each of which is a complete graph. The distance between two graphs is the number of noncoinciding edges. The problems under consideration are NP-hard. In 2008, Coleman, Saunderson, and Wirth presented a polynomial time $2$-approximation algorithm for the analogous problem in which the number of clusters does not exceed $2$. Unfortunately, the method of proving the performance guarantee of the Coleman, Saunderson, and Wirth algorithm is inappropriate for the graph $2$-clustering problem in which the number of clusters equals $2$. We propose a polynomial time $2$-approximation algorithm for the $2$-clustering problem on an arbitrary graph. In contrast to the proof by Coleman, Saunderson, and Wirth, our proof of the performance guarantee of this algorithm does not use switchings. Moreover, we propose an analogous $2$-approximation algorithm for the related semi-supervised problem. Bibliogr. 9.