Geodesic
Approximation algorithms for graph clustering problems with clusters of bounded size
Diskretnyj analiz i issledovanie operacij, Tome 31 (2024) no. 4, pp. 40-57 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

In the cluster editing problem, one has to partition the set of vertices of a graph into pairwise disjoint subsets (called clusters) minimizing the number of edges between clusters and the number of missing edges within clusters. We consider a version of the problem in which cluster sizes are bounded from above by a positive integer $s.$ This problem is NP-hard for any fixed $s \geqslant 3.$ We propose polynomial-time approximation algorithms for this version of the problem. Their performance guarantees equal $5/3$ for the case $s = 3$ and $2$ for $s = 4.$ We also show that the cluster editing problem is APX-hard for the case of $s = 3.$ Illustr. 5, bibliogr. 20.
Keywords: graph, clustering, NP-hard problem, approximation algorithm, performance guarantee. 
@article{DA_2024_31_4_a2,
     author = {V. P. Il'ev and S. D. Il'eva and A. V. Kononov},
     title = {Approximation algorithms for graph clustering problems with clusters of bounded size},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {40--57},
     year = {2024},
     volume = {31},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2024_31_4_a2/}
}
TY  - JOUR
AU  - V. P. Il'ev
AU  - S. D. Il'eva
AU  - A. V. Kononov
TI  - Approximation algorithms for graph clustering problems with clusters of bounded size
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2024
SP  - 40
EP  - 57
VL  - 31
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/DA_2024_31_4_a2/
LA  - ru
ID  - DA_2024_31_4_a2
ER  - 
%0 Journal Article
%A V. P. Il'ev
%A S. D. Il'eva
%A A. V. Kononov
%T Approximation algorithms for graph clustering problems with clusters of bounded size
%J Diskretnyj analiz i issledovanie operacij
%D 2024
%P 40-57
%V 31
%N 4
%U http://geodesic.mathdoc.fr/item/DA_2024_31_4_a2/
%G ru
%F DA_2024_31_4_a2
V. P. Il'ev; S. D. Il'eva; A. V. Kononov. Approximation algorithms for graph clustering problems with clusters of bounded size. Diskretnyj analiz i issledovanie operacij, Tome 31 (2024) no. 4, pp. 40-57. http://geodesic.mathdoc.fr/item/DA_2024_31_4_a2/

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

[2] G. Sh. Fridman, “One problem in graph approximation”, Controlled Systems, 8, Izd. Inst. Mat., Novosibirsk, 1971, 73–75 (In Russian)

[3] G. Sh. Fridman, “Investigation of one problem in graph classification”, Modelling Methods and Information Processing, Nauka, Novosibirsk, 1976, 147–177 (In Russian)

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

[5] Zahn C. T., “Approximating symmetric relations by equivalence relations”, J. Soc. Ind. Appl. Math., 12:4 (1964), 840–847 | DOI | MR

[6] A. A. Ageev, V. P. Il'ev, A. V. Kononov, and A. S. Talevnin, “Computational complexity of the graph approximation problem”, J. Appl. Ind. Math., 1:1 (2023), 1–8 | DOI | MR

[7] Bansal N., Blum A., Chawla S., “Correlation clustering”, Mach. Learn, 56:1–3 (2004), 89–113 | DOI | MR

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

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

[10] Puleo G. J., Milenkovic O., “Correlation clustering with constrained cluster sizes and extended weights bounds”, SIAM J. Optim., 25:3 (2015), 1857–1872 | DOI | MR

[11] Pandove D., Goel S., Rani R., “Correlation clustering methodologies and their fundamental results”, Expert Syst., 35:1 (2018), e12229, 24 pp. | DOI

[12] Chawla S., Makarychev K., Schramm T., Yaroslavtsev G., “Near optimal LP rounding algorithm for correlation clustering on complete and complete $k$-partite graphs”, Proc. 47th Annu. ACM Symp. Theory of Computing (Portland, OR, USA, June 14–17, 2015), ACM, New York, 2015, 219–228 | DOI | MR

[13] Il'ev V. P., Il'eva S. D., Kononov A. V., “Short survey on graph correlation clustering with minimization criteria”, Discrete optimization and operations research, Proc. 9th Int. Conf. (Vladivostok, Russia, Sept. 19–23, 2016), Lect. Notes Comput. Sci., 9869, Springer, Cham, 2016, 25–36 | DOI | MR

[14] Wahid D. F., Hassini E., “A literature review on correlation clustering: Cross-disciplinary taxonomy with bibliometric analysis”, Oper. Res. Forum, 3 (2022), 47, 42 pp. | DOI | MR

[15] Bonchi F., García-Soriano D., Gullo F., Correlation clustering, Springer, Cham, 2022, 148 pp. | DOI

[16] V. P. Il'ev and A. A. Navrotskaya, “Computational complexity of the problem of approximation by graphs with connected components of bounded size”, Prikl. Diskretn. Mat., 2011, no. 3, 80–84 (In Russian)

[17] V. P. Il'ev, S. D. Il'eva, and A. A. Navrotskaya, “Graph clustering with a constraint on cluster sizes”, J. Appl. Ind. Math., 10:3 (2016), 341–348 | DOI | MR

[18] Il'ev V. P., Il'eva S. D., “Approximation algorithms for graph cluster editing problems with cluster size at most \(3\) or \(4\)”, Mathematical optimization theory and operations research: Recent trends, Rev. Sel. Pap. 22nd Int. Conf. (Yekaterinburg, Russia, July 2–8, 2023), Commun. Comput. Inf. Sci., 1881, Springer, Cham, 2023, 134–145 | DOI | MR

[19] Kononov A. V., Il'ev V. P., “On cluster editing problem with clusters of small sizes”, Optimization and applications, Rev. Sel. Pap. 14th Int. Conf. (Petrovac, Montenegro, Sept. 18–22, 2023), Lect. Notes Comput. Sci., 14395, Springer, Cham, 2023, 316–328 | DOI | MR

[20] Chataigner F., Manić G., Wakabayashi Y., Yuster R., “Approximation algorithms and hardness results for the clique packing problem”, Discrete Appl. Math., 157:7 (2009), 1396–1406 | DOI | MR