最小頂点カバー問題がNPにあるのはなぜですか

Question

Vijay V. Vaziraniによる近似アルゴリズムの最小頂点カバーの定義を参照しています。vazirani（page 23）：

は、 $ g $ の最小頂点カバーのサイズです。 $ k $ ？

とこの定義の直後、著者はこの問題が np にあると述べています。

私の質問：はい証明書？

確かに、当社の非決定論的アルゴリズムは、 $ v '$ によって示され、 $ v '$ は、多項式時のいくつかのカーディナリティの頂点カバーですが、 $ v' $ が最小多項式時間は？

Answer 1

$ v '$ x が最小のことを確認する必要はありません。 頂点カバーの決定版（あなたの質問に引用したもの）は、 $ k $ の頂点の頂点カバーがあるかどうかを決定するように頼みます。

$ v '$ が、インスタンス $ \ langle g=（v）の有効なyes-certificateです。、e）、k \ rangle $ あなたはそれをチェックするだけです：

• $ v '\ subseteq v $ 、
• $ | V '|\ le k $ 、
• $ \ forall（u、v）¥¥¥¥¥¥Neq¥Neq¥EmptySet $ 。