A substructure based lower bound for eternal vertex cover number

• Published in: Theoretical computer science 2021-10, Vol.890, p.87-104
• Main Authors: Babu, Jasine, Prabhakaran, Veena, Sharma, Arko
• Format: Article
• Language: English
• Subjects: Cactus graphs; Chordal graphs; Eternal vertex cover; Substructure property
• ISSN: 0304-3975; 1879-2294
• DOI: 10.1016/j.tcs.2021.08.018

•We first define substructure property in the context of eternal vertex cover problem.•Using the property, we derive a new lower bounding technique for the problem.•We obtain a linear time algorithm for solving the problem for cactus graphs.•We obtain a new quadratic time algorithm for solving the problem for chordal graphs.•We derive an explicit formula for the eternal vertex cover number of cactus graphs. 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.