Приближённые алгоритмы для задач кластеризации на графах с кластерами небольшого размера

Приближённые алгоритмы для задач кластеризации на графах с кластерами небольшого размера

Ильев В. П., Ильева С. Д., Кононов А. В.
Дискретный анализ и исследование операций, 31, 4, 40-57 (2024)
Скачать статью

УДК 519.8 
DOI: 10.33048/daio.2024.31.802

Аннотация:

В задачах кластеризации на графах требуется разбить множество вершин заданного графа на попарно непересекающиеся подмножества (называемые кластерами) так, чтобы минимизировать число рёбер между кластерами и число отсутствующих рёбер внутри кластеров. Мы рассматриваем вариант задачи, в котором размеры кластеров ограничены сверху натуральным числом $s$. Задача NP-трудна для любого фиксированного $s \ge 3$. Для этого варианта задачи предложены полиномиальные приближённые алгоритмы с гарантированными оценками точности, равными 5/3 в случае $s$ = 3 и 2 в случае $s$ = 4. Доказано также, что при $s$ = 3 задача APX-трудна. 
Ил. 5, библиогр. 20.

Литература:
  1. Schaeffer S. E. Graph clustering // Comput. Sci. Rev. 2005. V. 1, No. 1. P. 27–64.
     
  2. Фридман Г. Ш. Одна задача аппроксимации графов // Управляемые системы. Вып. 8. Новосибирск: Изд-во Ин-та математики, 1971. C. 73–75.
     
  3. Фридман Г. Ш. Исследование одной задачи классификации на графах // Методы моделирования и обработка информации. Новосибирск: Наука, 1976. С. 147–177.
     
  4. Tomescu I. La reduction minimale d’un graphe à une reunion de cliques // Discrete Math. 1974. V. 10, No. 1–2. P. 173–179 [French].
     
  5. Zahn C. T. Approximating symmetric relations by equivalence relations // J. Soc. Ind. Appl. Math. 1964. V. 12, No. 4. P. 840–847.
     
  6. Агеев А. А., Ильев В. П., Кононов А. В., Талевнин А. С. Вычислительная сложность задачи аппроксимации графов // Дискрет. анализ и исслед. операций. Сер. 1. 2006. Т. 13, № 1. С. 3–11.
     
  7. Bansal N., Blum A., Chawla S. Correlation clustering // Mach. Learn. 2004. V. 56, No. 1–3. P. 89–113.
     
  8. Ben-Dor A., Shamir R., Yakhimi Z. Clustering gene expression patterns // J. Comput. Biol. 1999. V. 6, No. 3–4. P. 281–297.
     
  9. Shamir R., Sharan R., Tsur D. Cluster graph modification problems // Discrete Appl. Math. 2004. V. 144, No. 1–2. P. 173–182.
     
  10. Puleo G. J., Milenkovic O. Correlation clustering with constrained cluster sizes and extended weights bounds // SIAM J. Optim. 2015. V. 25, No. 3. P. 1857–1872.
     
  11. Pandove D., Goel S., Rani R. Correlation clustering methodologies and their fundamental results // Expert Syst. 2018. V. 35, No. 1. Paper ID e12229. 24 p.
     
  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). New York: ACM, 2015. P. 219–228. DOI: 10.1145/2746539.2746604.
     
  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). Cham: Springer, 2016. P. 25–36. (Lect. Notes Comput. Sci.; V. 9869). DOI: 10.1007/ 978-3-319-44914-2_3.
     
  14. Wahid D. F., Hassini E. A literature review on correlation clustering: Crossdisciplinary taxonomy with bibliometric analysis // Oper. Res. Forum. 2022. V. 3. Paper ID 47. 42 p.
     
  15. Bonchi F., García-Soriano D., Gullo F. Correlation clustering. Cham: Springer, 2022. 148 p. DOI: 10.1007/978-3-031-79210-6.
     
  16. Ильев В. П., Навроцкая А. А. Вычислительная сложность задачи аппроксимации графами с компонентами связности ограниченного размера // Прикл. дискрет. математика. 2011. № 3. С. 80–84.
     
  17. Ильев В. П., Ильева С. Д., Навроцкая А. А. О задаче кластеризации графа с ограничением на размеры кластеров // Дискрет. анализ и исслед. операций. 2016. Т. 23, № 3. С. 5–20.
     
  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). Cham: Springer, 2023. P. 134–145. (Commun. Comput. Inf. Sci.; V. 1881). DOI: 10.1007/978-3-031-43257-6_11.
     
  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). Cham: Springer, 2023. P. 316–328. (Lect. Notes Comput. Sci.; V. 14395). DOI: 10.1007/978-3-031-47859-8_23.
     
  20. Chataigner F., Manić G., Wakabayashi Y., Yuster R. Approximation algorithms and hardness results for the clique packing problem // Discrete Appl. Math. 2009. V. 157, No. 7. P. 1396–1406. DOI: 10.1016/j.dam.2008. 10.017.

Работа первого автора выполнена в рамках гос. задания Института математики им. С. Л. Соболева (проект № FWNF–2022–0020). Работа второго автора выполнена за счёт бюджета Омского гос. университета им. Ф. М. Достоевского. Работа третьего автора выполнена в рамках гос. задания Института математики им. С. Л. Соболева (проект № FWNF–2022–0019). Дополнительных грантов на проведение или руководство этим исследованием получено не было.

Ильев Виктор Петрович
  1. Институт математики им. С. Л. Соболева, 
    пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
  2. Омский гос. университет им. Ф. М. Достоевского, 
    пр. Мира, 55-А, 644077 Омск, Россия

