Abstract: Eternal vertex cover problem is a variant of the graph vertex cover problem that can be considered as a dynamic game between two players (Attacker and Defender) with an infinite number of turns. At each turn, there is an arrangement of guards over the vertices of the graph, forming a vertex cover. Attacker attacks one of the graph’s edges, and Defender must move the guard along the attacked edge from one vertex to another. Additionally, Defender can move other guards from their current vertices to some adjacent ones to obtain a new vertex cover. Attacker wins if Defender cannot build a new vertex cover after an attack. The eternal vertex cover problem is to determine the smallest number of guards and their placement such that Attacker has no sequence of attacks leading to a win. We consider the eternal vertex cover problem as a dynamic Stackelberg game. At each turn of the game, a vertex cover is considered and the optimal solution of the bi-level programming problem is calculated, which allows to determine whether the given vertex cover is stable against a single attack (1-stable). The results of the computational experiment on checking the 1-stability of various vertex covers of random graphs are presented.

Cite: Beresnev V. , Melnikov A. , Utyupin S.
Representation of the Eternal Vertex Cover Problem as a Dynamic Stackelberg Game
In compilation Optimization and Applications : 14th International Conference, OPTIMA 2023, Petrovac, Montenegro, September 18–22, 2023, Revised Selected Papers. – Springer., 2023. – C.3-13. – ISBN 9783031478598. DOI: 10.1007/978-3-031-47859-8_1 Scopus OpenAlex

Dates:

Published print:	Nov 10, 2023
Published online:	Nov 10, 2023

Identifiers:

Scopus:	2-s2.0-85177210702
OpenAlex:	W4388522856

Citing:

DB	Citing
OpenAlex	1
Scopus	1

Altmetrics: