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

 また前回から長い時間がたってしまいました。一体いつ終わるのか、私も少々疑問に思っているこのP=NP?問題を扱った連載。本当に頭の良い方々のおかげです。つまり、ほら。自分の健康問題を他人のせいにしてはいけませんが、本当に参っちゃうんですよ、いろいろと絡まれて。なんたって頭が良いうえにお育ちもよいらしいですから、その分アレでですね。私みたいな人間とは頭を下げないと口も聞いてくれないらしいですし、不幸が楽しくて仕方がないとまでおっしゃるんですから、仕方ありません、私は私なりにがんばるほかないと思っているところ。おまけに、別件で計算機理論の入門の記事をブログに書いて、もう関係ないけど、ソニー製品を買ってね、とお願いしたにも関わらず、なぜかソニーの赤字幅が増えてるらしく、私もまた及ばずながら少々何かしないといけないかと。

前置きが長い上に面白くなくてすいません。え？面白くないのはいつもだって？そ、それは言わない約束じゃないですか。

さて、気を取り直して、前回（ 「頂点カバー問題がNP完全であるということ　その１　その２　その３」） まで、3SATの問題がどのようにしてVC（頂点カバー）の問題に置き換えられるか、そして、置き換えたあとのグラフG=(V,E)がK≦|V|においてをVCの問題が3SATの問題を満たしているか解説をしてきました。

今回は、前回とは逆に、3SATの問題すなわち、リテラルの集合U={u1,u2,…,un}と節集合C={c1,c2,…,cm}が与えられた場合、真理関数t:U→{T,F}がCを充足するとした場合、3SATからVCの問題へと変換されたグラフG=(V,E)とK≦|V|で与えられるVCの問題が、節の部分集合W∈V,|W|≦KでVCであるということを述べたいと思います。

「頂点カバー問題がNP完全であるということ　その２」では、3SATの問題をVCの問題に変換する手続きを説明しました。

そこで、

　手順1.ではリテラルの集合Uを 部分グラフをTi={Vi,Ei}と表すとき

　　　　Vi={　ui,　￢ui　}
　　　　Ei={　{ui,￢ui}　}
　
と表すことにし、
　手順2．では、節の集合Cについて、部分グラフ 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かつa　[j]∈Vかつa3[j]∈V）
　　
とするのでした。

　手順3．では、以上の手順を用いて、頂点の集合Vが


と言う式で表されることを述べ、

　手順4．では、同様に枝の集合Eについて考えると、

　　　　　すべてのcj∈Cについて、cj={xj,yj,zj}と節を表すとき
　　　　　枝の部分集合を、
　　　　　　　
　　　　　　　E"j={　{a1[j],xj},　 {a2[j], yj}, 　{a3[j], zj}　}
　
　　　　　と表すことにすると、最終的には、



となり、K=n+2mと定義したのでした


さて、まず、上のViのなかから、真理関数tにおいて、真(T)になるものをVCのノードの集合Wとします。

そこで、E"jについて考えると、3SATの節cj={xj,yj,zj}が真理関数tで充足される、ということを考えると、最低でもxj,yj,zjのどれかが真理関数tにおいて真にならなければいけないということになります。したがって、E"jを満たすためには、a1[j],a2[j],a3[j]のいずれか二つがVCのノード集合Wに含まれていれば良いわけです。

ここで、|Vi|=n。また|E"j|=mより、多くてもa1[j],a2[j],a3[j]のいずれか二つが集合Wに含まれる必要があることから、2m個、すなわち、n+2m個のノードが集合Wに含まれ、K=n+2mと定義したことから|W|=Kを満たすことから、このときノード集合Wは|W|=KでのVCということを満たす、ということになるわけです。