東大 生物情報学科、学部生の備忘録

東京大学の学生です。日々の気づき、学び、つまづいたことをメモにします。

MENU

＜NP 完全性 (Karp's Reduction)＞3-SAT から Vertex Cover への多項式時間還元について（polynomial reduction 3-SAT to VC）

情報科学・数学

はじめに

大学で学んだ多項式時間還元について、日本語記事でわかりやすいものが見つからなかったため、ここに記す。数ヶ月後におそらく試験で出題されるので、その試験対策としても。 blog 末尾でも述べるつもりであるが、Garey と Johnson による黒い本 Computers and intractability. を参考にしている。

解くべき問題の整理

Vertex Cover を判定問題にする必要がある。 n, mを与えられた自然数とし、命題を以下のように定める。

  • 命題 VC: K = n + 2m の頂点からなる被覆 VC が存在する。
  • 命題 3-SAT: 「リテラルの数、節の数がそれぞれ n, m である論理積標準形 f が充足可能である。」

3-SAT から VC へ多項式時間還元可能であることを示す。

3-SAT から VC の多項式時間変換

n, m, f が与えられた時の 3-SAT を K = n + 2m の VC 問題に変換する。リテラルは x_1, x_2, ..., x_n とし、各節は l_1, l_2, ..., l_m とする。 ^\forall i, l_i は任意の三つのリテラルの論理和である。例えば l_1 = (\bar{x_1}, x_2, x_n) のようになっている。

n, m, f から、図１のようなグラフ G(f) を作成する。 グラフ G は n 組のリテラルノードペアと m 個のクロースノードガジェットからなる。両者について詳しく説明する。

  • n 組のリテラルノードペア： ^\forall i, x_i, \bar{x_i} のノードを一つずつ作成し、両者を一つの辺で結んだもの
  • m 個のクロースノードガジェット： ^\forall i, l_i を構成する三つのリテラル a, b, c のノードを作成し、それぞれ辺で結んだもの。辺は {a, b}, {b, c}, {c, a} のちょうど三つである。
  • リテラルノードペアとクロースノードガジェットについて、各ガジェット l_i に対して、それを構成するノード a, b, c と、リテラルノードペアにおける a, b, c の間にそれぞれ辺をちょうど一つ結ぶ。 l_1 = \lbrace x_1, x_2, \bar{x_3} \rbrace のとき、リテラルノードペアの x_1, x_2, \bar{x_3} と対応するものの間にそれぞれちょうど一つの辺を作成する。

実際のグラフは以下のようになる。（いずれ追記します。）

すると、このグラフ G(f) の頂点被覆は自明に以下の性質を持つ。

  • リテラルノードペアの辺を被覆するために、リテラルノードペアの少なくとも一方は頂点被覆集合に含まれる。少なくとも n 個は頂点被覆集合 VC に含まれる。
  • クロースノードガジェットの辺を被覆するために、各三つの頂点のうち、少なくとも 2 つは頂点被覆集合 VC に含まれる。

このことから、最小頂点被覆集合の大きさは K = n + 2m であることが導かれる。また逆に、ある頂点被覆集合 V のサイズが K = n + 2m であるとき、以下が成立する。すなわち、

  • 各リテラルノードペア（ x, \bar{x}）について、ちょうどどちらか一つが V に含まれる。
  • 各クロースノードガジェットの三つの頂点のうち、ちょうど二つが V に含まれる。

これらを確認した上で、以下で 「論理積標準形 f を満たす真理値割当が存在する \Leftrightarrow グラフ G(f) はサイズ K = n + 2m 以下の頂点被覆集合が存在する」を示す。

論理積標準形 f を充足する真理値割当が存在する \Rightarrow グラフ G(f) はサイズ K = n + 2m 以下の頂点被覆集合が存在する

論理積標準形を充足する真理値割当を Assignment^* とする。 十分条件「論理積標準形 f を満たす真理値割当が存在する \Rightarrow グラフ G(f) はサイズ K = n + 2m 以下の頂点被覆集合が存在する」を示す。初めに、頂点集合 V を空集合とする。

  1. 真理値割当 Assignment^* をリテラルノードペアに反映する。つまり、リテラルノードペア (x_i, \bar{x_i}) については、 x_i が真であればノード x_i を V に加え、そうでなければノード \bar{x_i} を V に入れる。
  2. G(f) の作成ルールと Assignment^* が f を充足することから、各クロースノードガジェット l_i のうち少なくとも一つのノードは真であることが保証されており、その真となっているノード以外の 2 つのノードを V に入れる。（ l_i に真となっているノードが複数ある場合はそのうち一つを選び、それ以外の二つのノードを V に入れる。）

ここまでの段階で V のサイズは n + 2m である。V が頂点被覆集合であることを示せば、十分性は示せたことになる。

  1. V が頂点被覆集合であるかということについて考える。 まず、各リテラルノードペア (x_i, \bar{x_i}) においては、どちらか一方が V に含まれていることから、両者をつなぐ辺 { x_i, \bar{x_i}} は被覆されている。
  2. 各ガジェット l_i の三つの頂点 a, b, c のうち二つが V に含まれていることから、ガジェット内の三つの辺はどれも被覆されている。
  3. 各ガジェットについて、それとリテラルノードペアを結ぶ三つの辺は被覆されている。ガジェット l_i の三つの頂点 a, b, c のうち、少なくとも一つは真が割り当てられており、それを a とする。b, c はガジェット l_i に含まれるノード a はリテラルノードペア ( a, \bar{a}) のノード a と辺を共有する。リテラルノードペアにおいて a は真が割り当てられているので、V に含まれている。したがって、リテラルノードペアのノード a とガジェットのノード a を結ぶエッジは被覆されている。 G(F) の生成ルールから、ガジェット l_i の三頂点のうち a 以外の2 点、つまり頂点 b, c は V に含まれている。したがって、ガジェット l_i の b とリテラルノードペアの b を結ぶ辺は被覆される。c についても同様に被覆される。

以上より、V はサイズ K = n + 2m の頂点被覆集合であることが示された。 したがって、十分性を示すことができた。

論理積標準形 f を充足する真理値割当が存在する \Leftarrow グラフ G(f) はサイズ K = n + 2m 以下の頂点被覆集合が存在する

必要性の証明を行う。

下準備

何らかの f から生成されたグラフ G(f) が与えられたとし、そのグラフ G(f) にサイズ K = n + 2m 以下の頂点被覆集合が存在するとする。グラフ G(f) は三頂点からなるガジェットと、二頂点からなるペアの二つの構造が繋がっているものとみなせて、二頂点からなるペアの数を n, ３頂点からなるガジェットの数を m とし、n 個のペアのうち i 番目のペアをそれぞれ x_i, \bar{x_i} とする。ペア p_i とガジェット l_j について、ペアのノード x とガジェットのノード a が辺を共有しているとき、「a は x に対応している」とする。各ガジェットの各頂点は、ちょうど一つのリテラルノードと辺を共有することから、各ガジェットの各頂点について、ちょうど一つのリテラルノードが対応づけれらる。そうして対応づけが完了したとする。すると、ガジェット l_i\, (^\forall i) について、 l_i[0, l_i[1], l_i[2] ] に対応するリテラルノードがそれぞれ a, b, c であるとき、ガジェット l_i は論理和 {a, b, c} に対応すると呼ぶことにする。すると、G(f) の元となった論理積標準形 f は、各ガジェットに対応する論理和の論理積で与えられることがわかる。 ここまでの段階で、G(f) から n, m, f をただ一つに求める（復元する）ことができた。

ペアを { x_i, \bar{x_i}} か { \bar{x_i}, x_i } のどちらにするかで f は 2 通りあるように思えるが、どちらであっても充足可能性には影響しないため、この決定の仕方は問題にはならない。

以上の過程を経て G から生成された論理積標準形を f(G) と表すことにする。

証明のメイン

G(f) から上の段落のようにして n, m, f を求めたとする。この G は仮定より、サイズ K = n + 2m 以下の頂点被覆集合 V をもつが、これは先ほどの議論：

このグラフ G(F) の頂点被覆は自明に以下の性質を持つ。

  • リテラルノードペアの辺を被覆するために、リテラルノードペアの少なくとも一方は頂点被覆集合に含まれる。少なくとも n 個は頂点被覆集合 VC に含まれる。
  • クロースノードガジェットの辺を被覆するために、各三つの頂点のうち、少なくとも 2 つは頂点被覆集合 VC に含まれる。

このことから、最小頂点被覆集合の大きさは K = n + 2m であることが導かれる。また逆に、ある頂点被覆集合 V のサイズが K = n + 2m であるとき、以下が成立する。すなわち、

  1. 各リテラルノードペア（ x, \bar{x}）について、ちょうどどちらか一つが V に含まれる。
  2. 各クロースノードガジェットの三つの辺のうち、ちょうど二つが V に含まれる。

より、最小頂点被覆集合に一致し、各リテラルノードペアのちょうど一方と、各クロースノードガジェットの三つの頂点のうちちょうど二つが V に含まれるということがわかる。

まず、各リテラルノードペアについてはちょうど一つのノードが V に含まれているので、含まれているノードに対応するリテラルを真とする。各リテラル x_i について、 x_i, \bar{x_i} の一方のみが真に割り当てられ、矛盾は存在しない。この真理値割当を Assignment と呼ぶことにする。

こうして得られた割当 Assignment が G(f) から一意に生成された論理割当 f(G) を充足することを示せば、必要性が示せたことになる。これは、「各ガジェットにおいて、どれか一つの頂点は真を割り当てられたリテラルノードと辺を共有する」ことを示すことと同値である。それを、背理法によって証明する。 帰無仮説：「あるガジェット l_i = [a, b, c] で、どの頂点も、真を割り当てられたリテラルノードと辺を共有しないものが存在する」を仮定する。まず、V が最小頂点被覆であることから、任意のガジェットは、三つの頂点のうち、V に含まれていない頂点がちょうど一つ存在する。 当然、そのガジェット l_i = [a, b, c] においても V に含まれていない頂点が存在し、それに対応するリテラルが a であるとする。帰無仮説より、リテラルノードペアにおいて、a ではなく、 \bar{a} が V に含まれていることから、 ガジェットの頂点 a とリテラルノードペアの頂点 a を結ぶ辺は被覆されていないことになる。これは、V が頂点被覆集合であることに矛盾する。 従って、帰無仮説は棄却された。したがって、V から生成された真理値割当 Assginment は、グラフ G から生成された論理積標準形 f(G) を充足するということが示された。 この瞬間、必要性は証明された。

必要十分性についてと多項式時間還元であることの証明

必要性と十分性が示されたことから、以下の命題は真である。すなわち、 「論理積標準形 f を満たす真理値割当が存在する \Leftrightarrow グラフ G(f) はサイズ K = n + 2m 以下の頂点被覆集合が存在する」は示された。

ここで、G(f) や f(G) の変換は、多項式時間で行われていることが簡単に確認できる。 したがって、3-SAT 問題は頂点被覆集合問題に多項式時間還元可能であるということが示された。 以上。

まとめ

かなり丁寧に書きました。適宜ブラッシュアップします。例えば、図は面倒なのでまだ作っていませんが、いずれ追加します。 なかなかの完成度で証明を書けたと思うが、これをレポートなどに転用しないように。コピペは誰も幸せになりません。

参考文献

Garey, Michael R., and David S. Johnson. "Computers and intractability." A Guide to the (1979).

関連記事

ut-bioinformatic.hatenablog.jp