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

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

Береснев В. Л., Мельников А. А., Утюпин С. Ю.
Дискретный анализ и исследование операций, 31, 2, 28–45 (2024)
Скачать статью

УДК 519.8 
DOI: 10.33048/daio.2024.31.797

Аннотация:

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

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

Литература:
  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. DOI: 10.2298/AADM151109021K.
     
  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. 17. P. 702–706. DOI: 10.1016/j.ipl.2010.05.029.
     
  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.; Vol. 13296). DOI: 10.1007/ 978-3-031-09574-0_5.
     
  5. Babu J., Prabhakaran V. A new lower bound for the eternal vertex cover number of graphs // J. Comb. Opt. 2022. V. 44. P. 2482–2498. DOI: 10.1007/ s10878-021-00764-8.
     
  6. 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. DOI: 10.1016/j.tcs.2021.08.018.
     
  7. 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. DOI: 10.1587/transfun.E98.A.1153.
     
  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.; Vol. 13973). DOI: 10.1007/ 978-3-031-27051-2_21.
     
  9. 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. (Petrovac, Montenegro, Sept. 18–22, 2023) Cham: Springer, 2023. P. 3–13. (Lect. Notes Comput. Sci.; V. 14395). DOI: 10.1007/978-3-031-47859-8_1.
     
  10. Bezanson J., Edelman A., Karpinski S., Shah V. B. Julia: A fresh approach to numerical computing // SIAM Rev. 2017. V. 59, No. 1. P. 65–98. DOI: 10.1137/141000671.
     
  11. COIN-OR Branch-and-cut solver. Towson: COIN-OR Found., 2023. URL: github.com/coin-or/Cbc (accessed Mar. 27, 2024).

Работа выполнена в рамках государственного задания Института математики им. С. Л. Соболева СО РАН (проект № FWNF–2022–0019).

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

E-mail: beresnev@math.nsc.ru

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

E-mail: melnikov@math.nsc.ru

Утюпин Степан Юрьевич
  1. Новосибирский гос. университет, 
    ул. Пирогова, 2, 630090 Новосибирск, Россия

E-mail: stepan.utyupin@gmail.com

Статья поступила 26 февраля 2024 г. 
После доработки — 14 марта 2024 г. 
Принята к публикации 21 марта 2024 г.

Abstract:

The eternal vertex cover problem is a version of the graph vertex cover problem that can be represented as a dynamic game between two players (the Attacker and the Defender) with an infinite number of steps. At each step, there is an arrangement of guards over the vertices of the graph forming a vertex cover. When the Attacker attacks one of the graph’s edges, the Defender must move the guard along the attacked edge from one vertex to the other. In addition, the Defender can move any number of other guards from their current vertices to some adjacent ones to obtain a new vertex cover. The Attacker wins if the Defender cannot build a new vertex cover after the attack. 

In this paper, we propose a procedure that allows us to answer the question, whether there exists a winning Defender strategy that permits protecting a given vertex cover for a given finite number of steps. To construct the Defender strategy, the problem is represented as a dynamic Stackelberg game in which at each step the interaction of the opposing sides is formalized as a two-level mathematical programming problem. The idea of the procedure is to recursively check the 1-stability of vertex covers obtained as a result of solving lower-level problems and to use some information about the covers already considered. 
Illustr. 6, bibliogr. 11.

References:
  1. W. F. Klostermeyer and C. M. Mynhardt, Protecting a graph with mobile guards, Appl. Anal. Discrete Math. 10 (1), 1–29 (2016), DOI: 10.2298/ AADM151109021K.
     
  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 (17), 702–706 (2010), DOI: 10.1016/j.ipl.2010.05.029.
     
  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), DOI: 10.1007/978-3-031-09574-0_5. 
     
  5. J. Babu and V. Prabhakaran, A new lower bound for the eternal vertex cover number of graphs, J. Comb. Opt. 44, 2482–2498 (2022), DOI: 10.1007/ s10878-021-00764-8.
     
  6. J. Babu, V. Prabhakaran, and A. Sharma, A substructure based lower bound for eternal vertex cover number, Theor. Comput. Sci. 890, 87–104 (2021), DOI: 10.1016/j.tcs.2021.08.018.
     
  7. 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), DOI: 10.1587/transfun.E98.A.1153.
     
  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), DOI: 10.1007/ 978-3-031-27051-2_21.
     
  9. 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., Petrovac, Montenegro, Sept. 18–22, 2023) (Springer, Cham, 2023), pp. 3–13 (Lect. Notes Comput. Sci., Vol. 14395), DOI: 10.1007/978-3-031-47859-8_1.
     
  10. J. Bezanson, A. Edelman, S. Karpinski, and V. B. Shah, Julia: A fresh approach to numerical computing, SIAM Rev. 59 (1), 65–98 (2017), DOI: 10. 1137/141000671.
     
  11. COIN-OR Branch-and-Cut solver (COIN-OR Found., Towson, 2023). URL: github.com/coin-or/Cbc (accessed Mar. 27, 2024).