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 (defender) moves 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 with which the defender has a winning strategy is called the Eternal Vertex Cover Number of the graph G. On general graphs, the computational problem of determining the minimum eternal vertex cover number is NP-hard and admits a 2-approximation algorithm and an exponential kernel. The complexity of the problem on bipartite graphs is open, as is the question of whether the problem admits a polynomial kernel. We settle both these questions by showing that Eternal Vertex Cover is NP-hard and does not admit a polynomial compression even on bipartite graphs of diameter six. This result also holds for split graphs. We also show that the problem admits a polynomial time algorithm on the class of cobipartite graphs.
翻译:Eternal Vertex 封面问题是一个顶端覆盖问题的动态变体。 我们有一个两个玩家游戏, 将警卫放在一个图形的顶部。 在每一个动作中, 一个玩家( 攻击者) 攻击一个边缘。 在攻击后, 第二个玩家( defender) 将警卫沿着图形边缘移动, 使至少一个警卫沿着被攻击边缘移动。 如果这种移动不可能, 那么攻击者会赢。 如果辩护人能够捍卫图形, 对抗无限的攻击序列, 那么捍卫者会赢。 与辩护人有获胜策略的最少的警卫人数被称为图形 G 的 Enernal Vertex 封面号 。 在一般图表中, 确定最低永久顶部顶部覆盖数的计算问题是 NP- 硬度, 并承认一个 2 适应算法和指数内核。 双面图形上的问题是开放的, 问题是否包含一个多面直径的图形内核, 我们甚至用双面平面平面平面平面的平面平面的平面图也显示一个双面平面平面平面的平面平面平面的平面。