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

　ソチオリンピックでの日本選手の活躍に心励まされる今日この頃。いくら私でも、さすがに少しがんばろうかなという気にもなってきました。どこまで続くか分からないというところが私らしいところですが。

　

さて、前回（頂点カバー問題がNP完全であるということ　その２）は、3SAT∝VCを証明するために、3SATの問題をVCの問題に翻訳するということをやりました。今回は、この、（リテラルの集合Uと節集合Cで表される）3SATの問題が、（グラフG=(V,E)といくつの頂点を選ぶかを表す数Kで表される）VCの問題と同等ということをこれから二回に分けて証明していきます。

　

【Kについて】
    まず、VCの問題におけるノードの集合W∈V（本来的にはWはV'と書きたいところですが、以下紛らわしいのでWとします）が|W|<Kを満たす頂点カバーだったとします。

　

①　前回のリテラルui∈U (1≦i≦n)を変換した部分グラフ Ti={Vi,Ei) について注目すると、部分グラフTiのノードの集合Viのどちらかのノードが含まれていないといけませんので、ノード集合Wとノード集合∪Viの共通部分（積集合）には少なくてもn個のノードが含まれています。

　
②　同様に、前回の節cj∈C(1≦j≦m)を変換した部分グラフSj={V'j,E'j}のうち、少なくても2個のノードがWに含まれなければなりませんので、ノード集合Wとノード集合∪V'jの積集合には少なくても2m個のノードが含まれます。

　

　|W|=Kでは、前回K=n+2mと定義しました。したがって、∪Viからはちょうどn個、∪V'jからはちょうど2m個のノードがWに含まれていることが分かります。

　
（※2014年5月7日　ノード集合Wとノード集合∪V'jの積集合のノードの数をｍ個と説明していましたが、正しくは2mこの間違いです。お詫びして訂正いたします）　

【VCの問題が3SATを満たしているか】
　ところで、いま3SATの問題におけるリテラルの集合Uの真理関数t:U→{T,F}を次のように定義する事とします。

　

　　　　

　　　　　　　　　　　　                                 
　ここで、Cj∈Cとしたとき、上記の真理関数tがCjを充足しているかどうかについて考えます。

　

　いま、前回の手順2で次のように定義しました。

　

　　　　 Sj={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]∈Vかつa2[j]∈Vかつa3[j]∈V)

　

　手順4では、すべてのcj∈Cについて、cj={xj,yj,zj}と節を表すとき
　　　　　　枝の部分集合を
　　　　　　　
　　　　　　　E"j={　{a1[j], xj},　 {a2[j], yj}, 　{a3[j], zj}　}
　
と表すことにし、最後に、こうしたときグラフGの枝の集合Eを

　　　　　　

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

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

　　　　　　　　

と定義しました。

　

　上記【Kについて】②においても記述していますが、WにはV'jのノードのうちすくなくても二つが含まれます。しかし、K=n+2mと定義されていますから、E''を満たすためには、最低でももう一つのノードが、手順4のcj={xj,yj,zj}のいずれかのノードでなければならず、したがって、cjに含まれる頂点はVCの問題を満たす部分集合Wであるということを満たさなければならないという事が分かります。

　今回はここまでにしましょう。次回は、3SATの問題が逆にVCをみたしているかを考えてみます。

　

葛西選手の妹さまの御快癒と日本選手団のみなさまのご活躍を祈念いたしまして。