Standard

Stability of Vertex Covers in a Game with Finitely Many Steps. / Beresnev, V. L.; Melnikov, A. A.; Utyupin, S. Yu.

In: Journal of Applied and Industrial Mathematics, Vol. 18, No. 2, 3, 06.2024, p. 206-215.

Research output: Contribution to journalArticlepeer-review

Harvard

Beresnev, VL, Melnikov, AA & Utyupin, SY 2024, 'Stability of Vertex Covers in a Game with Finitely Many Steps', Journal of Applied and Industrial Mathematics, vol. 18, no. 2, 3, pp. 206-215. https://doi.org/10.1134/S1990478924020030

APA

Beresnev, V. L., Melnikov, A. A., & Utyupin, S. Y. (2024). Stability of Vertex Covers in a Game with Finitely Many Steps. Journal of Applied and Industrial Mathematics, 18(2), 206-215. [3]. https://doi.org/10.1134/S1990478924020030

Vancouver

Beresnev VL, Melnikov AA, Utyupin SY. Stability of Vertex Covers in a Game with Finitely Many Steps. Journal of Applied and Industrial Mathematics. 2024 Jun;18(2):206-215. 3. doi: 10.1134/S1990478924020030

Author

Beresnev, V. L. ; Melnikov, A. A. ; Utyupin, S. Yu. / Stability of Vertex Covers in a Game with Finitely Many Steps. In: Journal of Applied and Industrial Mathematics. 2024 ; Vol. 18, No. 2. pp. 206-215.

BibTeX

@article{2b454bdc7fc442c6ad968c9757eda4c6,
title = "Stability of Vertex Covers in a Game with Finitely Many Steps",
abstract = "The eternal vertex cover problem is a version of the graph vertex cover problem that canbe represented as a dynamic game between two players (the Attacker and the Defender) withan infinite number of steps. At each step, there is an arrangement of guards over the vertices ofthe graph forming a vertex cover. When the Attacker attacks one of the graph{\textquoteright}s edges, theDefender 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 adjacentones to obtain a new vertex cover. The Attacker wins if the Defender cannot build a new vertexcover after the attack. In this paper, we propose a procedure that allows us to answer the questionwhether there exists a winning Defender strategy that permits protecting a given vertex cover fora given finite number of steps. To construct the Defender strategy, the problem is represented asa dynamic Stackelberg game in which at each step the interaction of the opposing sides isformalized as a two-level mathematical programming problem. The idea of the procedure is torecursively check the 1-stability of vertex covers obtained as a result of solving lower-levelproblems and to use some information about the covers already considered.",
keywords = "dynamic Stackelberg game, eternal vertex cover, graph edge protection, stability check algorithm",
author = "Beresnev, {V. L.} and Melnikov, {A. A.} and Utyupin, {S. Yu}",
note = "The study is carried out within the framework of the state contract for the Sobolev Institute of Mathematics, project no. FWNF–2022–0019.",
year = "2024",
month = jun,
doi = "10.1134/S1990478924020030",
language = "English",
volume = "18",
pages = "206--215",
journal = "Journal of Applied and Industrial Mathematics",
issn = "1990-4789",
publisher = "Maik Nauka-Interperiodica Publishing",
number = "2",

}

RIS

TY - JOUR

T1 - Stability of Vertex Covers in a Game with Finitely Many Steps

AU - Beresnev, V. L.

AU - Melnikov, A. A.

AU - Utyupin, S. Yu

N1 - The study is carried out within the framework of the state contract for the Sobolev Institute of Mathematics, project no. FWNF–2022–0019.

PY - 2024/6

Y1 - 2024/6

N2 - The eternal vertex cover problem is a version of the graph vertex cover problem that canbe represented as a dynamic game between two players (the Attacker and the Defender) withan infinite number of steps. At each step, there is an arrangement of guards over the vertices ofthe graph forming a vertex cover. When the Attacker attacks one of the graph’s edges, theDefender 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 adjacentones to obtain a new vertex cover. The Attacker wins if the Defender cannot build a new vertexcover after the attack. In this paper, we propose a procedure that allows us to answer the questionwhether there exists a winning Defender strategy that permits protecting a given vertex cover fora given finite number of steps. To construct the Defender strategy, the problem is represented asa dynamic Stackelberg game in which at each step the interaction of the opposing sides isformalized as a two-level mathematical programming problem. The idea of the procedure is torecursively check the 1-stability of vertex covers obtained as a result of solving lower-levelproblems and to use some information about the covers already considered.

AB - The eternal vertex cover problem is a version of the graph vertex cover problem that canbe represented as a dynamic game between two players (the Attacker and the Defender) withan infinite number of steps. At each step, there is an arrangement of guards over the vertices ofthe graph forming a vertex cover. When the Attacker attacks one of the graph’s edges, theDefender 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 adjacentones to obtain a new vertex cover. The Attacker wins if the Defender cannot build a new vertexcover after the attack. In this paper, we propose a procedure that allows us to answer the questionwhether there exists a winning Defender strategy that permits protecting a given vertex cover fora given finite number of steps. To construct the Defender strategy, the problem is represented asa dynamic Stackelberg game in which at each step the interaction of the opposing sides isformalized as a two-level mathematical programming problem. The idea of the procedure is torecursively check the 1-stability of vertex covers obtained as a result of solving lower-levelproblems and to use some information about the covers already considered.

KW - dynamic Stackelberg game

KW - eternal vertex cover

KW - graph edge protection

KW - stability check algorithm

UR - https://www.scopus.com/record/display.uri?eid=2-s2.0-85201428060&origin=inward&txGid=94eed5645330785650ff3b67ffeb0633

UR - https://elibrary.ru/item.asp?id=68611698

UR - https://www.mendeley.com/catalogue/eada96b0-6b9f-3d66-9da1-b1630e4ed210/

U2 - 10.1134/S1990478924020030

DO - 10.1134/S1990478924020030

M3 - Article

VL - 18

SP - 206

EP - 215

JO - Journal of Applied and Industrial Mathematics

JF - Journal of Applied and Industrial Mathematics

SN - 1990-4789

IS - 2

M1 - 3

ER -

ID: 60747754