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 turns. At each turn, there is an arrangement of guards over the vertices of the graph, forming a vertex cover. The Attacker attacks one of the graph’s edges, and the Defender must move the guard along the attacked edge from one vertex to another. 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 an attack. The eternal vertex cover problem is to determine the smallest number of guards for which the 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 resistant to attack. The results of the computational experiment on the stability of various vertex covers of random graphs against attacks are presented.

Cite: Utyupin S. , Melnikov A. , Beresnev V.
Representation of the Eternal Vertex Cover Problem as a Dynamic Stackelberg Game
XIV International Conference Optimization and Applications 18-22 Sep 2023