最小頂点被覆問題

vertex cover problem

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

wikiの図がわかりやすい

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

https://upload.wikimedia.org/wikipedia/commons/thumb/b/bd/Minimum-vertex-cover.svg/200px-Minimum-vertex-cover.svg.png

これはNP完全問題である

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

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

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

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

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

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

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

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

証明 ref 『計算理論の基礎 3』.icon p.342

参考

証明が載っている