Geodesic
On the complexity of graph clustering in~the~problem~with bounded cluster sizes
Prikladnaâ diskretnaâ matematika, no. 2 (2023), pp. 76-84.

Voir la notice de l'article provenant de la source Math-Net.Ru

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}$.
Keywords: graph, clustering, clustering complexity. 
@article{PDM_2023_2_a5,
     author = {R. V. Baldzhanova and A. V. Ilev and V. P. Il'ev},
     title = {On the complexity of graph clustering in~the~problem~with bounded cluster sizes},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {76--84},
     publisher = {mathdoc},
     number = {2},
     year = {2023},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2023_2_a5/}
}
TY  - JOUR
AU  - R. V. Baldzhanova
AU  - A. V. Ilev
AU  - V. P. Il'ev
TI  - On the complexity of graph clustering in~the~problem~with bounded cluster sizes
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2023
SP  - 76
EP  - 84
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2023_2_a5/
LA  - ru
ID  - PDM_2023_2_a5
ER  - 
%0 Journal Article
%A R. V. Baldzhanova
%A A. V. Ilev
%A V. P. Il'ev
%T On the complexity of graph clustering in~the~problem~with bounded cluster sizes
%J Prikladnaâ diskretnaâ matematika
%D 2023
%P 76-84
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2023_2_a5/
%G ru
%F PDM_2023_2_a5
R. V. Baldzhanova; A. V. Ilev; V. P. Il'ev. On the complexity of graph clustering in~the~problem~with bounded cluster sizes. Prikladnaâ diskretnaâ matematika, no. 2 (2023), pp. 76-84. http://geodesic.mathdoc.fr/item/PDM_2023_2_a5/

[1] Schaeffer S. E., “Graph clustering”, Comput. Sci. Rev., 1:1 (2005), 27–64 | DOI

[2] Lyapunov A. A., “On the structure and evolution of control systems in connection with the theory of classification”, Problemy Kibernetiki, 27, Nauka Publ., M., 1973, 7–18 (in Russian)

[3] Fridman G. Sh., “A graph approximation problem”, Upravlyaemye Sistemy, 8 (1971), 73–75 (in Russian)

[4] Fridman G. Sh., “On an inequality in the graph approximation problem”, Cybern. Syst. Anal., 1974, no. 10, 554

[5] Bansal N., Blum A., and Chawla S., “Correlation clustering”, Machine Learning, 56 (2004), 89–113 | DOI | MR | Zbl

[6] Ben-Dor A., Shamir R., and Yakhimi Z., “Clustering gene expression patterns”, J. Comput. Biol., 6:3–4 (1999), 281–297 | DOI

[7] Shamir R., Sharan R., and Tsur D., “Cluster graph modification problems”, Discrete Appl. Math., 144:1–2 (2004), 173–182 | DOI | MR | Zbl

[8] Tomescu I., “La reduction minimale d'un graphe a une reunion de cliques”, Discrete Math., 10:1–2 (1974), 173–179 | DOI | MR | Zbl

[9] Zahn C. T., “Approximating symmetric relations by equivalence relations”, J. SIAM, 12:4 (1964), 840–847 | MR | Zbl

[10] Il'ev V. P. and Fridman G. Sh., “On the problem of approximation by graphs with a fixed number of components”, Sov. Math. Dokl., 25:3 (1982), 666–670 | MR | Zbl

[11] Fridman G. Sh., “Study of a classifying problem on graphs”, Metody Modelirovaniya i Obrabotki Informatsii, Nauka Publ., Novosibirsk, 1976, 147–177 (in Russian)

[12] Papadimitriou C. H. and Steiglitz K., Combinatorial Optimization: Algorithms and Complexity, Prentice-Hall Inc., NJ, 1982, 496 pp. | MR | MR | Zbl