Метод ветвей и отсечений для задачи взвешенной 3-раскраски графа

Метод ветвей и отсечений для задачи взвешенной 3-раскраски графа

Жуков Г. А., Ерзин А. И., Плотников Р. В.
Дискретный анализ и исследование операций, 33, 2, 46-63 (2026)
Скачать статью

УДК 519.852+519.856+519.6 
DOI: 10.33048/daio.2026.33.848

Аннотация:

Для рёберно-взвешенного неориентированного графа рассматривается NP-трудная задача раскраски вершин в три цвета при условии минимизации суммарного веса рёбер, соединяющих вершины одного цвета. Данная задача математически эквивалентна известной задаче о максимальном разрезе на $k$ частей (о максимальном $k$-разрезе, maximum $k$-cut), где требуется максимизировать вес рёбер между вершинами из различных подмножеств. В настоящей работе представлен точный алгоритм для случая $k = 3$, реализованный в рамках схемы ветвей и отсечений (branch-and-cut). В то время как большинство существующих исследований сфокусированы на классах допустимых неравенств, ключевым вкладом данной работы является метод уменьшения глубины дерева ветвления на основе декомпозиции вершин, интегрированный в схему branch-and-cut. Вычислительные эксперименты демонстрируют высокую эффективность разработанного алгоритма. 

Табл. 4, ил. 1, библиогр. 28.