E-mail: iljev@mail.ru

Ильева Светлана Диадоровна
  1. Омский гос. университет им. Ф. М. Достоевского, 
    пр. Мира, 55-А, 644077 Омск, Россия
Кононов Александр Вениаминович
  1. Институт математики им. С. Л. Соболева, 
    пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия

E-mail: alvenko@math.nsc.ru

Статья поступила 17 мая 2024 г.
После доработки — 11 июня 2024 г.
Принята к публикации 22 июня 2024 г.

Abstract:

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 \ge 3$. We propose polynomialtime 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.

References:
  1. S. E. Schaeffer, Graph clustering, Comput. Sci. Rev. 1 (1), 27–64 (2005).
     
  2. G. Sh. Fridman, One problem in graph approximation, in Controlled Systems, Vol. 8 (Izd. Inst. Mat., Novosibirsk, 1971), pp. 73–75 [Russian].
     
  3. G. Sh. Fridman, Investigation of one problem in graph classification, in Modelling Methods and Information Processing (Nauka, Novosibirsk, 1976), pp. 147–177 [Russian].
     
  4. I. Tomescu, La reduction minimale d’un graphe à une reunion de cliques, Discrete Math. 10 (1–2), 173–179 (1974) [French].
     
  5. C. T. Zahn, Approximating symmetric relations by equivalence relations, J. Soc. Ind. Appl. Math. 12 (4), 840–847 (1964).
     
  6. A. A. Ageev, V. P. Il’ev, A. V. Kononov, and A. S. Talevnin, Computational complexity of the graph approximation problem, Diskretn. Anal. Issled. Oper., Ser. 1, 13 (1), 3–11 (2006) [Russian] [J. Appl. Ind. Math. 1 (1), 1–8 (2023)].
     
  7. N. Bansal, A. Blum, and S. Chawla, Correlation clustering, Mach. Learn. 56 (1–3), 89–113 (2004).
     
  8. A. Ben-Dor, R. Shamir, and Z. Yakhimi, Clustering gene expression patterns, J. Comput. Biol. 6 (3–4), 281–297 (1999).
     
  9. R. Shamir, R. Sharan, and D. Tsur, Cluster graph modification problems, Discrete Appl. Math. 144 (1–2), 173–182 (2004).
     
  10. G. J. Puleo and O. Milenkovic, Correlation clustering with constrained cluster sizes and extended weights bounds, SIAM J. Optim. 25 (3), 1857–1872 (2015).
     
  11. D. Pandove, S. Goel, and R. Rani, Correlation clustering methodologies and their fundamental results, Expert Syst. 35 (1), ID e12229 (2018).
     
  12. S. Chawla, K. Makarychev, T. Schramm, and G. Yaroslavtsev, Near optimal LP rounding algorithm for correlation clustering on complete and complete $k$-partite graphs, in Proc. 47th Annu. ACM Symp. Theory of Computing, Portland, OR, USA, June 14–17, 2015 (ACM, New York, 2015), pp. 219–228, DOI: 10.1145/2746539.2746604.
     
  13. V. P. Il’ev, S. D. Il’eva, and A. V. Kononov, Short survey on graph correlation clustering with minimization criteria, in Discrete Optimization and Operations Research (Proc. 9th Int. Conf., Vladivostok, Russia, Sept. 19–23, 2016) (Springer, Cham, 2016), pp. 25–36 (Lect. Notes Comput. Sci., Vol. 9869), DOI: 10.1007/978-3-319-44914-2_3.
     
  14. D. F. Wahid and E. Hassini, A literature review on correlation clustering: Cross-disciplinary taxonomy with bibliometric analysis, Oper. Res. Forum 3, ID 47 (2022).
     
  15. F. Bonchi, D. García-Soriano and F. Gullo, Correlation Clustering (Springer, Cham, 2022), DOI: 10.1007/978-3-031-79210-6.
     
  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., No. 3, 80–84 (2011) [Russian].
     
  17. V. P. Il’ev, S. D. Il’eva, and A. A. Navrotskaya, Graph clustering with a constraint on cluster sizes, Diskretn. Anal. Issled. Oper. 23 (3), 5–20 (2016) [Russian] [J. Appl. Ind. Math. 10 (3), 341–348 (2016)].
     
  18. V. P. Il’ev and S. D. Il’eva, Approximation algorithms for graph cluster editing problems with cluster size at most 3 or 4, in Mathematical Optimization Theory and Operations Research: Recent Trends (Rev. Sel. Pap. 22nd Int. Conf., Yekaterinburg, Russia, July 2–8, 2023) (Springer, Cham, 2023), pp. 134–145 (Commun. Comput. Inf. Sci., Vol. 1881), DOI: 10.1007/978-3-031-43257-6.
     
  19. A. V. Kononov and V. P. Il’ev, On cluster editing problem with clusters of small sizes, in Optimization and Applications (Rev. Sel. Pap. 14th Int. Conf., Petrovac, Montenegro, Sept. 18–22, 2023) (Springer, Cham, 2023), pp. 316–328 (Lect. Notes Comput. Sci., Vol. 14395), DOI: 10.1007/978-3-031-47859-8.
     
  20. F. Chataigner, G. Manić, Y. Wakabayashi, and R. Yuster, Approximation algorithms and hardness results for the clique packing problem, Discrete Appl. Math. 157 (7), 1396–1406 (2009), DOI: 10.1016/j.dam.2008.10.017.