最小の頂点被覆のサイズを求める問題

wikiの図がわかりやすい

以下の赤点が各グラフの最小の頂点被覆になっている

これはNP完全問題である

頂点被覆問題がNP完全問題であることのアプローチ

この問題がクラスNPに属することは明らか。

k個の頂点被覆を証拠として示せば良い

難しいのは、この問題がクラスNPの任意の問題から多項式時間還元だと示すこと

この問題が3SAT問題から多項式時間還元であることを示せばいい

なんでこれで必要十分なのかは知らん #??

3CNFな論理式\phiを、グラフG(V,E)とkに変換することを考える

Gがk個の頂点被覆を持つ時、\phiが充足可能に、なるように変換をする写像を考える

図解を3CNFをグラフGに変換して、最小の頂点被覆を求めるに書いた

証明 ref p.342

参考

証明が載っている