Литература:
  1. Karp R. M. Reducibility among combinatorial problems // Complexity of computer computations. Proc. Symp. (New York, USA, March 20–22, 1972). New York: Plenum Press, 1972. P. 85–103. DOI: 10.1007/978-1-4684-2001-2_9.
     
  2. Borodin O. V. Colorings of plane graphs: A survey // Discrete Math. 2013. V. 313, No. 4. P. 517–539. DOI: 10.1016/j.disc.2012.11.011.
     
  3. Husfeldt T. Graph colouring algorithms // Topics in chromatic graph theory. Cambridge: Cambridge Univ. Press, 2015. P. 277–303. (Encycl. Math. Appl.). DOI: 10.1017/CBO9781139519793.016.
     
  4. Kostochka A. V., Yancey M. On coloring of sparse graphs // Computer science — Theory and applications. Proc. 8th Int. Comput. Sci. Symp. in Russia (Yekaterinburg, Russia, June 25–29, 2013). Heidelberg: Springer, 2013. P. 224–234. (Lect. Notes Comput. Sci.; V. 7913). DOI: 10.1007/ 978-3-642-38536-0_20.
     
  5. Brélaz D. New methods to color the vertices of a graph // Commun. ACM. 1979. V. 22, No. 4. P. 251–256. DOI: 10.1145/359094.359101.
     
  6. Mehrotra A., Trick M. A. A column generation approach for graph coloring // INFORMS J. Comput. 1996. V. 8, No. 4. P. 344–354. DOI: 10.1287/ijoc.8.4.344.
     
  7. Galinier P., Hao J.-K. Hybrid evolutionary algorithms for graph coloring // J. Comb. Optim. 1999. V. 3. P. 379–397. DOI: 10.1023/A:1009823419804.
     
  8. Moalic L., Gondran A. Variations on memetic algorithms for graph coloring problems // J. Heuristics. 2018. V. 24, No. 4. P. 1–24. DOI: 10.1007/s10732-017-9354-9.
     
  9. Cranston D. W., Rabern L. W. Coloring a graph with $\Delta − 1$ colors: Conjectures equivalent to the Borodin–Kostochka conjecture that appear weaker // Eur. J. Comb. 2015. V. 44. P. 23–42. DOI: 10.1016/j.ejc.2014.09.006.
     
  10. Choi I., Kierstead H. A., Rabern L. W. The list version of the Borodin–Kostochka conjecture for graphs with large maximum degree // Discrete Math. 2023. V. 346, No. 11. Article ID 113300. 12 p. DOI: 10.1016/j.disc.2022.113300.
     
  11. Maus Y. Distributed graph coloring made easy. Ithaca, NY, 2021. 22 p. (e-Print Archive / Cornell Univ.; arXiv:2105.05575). DOI: 10.48550/arXiv. 2105.05575.
     
  12. Dailey D. P. Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete // Discrete Math. 1980. V. 30, No. 3. P. 289–293. DOI: 10.1016/0012-365X(80)90236-8.
     
  13. Meijer L. 3-Coloring in time O(1.3217n). Ithaca, NY, 2023. 17 p. (e-Print Archive / Cornell Univ.; arXiv:2302.13644). DOI: 10.48550/arXiv.2302.13644.
     
  14. Dvořák Z., Kawarabayashi K.-I., Thomas R. Three-coloring triangle-free planar graphs in linear time // ACM Trans. Algorithms. 2011. V. 7, No. 4. Article ID 41. 14 p. DOI: 10.1145/2000807.2000809.
     
  15. Goemans M., Williamson D. P. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming // J. ACM. 1995. V. 42, No. 6. P. 1115–1145. DOI: 10.1145/227683.227684.
     
  16. Frieze A., Jerrum M. Improved approximation algorithms for max-$k$-cut and max bisection // Algorithmica. 1997. V. 18. P. 67–81. DOI: 10.1007/BF02523688.
     
  17. De Klerk E., Pasechnik D. V., Warners J. P. On approximate graph colouring and max-$k$-cut algorithms based on the $\vartheta$-function // J. Comb. Optim. 2004. V. 8, No. 3. P. 267–294. DOI: 10.1023/B:JOCO.0000038911.67280.3f.
     
  18. Margot F. Pruning by isomorphism in Branch-and-cut // Math. Program. Ser. A. 2002. V. 94. P. 71–90. DOI: 10.1007/s10107-002-0358-2.
     
  19. Chopra S., Rao M. The partition problem // Math. Program. 1993. V. 59, No. 1. P. 87–115. DOI: 10.1007/BF01581239.
     
  20. Eisenblätter A. The semidefinite relaxation of the $k$-partition polytope is strong // Integer programming and combinatorial optimization. Proc. 9th Int. IPCO Conf. (Cambridge, USA, May 27–29, 2002). Heidelberg: Springer, 2002. P. 273–290. (Lect. Notes Comput. Sci.; V. 2337). DOI: 10.1007/3-540-47867-1_20.
     
  21. De Sousa R. Global optimization of the maximum $K$-cut problem: PhD Thesis. Montreal, 2018. 95 p.
     
  22. Ghaddar B., Anjos M. F., Liers F. A branch-and-cut algorithm based on semidefinite programming for the minimum $k$-partition problem // Ann. Oper. Res. 2011. V. 188, No. 1. P. 155–174. DOI: 10.1007/ s10479-008-0481-4.
     
  23. Ales Z., Knippel A. The $K$-partitioning problem: Formulations and branchand-cut // Networks. 2020. V. 76, No. 3. P. 323–349. DOI: 10.1002/net.21944.
     
  24. Healy P., Jozefowiez N., Laroche P., Marchetti F., Martin S., Róka Z. A branch-and-cut algorithm for the connected max-$k$-cut problem // Eur. J. Oper. Res. 2024. V. 312, No. 1. P. 117–124. DOI: 10.1016/j.ejor.2023.06.015.
     
  25. Benichou M., Gauthier J. M., Girodet P., Hentges G., Ribiere G., Vincent O. Experiments in mixed-integer linear programming // Math. Program. 1971. V. 1. P. 76–94. DOI: 10.1007/BF01584074.
     
  26. Kovrizhnykh N. A. 3-Coloring: Graph generator for MOTOR 2025 Challenge 5. 2025. URL: https://github.com/sedefe/3-coloring  (accessed: 6.08.2026).
     
  27. MOTOR 2025 challenges. Novosibirsk: IM SO RAN, 2025. URL: https://old.math.nsc.ru/conference/motor/2025/challenges.html (accessed: 6.08.2026).
     
  28. Dataset of generated and unit-disk graphs. 2025. URL: https://disk.yandex.ru/d/cbMBI1Rp0J535Q (accessed: 6.08.2026).

Исследование выполнено в рамках государственного задания Институт математики им. С. Л. Соболева (проект № FWNF–2026–0021). Дополнительных грантов на проведение или руководство этим исследованием получено не было.

