Eternal Connected Vertex Cover Problem in Graphs: Complexity and Algorithms

A variation of the vertex cover problem is the eternal vertex cover problem. This is a two-player (attacker and defender) game, where the defender must allocate guards at specific vertices in order for those vertices to form a vertex cover. The attacker can attack one edge at a time. The defender must move the guards along the edges so that at least one guard passes through the attacked edge (guard moves from one end point of the attacked edge to the another end point), and the new configuration still acts as a vertex cover. If the defender is unable to make such a maneuver, the attacker prevails. If a strategy for defending the graph against any infinite series of attacks emerges, the defender wins. The eternal vertex cover problem is to find the smallest number of guards with which the defender can develop a successful strategy. The same problem is referred as the eternal connected vertex cover problem if the following additional requirement is added: underlying vertices of each defensive configuration form a connected vertex cover. The smallest number of guards that can be used to create a successful defensive strategy, in this case, is known as the eternal connected vertex cover number and is denoted by the ecvc(G). The decision version of the eternal connected vertex cover problem is NP-hard for general graphs and it also remains NP-hard for bipartite graphs. In this paper, we proved that the problem is polynomial-time solvable for chain graphs and cographs. In addition, we proved that the problem is NP-hard for Hamiltonian graphs, and proposed a polynomial-time algorithm to compute eternal connected vertex cover number for Mycielskian of a given Hamiltonian graph.