頂点カバー問題がNP完全であるということ その２

疲れていますか？私は疲れています。いわばご乱心です。なにがと聞かれても困りますが。そういうわけで今回は、寒さ厳しい折ということもあってよけいに寒くなるようなそういう無駄な部分を省こうと思います。ここまで、いろいろ意味を問われても困ります。

　

前回、頂点カバー問題（以下VCと略す）がクラスＮＰであると言うことをお話ししました。VCがＮＰ完全であると言うためには、ＮＰ完全であるという問題、今回はそれが3SATとなりますが、それと同等な問題である（SAT∝VCと表記する）ということを証明すれば良い訳です。

　

大まかな方法論としては、3SATの問題（「３SAT　その１」などを参照下さい）をVCの問題に翻訳します。

　

3SATはすべてのリテラル（ここではブール変数と同じと考えても可）の集合U={u1,u2,…,un}と、各節の要素の数が3つのブール変数に固定された節の集合C={c1,c2,…,cm}で一般的に表されます。

一方、VCについては、ノードの集合をV、枝の集合をEとしたとき一般的なグラフGをG={V,E}と表しすことにし、これがVCとして成立するノードの数をK（K≦｜V｜）と定義することにします。

3SATの問題をVCに翻訳するためにもう一つ、グラフＧをいろいろな部分集合の和であると定義しておきます。

　

このような準備をしてから、実際の翻訳作業に入ります。

　

　

　

　手順1.　3SATのリテラルui∈Uを部分グラフで表すことを考える

　　　　　そのような部分グラフをTi={Vi,Ei}と表すとき、Vi={ui,￢ui},Ei={{ui,￢ui}}とする

　

　　　　　このようにした場合、G={V,E}の頂点カバーであるようなノードの集合V'には
　　　　　uiか￢uiのどちらかが必ず含まれることになる　　　

　

　手順2．次に3SATの節cj∈Cについて同様のことを考え、そのような部分グラフを
　　　　 Sj={V'j,E'j}と表すこととすると、V'jとE'j次のように考えられる
　　　　　　
　　　　　　V'j={　a1[j],　a2[j],　a3[j]　},
　　　　　　E'j={　{a1[j], a2[j]},　 {a2[j], a3[j]}, 　{a3[j], a1[j]}　}

　

　　　　　ここで、a1[j], a2[j], a3[j]は新しく導入されたノードの表記ではあるが、
　　　　　当然ながら、a1[j]∈Vかつa２[j]∈Vかつa３[j]∈Vである

　　

　　　　　また、手順1で表したリテラルのときと同様に、このような場合
　　　　　G={V,E}の頂点カバーであるようなノードの集合V'には、
　　　　　a1[j], a2[j], a3[j]の三つのノードのうち少なくても二つのノードが
　　　　　含まれなければならない

　

　手順3．　G={V,E}においてノードの集合Vは以上で定義されたものですべて表される
　　　　　すなわち、

　　　　　　　

　　　　　　　　　　（※2014年5月7日　V'jの和集合の添え字がmでは無くnになっていました。
　　　　　　　　　　　　                      1≦j≦m　ですので、正しくはmです。お詫びして訂正いたします）

　手順4．　最後にG={V,E}において枝の集合Eについて考えると
　　　　　　すべてのcj∈Ｃについて、cj={xj,yj,zj}と節を表すとき
　　　　　　枝の部分集合を
　　　　　　　
　　　　　　　E"j={　{a1[j], xj},　 {a2[j], yj}, 　{a3[j], zj}　}
　
　　　　　と表すことにする

　　　　　こうしたときグラフＧの枝の集合Eを次のように定義する

　

　　　　　

　　　　　　　　（※2014年5月7日　上の図表の式と同じくE'jおよびE''jの和集合の添え字が
                                          mでは無くnになっていました。お詫びして訂正いたします）

また、ここでK=n+2mと定義する

　

　

以上のように翻訳することは明らかに多項式時間以内に可能だということがわかると思います。

　

今回は定義ばかりとなってしまいましたが、このような翻訳作業ということは、Cookの定理やSATを3SATに変換するというところでやったことにも似ています。

　

残りは、このようにして翻訳した結果がVCと同等だということを証明すればいいわけですが、それは次回ということで。

　

それにしてもうっぴょぴょん（乱心）

（※2014年5月7日　手順１.～手順4.までの文字を太線に変更）