On the complexity of graph clustering in~the~problem~with bounded cluster sizes

R. V. Baldzhanova ; A. V. Ilev ; V. P. Il'ev

Prikladnaâ diskretnaâ matematika, no. 2 (2023), pp. 76-84

Résumé

In the graph clustering problems, for a given graph $G$, one has to find a nearest cluster graph on the same vertex set. A graph is called cluster graph if all its connected components are complete graphs. The distance between two graphs is equal to the number of non-coincide edges. In the paper, we consider the graph clustering problem with bounded size $s$ of clusters. The clustering complexity of a graph $G$ is the distance from $G$ to a nearest cluster graph. In the case of ${s=2}$, we prove that the clustering complexity of an arbitrary $n$-vertex graph doesn't exceed ${\left\lfloor {(n-1)^2}/{2} \right\rfloor}$ for ${n \geq 2}$. In the case of ${s=3}$, we propose a polynomial time approximation algorithm for solving the graph clustering problem and use this algorithm to prove that clustering complexity of an arbitrary $n$-vertex graph doesn't exceed ${({n(n-1)}/{2} - 3\left\lfloor {n}/{3}\right\rfloor)}$ for ${n \geq 4}$.

Détail

Keywords: graph, clustering, clustering complexity.