Жуков Георгий Алексеевич
  1. Новосибирский гос. университет, 
    ул. Пирогова, 2, 630090 Новосибирск, Россия

E-mail: g.zhukov@g.nsu.ru 

Ерзин Адиль Ильясович
  1. Новосибирский гос. университет, 
    ул. Пирогова, 2, 630090 Новосибирск, Россия
  2. Институт математики им. С. Л. Соболева, 
    пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия

E-mail: adilerzin@math.nsc.ru 

Плотников Роман Викторович
  1. ООО «Ледас», 
    ул. Николаева, 11/5, 630090 Новосибирск, Россия

E-mail: rvplotnikov@gmail.com 

Статья поступила 17 декабря 2025 г.
После доработки — 15 февраля 2026 г.
Принята к публикации 23 марта 2026 г.

Abstract:

This study addresses the NP-hard problem of coloring the vertices of an edge-weighted undirected graph with 3 colors, aiming to minimize the total weight of edges connecting vertices of the same color. This problem is mathematically equivalent to the well-known Maximum $k$-Cut problem, where the objective is to maximize the weight of edges between vertices from different subsets. In this work, we present an exact algorithm for the case $k = 3$, implemented within the branchand-cut framework. While most existing research focuses on classes of valid inequalities, the key contribution of this paper is a method for reducing the depth of the branching tree based on vertex decomposition integrated into the branch-and-cut scheme. Computational experiments demonstrate the high efficiency of the proposed algorithm. 

Tab. 4, illustr. 1, bibliogr. 28.

