Some Algorithmic Results for Eternal Vertex Cover Problem in Graphs

Kaustav Paul¹ ; Arti Pandey¹

¹ Indian Institute of Technology Ropar

Journal of Graph Algorithms and Applications, Special issue on Selected Papers from the 17th International Conference and Workshops on Algorithms and Computation, WALCOM 2023 , Tome 28 (2024) no. 3, pp. 69-85.

Résumé

The eternal vertex cover problem is a variant of the vertex cover problem. It is a two-player (attacker and defender) game in which, given a graph $G=(V,E)$, the defender needs to allocate guards at some vertices so that the allocated vertices form a vertex cover. The attacker can attack one edge at a time, and the defender needs to move the guards along the edges such that at least one guard moves through the attacked edge and the new configuration still remains a vertex cover. The attacker wins if no such move exists for the defender. The defender wins if there exists a strategy to defend the graph against infinite sequence of attacks. The minimum number of guards with which the defender can form a winning strategy is called the eternal vertex cover number of $G$, and is denoted by $evc(G)$. Given a graph $G$, the problem of finding the eternal vertex cover number is NP-hard for general graphs and remains NP-hard even for bipartite graphs. We have given a polynomial time algorithm to find the Eternal vertex cover number in chain graphs and $P_4$-sparse graphs. We have also given a linear-time algorithm to find the eternal vertex cover number for split graphs, an important subclass of chordal graphs.

Détail

DOI : 10.7155/jgaa.v28i3.2972

Keywords: Eternal vertex cover, Chain graphs, Split graphs, Cographs