Abstract: The eternal vertex cover problem is a variant of the graph vertex cover problem that can be represented as a dynamic game between two players (Attacker and 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. Attacker attacks one of the graph’s edges, and Defender must move the guard along the attacked edge from one vertex to another. In addition, Defender can move any number of 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. In this paper, we propose a procedure that allows us to answer the question whether there is a winning strategy for Defender that allows protecting a given vertex cover within a given finite number of steps. To construct a strategy of Defender, the problem is represented as a dynamic Stackelberg game, at each step of which, 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 the lower-level problems, and to use some information about the covers already considered. Computational experiments demonstrates results from which it can be assumed that most random covers either have a high degree of stability or are unstable.

Cite: Utyupin S. , Мельников А.А. , Береснев В.Л.
Stability of vertex covers in a game with a finite number of steps
XXIII International Conference Mathematical Optimization Theory and Operations Research 30 Jun - 6 Jul 2024