References:
  1. R. M. Karp, Reducibility among combinatorial problems, in Complexity of Computer Computations, Proc. Symp. (New York, USA, March 20–22, 1972) (Plenum Press, New York, 1972), pp. 85–103, DOI: 10.1007/ 978-1-4684-2001-2_9.
     
  2. O. V. Borodin, Colorings of plane graphs: A survey, Discrete Math. 313 (4), 517–539 (2013), DOI: 10.1016/j.disc.2012.11.011.
     
  3. T. Husfeldt, Graph colouring algorithms, in Topics in Chromatic Graph Theory (Cambridge Univ. Press, Cambridge, 2015), pp. 277–303 (Encycl. Math. Appl.), DOI: 10.1017/CBO9781139519793.016.
     
  4. A. V. Kostochka and M. Yancey, On coloring of sparse graphs, in Computer Science— Theory and Applications, Proc. 8th Int. Comput. Sci. Symp. in Russia (Yekaterinburg, Russia, June 25–29, 2013) (Springer, Heidelberg, 2013), pp. 224–234 (Lect. Notes Comput. Sci., Vol. 7913), DOI: 10.1007/ 978-3-642-38536-0_20.
     
  5. D. Brélaz, New methods to color the vertices of a graph, Commun. ACM 22 (4), 251–256 (1979), DOI: 10.1145/359094.359101.
     
  6. A. Mehrotra and M. A. Trick, A column generation approach for graph coloring, INFORMS J. Comput. 8 (4), 344–354 (1996), DOI: 10.1287/ijoc.8.4.344.
     
  7. P. Galinier and J.-K. Hao, Hybrid evolutionary algorithms for graph coloring, J. Comb. Optim. 3, 379–397 (1999), DOI: 10.1023/A:1009823419804.
     
  8. L. Moalic and A. Gondran, Variations on memetic algorithms for graph coloring problems, J. Heuristics 24 (4), 1–24 (2018), DOI: 10.1007/s10732-017-9354-9.
     
  9. D. W. Cranston and L. W. Rabern, Coloring a graph with $\Delta − 1$ colors: Conjectures equivalent to the Borodin–Kostochka conjecture that appear weaker, Eur. J. Comb. 44, 23–42 (2015), DOI: 10.1016/j.ejc.2014.09.006.
     
  10. I. Choi, H. A. Kierstead, and L. W. Rabern, The list version of the Borodin–Kostochka conjecture for graphs with large maximum degree, Discrete Math. 346 (11), ID 113300 (2023), DOI: 10.1016/j.disc.2022.113300.
     
  11. Y. Maus, Distributed graph coloring made easy (Ithaca, NY, 2021) (e-Print Archive / Cornell Univ., arXiv:2105.05575), DOI: 10.48550/arXiv.2105.05575.
     
  12. D. P. Dailey, Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete, Discrete Math. 30 (3), 289–293 (1980), DOI: 10. 1016/0012-365X(80)90236-8.
     
  13. L. Meijer, 3-Coloring in time O(1.3217n) (Ithaca, NY, 2023) (e-Print Archive / Cornell Univ., arXiv:2302.13644), DOI: 10.48550/arXiv.2302. 13644.
     
  14. Z. Dvořák, K.-I. Kawarabayashi, and R. Thomas, Three-coloring triangle-free planar graphs in linear time, ACM Trans. Algorithms 7 (4), ID 41 (2011), DOI: 10.1145/2000807.2000809.
     
  15. M. Goemans and D. P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. ACM 42 (6), 1115–1145 (1995), DOI: 10.1145/227683.227684.
     
  16. A. Frieze and M. Jerrum, Improved approximation algorithms for max-$k$-cut and max bisection, Algorithmica 18, 67–81 (1997), DOI: 10.1007/ BF02523688.
     
  17. E. De Klerk, D. V. Pasechnik, and J. P. Warners, On approximate graph colouring and max-$k$-cut algorithms based on the $\vartheta$-function, J. Comb. Optim. 8 (3), 267–294 (2004), DOI: 10.1023/B:JOCO.0000038911.67280.3f.
     
  18. F. Margot, Pruning by isomorphism in Branch-and-Cut, Math. Program., Ser. A, 94, 71–90 (2002), DOI: 10.1007/s10107-002-0358-2.
     
  19. S. Chopra and M. Rao, The partition problem, Math. Program. 59 (1), 87–115 (1993), DOI: 10.1007/BF01581239. 
     
  20. A. Eisenblätter, The semidefinite relaxation of the $k$-partition polytope is strong, in Integer Programming and Combinatorial Optimization, Proc. 9th Int. IPCO Conf. (Cambridge, USA, May 27–29, 2002) (Springer, Heidelberg, 2002), pp. 273–290 (Lect. Notes Comput. Sci., Vol. 2337), DOI: 10.1007/ 3-540-47867-1_20.
     
  21. R. de Sousa, Global optimization of the maximum $K$-cut problem, PhD Thesis (Montreal, 2018).
     
  22. B. Ghaddar, M. F. Anjos, and F. Liers, A branch-and-cut algorithm based on semidefinite programming for the minimum $k$-partition problem, Ann. Oper. Res. 188 (1), 155–174 (2011), DOI: 10.1007/s10479-008-0481-4. 
     
  23. Z. Ales and A. Knippel, The $K$-partitioning problem: Formulations and branch-and-cut, Networks 76 (3), 323–349 (2020), DOI: 10.1002/net.21944.
     
  24. P. Healy, N. Jozefowiez, P. Laroche, F. Marchetti, S. Martin, and Z. Róka, A branch-and-cut algorithm for the connected max-$k$-cut problem, Eur. J. Oper. Res. 312 (1), 117–124 (2024), DOI: 10.1016/j.ejor.2023.06.015. 
     
  25. M. Benichou, J. M. Gauthier, P. Girodet, G. Hentges, G. Ribiere, and O. Vincent, Experiments in mixed-integer linear programming, Math. Program. 1, 76–94 (1971), DOI: 10.1007/BF01584074.
     
  26. N. A. Kovrizhnykh, 3-Coloring: Graph generator for MOTOR 2025 Challenge 5 (2025), URL: https://github.com/sedefe/3-coloring (accessed: 6.08.2026).
     
  27. MOTOR 2025 Challenges (IM SO RAN, Novosibirsk, 2025), URL: https://old.math.nsc.ru/conference/motor/2025/challenges.html (accessed: 6.08.2026).
     
  28. Dataset of generated and unit-disk graphs (2025), URL: https://disk.yandex.ru/d/cbMBI1Rp0J535Q (accessed: 6.08.2026).