Устойчивость вершинных покрытий в задаче о вечном вершинном покрытии

Устойчивость вершинных покрытий в задаче о вечном вершинном покрытии

Утюпин С. Ю.
Дискретный анализ и исследование операций, 33, 2, 115-135 (2026)
Скачать статью

УДК 519.8 
DOI: 10.33048/daio.2026.33.863

Аннотация:

Задача о вечном вершинном покрытии является вариантом задачи о вершинном покрытии графа и может рассматриваться как динамическая игра двух сторон (атакующего и защитника) с бесконечным числом шагов. Для построения стратегии защитника задача представляется в виде динамической игры, на каждом шаге которой взаимодействие противоборствующих сторон формализуется как двухуровневая задача математического программирования. В данной работе предложена процедура, позволяющая ответить на вопрос, является ли заданное вершинное покрытие вечным. Идея процедуры заключается в рекурсивной проверке устойчивости вершинных покрытий, полученных в результате решения задач защитника и построения дополнительного графа покрытий и переходов. 

Табл. 2, ил. 7, библиогр. 12.

Литература:
  1. Klostermeyer W. F., Mynhardt C. M. Protecting a graph with mobile guards // Appl. Anal. Discrete Math. 2016. V. 10, No. 1. P. 1–29.
     
  2. Klostermeyer W. F., Mynhardt C. M. Edge protection in graphs // Australas. J. Comb. 2009. V. 45. P. 235–250.
     
  3. Fomin F. V., Gaspers S., Golovach P. A., Kratsch D., Saurabh S. Parameterized algorithm for eternal vertex cover // Inf. Process. Lett. 2010. V. 110, No. 16. P. 702–706.
     
  4. Babu J., Misra N., Nanoti S. G. Eternal vertex cover in bipartite graphs // Computer science — Theory and applications. Proc. 17th Int. Comp. Sci. Symp. in Russia (St. Petersburg, Russia, June 29 – July 1, 2022). Cham: Springer, 2022. P. 64–76. (Lect. Notes Comput. Sci.; V. 13296).
     
  5. Babu J., Prabhakaran V. A new lower bound for the eternal vertex cover number of graphs // J. Comb. Optim. 2021. V. 44, No. 4. P. 2482–2498.
     
  6. Babu J., Chandran L. S., Francis M., Prabhakaran V., Rajendraprasad D., Warrier N. J. On graphs whose eternal vertex cover number and vertex cover number coincide // Discrete Appl. Math. 2022. V. 319. P. 171–182.
     
  7. Babu J., Prabhakaran V., Sharma A. A substructure based lower bound for eternal vertex cover number // Theor. Comput. Sci. 2021. V. 890. P. 87–104.
     
  8. Paul K., Pandey A. Some algorithmic results for eternal vertex cover problem in graphs // WALCOM: Algorithms and computation. Proc. 17th Int. Conf. and Workshops (Hsinchu, Taiwan, Mar. 22–24, 2023). Cham: Springer, 2023. P. 242–253. (Lect. Notes Comput. Sci.; V. 13973).
     
  9. Araki H., Fujito T., Inoue S. On the eternal vertex cover numbers of generalized trees // IEICE Trans. Fundam. Electron. Commun. Comput. Sci. 2015. V. E98-A, No. 6. P. 1153–1160.
     
  10. Klostermeyer W. F., Mynhardt C. M. Graphs with equal eternal vertex cover and eternal domination numbers // Discrete Math. 2011. V. 311, No. 14. P. 1371–1379.
     
  11. Beresnev V. L., Melnikov A. A., Utyupin S. Yu. Representation of the eternal vertex cover problem as a dynamic Stackelberg game // Optimization and applications. Rev. Sel. Pap. 14th Int. Conf. OPTIMA 2023 (Petrovac, Montenegro, Sept. 18–22, 2023). Cham: Springer, 2023. P. 3–13. (Lect. Notes Comput. Sci.; V. 14395).
     
  12. Береснев В. Л., Мельников А. А., Утюпин С. Ю. Устойчивость вершинных покрытий в игре с конечным числом шагов // Дискрет. анализ и исслед. операций. 2024. Т. 31, № 2. С. 28–45.

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

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

