| Title | : | Introduction to Eternal Vertex Cover |
| Speaker | : | Saraswati Nanoti (IIT Gandhinagar) |
| Details | : | Tue, Feb 18, 2025 12:00 PM, @ Turing Hall |
| Abstract | : | In this talk, we discuss the ETERNAL VERTEX COVER problem. The ETERNAL VERTEX COVER problem is a dynamic variant of the vertex cover problem. We have a two player game in which guards are placed on some vertices of a graph. In every move, one player (the attacker) attacks an edge. In response to the attack, the second player (the defender) moves some of the guards along the edges of the graph in such a manner that at least one guard moves along the attacked edge. If such a movement is not possible, then the attacker wins. If the defender can defend the graph against an infinite sequence of attacks, then the defender wins. The minimum number of guards for which the defender has a winning strategy is called the eternal vertex cover number of the graph
G which is denoted by evc(G). This problem was introduced by Klostermeyer and Mynhardt in 2009. It was shown in this paper that evc(G) lies between mvc(G) and 2mvc(G) where mvc(G) denotes the size of a smallest vertex cover of the graph G. The characterization of graphs satisfying evc(G) = 2mvc(G) was also shown in this paper. The characterization of graphs with evc(G) = vc(G) was open (even for bipartite graphs). Also in 2010, Fomin et.al. showed that the ETERNAL VERTEX COVER problem is NP-hard. We will give a reduction which proves that the ETERNAL VERTEX COVER problem is NP-hard even on bipartite graphs of diameter 5. We give a characterization of bipartite graphs for which evc(G) = mvc(G). We will give new lower bounds for evc(G) for graphs in general and use them to characterize Konig graphs for which evc(G) = mvc(G). We will also give a characterization for graphs satisfying evc(G) = mvc(G). |