graph - 最小顶点覆盖的一种变体

Question

在我的研究中，我遇到了以下顶点覆盖问题的变体：

给定一个图 G，一个顶点 v 和一个数 k，来决定 G 是否有一个包含 v 的大小为 k 的顶点覆盖。

我搜索了所有文献，找不到类似的问题。我对这个问题的复杂性感兴趣（我已经证明它对于 $P^NP[long]$ 是完整的）。

问题是你见过这种顶点覆盖问题的变体吗？你怎么称呼这个问题？

Answer 1

给定一个图 G 和一个整数K，判断 G 是否有大小K为顶点覆盖的决策问题是最小顶点覆盖问题。它是NP完全的。

如果事实上，您描述的问题与那个问题没有区别。那是因为如果你已经包含了顶点 v，你可以删除 v 和所有以 v 为端点的边。接下来你应该做的是决定你是否可以用k-1顶点覆盖左子图。