A Substructure based Lower Bound for Eternal Vertex Cover Number.

Abstract The eternal vertex cover (EVC) problem is to compute the minimum number of guards to be placed on the vertices of a graph so that any sequence of attacks on its edges can be defended by dynamically reconfiguring the guards. The problem is NP-hard in general and polynomial time algorithms are unknown even for simple graph classes like cactus graphs and bipartite graphs. A major difficulty is that only few lower bounds, other than the trivial lower bound of vertex cover, is known in general and the known bounds are too weak to yield useful results even for the graph classes mentioned above. We introduce the notion of substructure property in the context of the EVC problem and derive a new lower bounding technique for the problem based on the property. We apply the technique to cactus graphs and chordal graphs and obtain new algorithms for solving the eternal vertex cover problem in linear time for cactus graphs and quadratic time for a family of graphs that includes all chordal graphs and cactus graphs.