论文标题
永恒的顶点覆盖在两部分和联合三分线图上
Eternal Vertex Cover on Bipartite and Co-Bipartite Graphs
论文作者
论文摘要
永恒的顶点覆盖问题是顶点覆盖问题的动态变体。我们有一个两个玩家游戏，其中的警卫在图形的某些顶点上放置。在每一步，一个玩家（攻击者）都会攻击边缘。为了响应攻击，第二名球员（防守者）以沿图的边缘移动守卫，以至于至少一个后卫沿攻击的边缘移动。如果不可能进行这样的运动，那么攻击者将获胜。如果防守者可以防御无限攻击序列，则防守者将获胜。 防守者拥有获胜策略的最小卫队数量称为图G的永恒顶点覆盖码。在一般图中，确定最小永恒顶点覆盖码的计算问题是NP-HARD，并接受了2个附属的近似算法和指数kernel。问题上的问题的复杂性是打开的，问题是否接受多项式内核的问题也是如此。 我们通过表明永恒的顶点覆盖物为NP螺旋，即使在直径六的两分图上也不接受多项式压缩，我们解决了这两个问题。我们还表明，该问题允许在鹅卵石图类别上使用多项式时间算法。
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. We also show that the problem admits a polynomial time algorithm on the class of cobipartite graphs.