E-mail: stepan.utyupin@gmail.com 

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

Abstract:

The eternal vertex cover problem is a modification of the graph vertex cover problem and can be viewed as a dynamic two-player (attacker and defender) game with an infinite number of moves. To construct defender’s strategy, the problem is represented as a dynamic game, where at each step the interaction between the opposing players is formalized as a two-level mathematical programming problem. This study proposes a procedure that allows us to determine whether a given vertex cover is eternal or not. The idea of the procedure is based on recursive verification of stability of vertex covers obtained by solving defender’s problems and constructing an additional graph of covers and transitions. 

Tab. 2, illustr. 7, bibliogr. 12.

References:
  1. W. F. Klostermeyer and C. M. Mynhardt, Protecting a graph with mobile guards, Appl. Anal. Discrete Math. 10 (1), 1–29 (2016).
     
  2. W. F. Klostermeyer and C. M. Mynhardt, Edge protection in graphs, Australas. J. Comb. 45, 235–250 (2009).
     
  3. F. V. Fomin, S. Gaspers, P. A. Golovach, D. Kratsch, and S. Saurabh, Parameterized algorithm for eternal vertex cover, Inf. Process. Lett. 110 (16), 702–706 (2010).
     
  4. J. Babu, N. Misra, and S. G. Nanoti, Eternal vertex cover in bipartite graphs, in Computer Science — Theory and Applications, Proc. 17th Int. Comp. Sci. Symp. in Russia (St. Petersburg, Russia, June 29 – July 1, 2022) (Springer, Cham, 2022), pp. 64–76 (Lect. Notes Comput. Sci., Vol. 13296).
     
  5. J. Babu and V. Prabhakaran, A new lower bound for the eternal vertex cover number of graphs, J. Comb. Optim. 44 (4), 2482–2498 (2021).
     
  6. J. Babu, L. S. Chandran, M. Francis, V. Prabhakaran, D. Rajendraprasad, and N. J. Warrier, On graphs whose eternal vertex cover number and vertex cover number coincide, Discrete Appl. Math. 319, 171–182 (2022).
     
  7. J. Babu, V. Prabhakaran, and A. Sharma, A substructure based lower bound for eternal vertex cover number, Theor. Comput. Sci. 890, 87–104 (2021).
     
  8. K. Paul and A. Pandey, Some algorithmic results for eternal vertex cover problem in graphs, in WALCOM: Algorithms and Computation, Proc. 17th Int. Conf. and Workshops (Hsinchu, Taiwan, Mar. 22–24, 2023) (Springer, Cham, 2023), pp. 242–253 (Lect. Notes Comput. Sci., Vol. 13973).
     
  9. H. Araki, T. Fujito, and S. Inoue, On the eternal vertex cover numbers of generalized trees, IEICE Trans. Fundam. Electron. Commun. Comput. Sci. E98-A (6), 1153–1160 (2015).
     
  10. W. F. Klostermeyer and C. M. Mynhardt, Graphs with equal eternal vertex cover and eternal domination numbers, Discrete Math. 311 (14), 1371–1379 (2011).
     
  11. V. L. Beresnev, A. A. Melnikov, and S. Yu. Utyupin, Representation of the eternal vertex cover problem as a dynamic Stackelberg game, in Optimization and Applications, Rev. Sel. Pap. 14th Int. Conf. OPTIMA 2023 (Petrovac, Montenegro, Sept. 18–22, 2023) (Springer, Cham, 2023), pp. 3–13 (Lect. Notes Comput. Sci., Vol. 14395).
     
  12. V. L. Beresnev, A. A. Melnikov, and S. Yu. Utyupin, Stability of vertex covers in a game with finitely many steps, Diskretn. Anal. Issled. Oper. 31 (2), 28–45 (2024) [Russian] [J. Appl. Ind. Math. 18 (2), 206–215 (2024)].