为什么要最小的顶点封面问题是np

Question

我指的是来自vijay V.Vazirani的书近似算法的最小顶点封面问题的定义（第23页）：

是 $ g $ 的最小顶点封面的大小，最多 $ k $ ？

而且在此定义后，作者指出此问题在 np 中。

我的问题：什么是是证书？

事实上，我们的非确定性算法可能猜测顶点的子集，由 $ v'$ ，我们可以验证 $ V'$ 是多项式时间中的一些基数的顶点封面，但是如何怎样才能显示 $ v'$ 是多项式时间中的最小？

Answer 1

您不必验证 $ v'$ 最小。 顶点封面的决定版本（在您的问题中引用）只要求您决定最多的大多数 $ k $ 的顶点封面。

要验证 $ v'$ 是一个实例 $ \ langle g=（v，e），k \ rangle $ 您只需检查：

• $ v'\ subseteq v $ ，
• $ | v'|\ Le K $ ，和
• $ \ forall（u，v）\在e，\ {u，v \} \ cap v'\ neq \ imptyset $