次の問題の削減を見つける必要があります。
Vertex Cover- 与えられた (G=(V, E), k)-> G は無向グラフであり、E のすべてのエッジをカバーするサイズ k の S (V のサブグループ) が必要です。
Hal Vertex Cover- 与えられた (G=(V', E'), k')-> G は無向グラフです。また、E' のエッジのちょうど半分をカバーするサイズ k' の S' (V' のサブグループ) が必要です。
その方法と、Karp-Reduction が真になる理由 (証明の 2 つの方向) を教えていただければ幸いです。
ありがとうございました。