The eternal vertex cover problem is a variant of the classical vertex cover problem where a set of guards on the vertices have to be dynamically reconfigured from one vertex cover to another in every round of an attacker-defender game. The minimum number of guards required to protect a graph from an infinite sequence of attacks is the eternal vertex cover number (evc) of the graph. It is known that, given a graph $G$ and an integer $k$, checking whether $evc(G) \le k$ is NP-Hard. However, for any graph $G$, $mvc(G) \le evc(G) \le 2 mvc(G)$, where $mvc(G)$ is the minimum vertex cover number of $G$. Precise value of eternal vertex cover number is known only for certain very basic graph classes like trees, cycles and grids. Though a characterization is known for graphs for which $evc(G) = 2mvc(G)$, a characterization of graphs for which $evc(G) = mvc(G)$ remained open. Here, we achieve such a characterization for a class of graphs that includes chordal graphs and internally triangulated planar graphs. For some graph classes including biconnected chordal graphs, our characterization leads to a polynomial time algorithm to precisely determine $evc(G)$ and to determine a safe strategy of guard movement in each round of the game with $evc(G)$ guards. It is also shown that deciding whether $evc(G) \le k$ is NP-Complete even for biconnected internally triangulated planar graphs.
from cs updates on arXiv.org https://ift.tt/2EwlYaP
//
0 comments:
Post a Comment