NP完全性と多項式時間還元

下の図は、あるライトノベルの登場人物たちの関係を抜き出したものです。1つの文の中に2人以上の人物が登場したときに、その人たちの間に線を引いただけの単純なルールで作られています。

この図の線は「同じ文に登場した」という観測を表すだけで、知り合い・友人・好意などを直接証明するものではありません。以下の仲良しグループのたとえでは、辺を「互いに知り合い」と読む別のモデルを考えます。

主人公「マイン」を中心に、いくつかのグループ（コミュニティー）ができているのが見て取れます。家族や友人、職場など、現実の人間関係にも似た塊があります。

さて、このような関係図の中で、特に注目したいのが「そのグループに属する全員が、互いに直接知り合いである」ような、非常に結びつきの強いグループです。このような特別なグループ、つまり完全部分グラフ（どの2頂点も互いに辺で結ばれた部分グラフ）をなす頂点集合のことを、グラフ理論の言葉で「クリーク」と呼びます。

上の図は、それぞれ2人、3人、4人、5人のメンバー全員が互いに知り合い（辺で結ばれている）の「クリーク」です。クリークは「強固な仲良しグループ」と言えます。\(k\) 人のクリークでは、どの2人の組も辺で結ばれているので、辺の数は \(\frac{k(k-1)}{2}\) 本です（図の1本、3本、6本、10本）。人間関係の分析だけでなく、SNSのコミュニティ発見や、タンパク質の相互作用ネットワークの解析など、様々な分野でこの「密な構造」を見つけることが重要になります。

この「クリーク」を探す問題を、コンピューターに解かせるための形式的な問いとして定義したものが「クリーク問題」です。

これは「Yes/No」で答えるシンプルな決定問題です。 以下のグラフ \(G\) を例に、問題を具体的に見てみましょう。

一方で、「このグラフで、最大何人の『全員知り合い』グループが作れますか？」という問題は最大クリーク問題と呼ばれます。決定問題であるクリーク問題を繰り返し使えば、最大クリーク問題も解けます。具体的には、\(k=1,2,\ldots,n\) と大きくしながら「サイズ \(k\) のクリークはあるか？」を問い、はじめてNoが返る直前の \(k\) が最大サイズです。すべてYesなら最大サイズは \(n\) です（頂点数 \(n\) に対し高々 \(n\) 回の問い合わせで済み、二分探索ならさらに少なくできます）。決定問題が解ければ最大化問題も多項式回の呼び出しで解ける、という関係です。

SAT問題とは、与えられた論理式を真（1）にするような変数の割り当てが存在するかどうかを判定する問題でした（前章）。

例えば、\((x + \bar y) \cdot (\bar x + y)\) のような論理式が与えられます。この式全体を真（1）にするには、AND（\(\cdot\)）で結ばれた \((x + \bar y)\) と \((\bar x + y)\) の両方を真にする必要があります。

ここで用語を確認します。

SAT問題は「すべての節を同時に満たす(真にする)ことは可能か？」という問題です。

さて、話をSATからクリークへの還元に戻しましょう。以下の論理式 f に関するSAT問題を例に、翻訳のプロセスを体験します。

この式には3つの節があります。このSAT問題の目標は、3つの節すべてを 1 にする x, y, z の組み合わせを見つけることです。

Step 1: 節ごとにリテラルを頂点として配置する まず、節ごとにグループを作り、リテラルの出現ごとに1頂点を描きます。同じ \(y\) でも、第1節の \(y\) と第3節の \(y\) は別の頂点です。変数は同じでも、「どの節の代表を選ぶか」を区別するためです。

Step 2: 矛盾しない頂点同士を辺で結ぶ 次に、頂点と頂点を辺で結びます。ただし、辺を結ばない例外的なルールが2つあります。

この2つの例外を除き、他のすべての頂点ペアを辺で結びます。すると、次のようなグラフが完成します。

この変換は多項式時間で実行できます。リテラルの総数を \(L\) とすると、 変数を整数の識別番号で表し、その比較を1回と数えるモデルでは、 辺を引くかどうかの判定は各頂点ペアについて定数時間で行え、 ペアの総数は高々 \(\frac{L(L-1)}{2}\) なので、全体の計算量は \(\text O(L^2)\) です。

グラフが完成しました。元のSAT問題には節が 3つ あったので、このグラフでサイズ3のクリークを探します。もし見つかれば、元のSAT問題の答えは「Yes」です。

実際に探すと、3つの節からそれぞれ1つずつ選んだ頂点、第1節の \(\bar x\)、第2節の \(\bar y\)、第3節の \(z\) により、下の図で太線と二重丸で示された \(\{\bar x, \bar y, z\}\) という頂点サイズ3のクリークが見つかります。3頂点はどれも異なる節に属し、互いに辺で結ばれています。

このクリークが、なぜSAT問題の解になるのか見てみましょう。

逆向きも成り立ちます。もし \(f\) を真にする割り当てがあれば、各節には必ず真になっているリテラルが少なくとも1つあります。節ごとにその1つを選ぶと、選んだリテラルはどれも同じ割り当ての下で真なので、\(x\) と \(\bar x\) が同時に選ばれることはありません（ルール(B)を満たす）。しかも各節から1つずつ選んでいるので同一グループの重複もありません（ルール(A)を満たす）。したがって選んだ \(k\) 頂点は互いに辺で結ばれ、サイズ \(k\) のクリークになります。

ここで \(k\) は節の数です。元の式に充足割り当てが存在することと、変換で作ったグラフにサイズ \(k\) のクリークが存在することが同値です。したがって、YesだけでなくNoも保存されます。

これまでの議論から、どんなSAT問題でも多項式時間でクリーク問題に還元できることがわかりました（\(\text{SAT}\preceq_P \text{クリーク}\)）。 つまり、クリーク問題は少なくともSAT問題と同じか、それ以上に難しいと言えます。

これだけでクリーク問題がNP困難だと言えるのは、還元をつなげられるからです。NPのどの問題Xも、SATに多項式時間還元できます（クック-レヴィンの定理）。そこで、Xの入力をまずSATの入力に変換し、それをさらにクリーク問題の入力に変換すれば、Xをクリーク問題に還元できます。多項式時間の変換を2回続けても、全体の時間は多項式でおさえられます（1回目の変換結果の大きさも入力の大きさの多項式でおさえられるためです）。よって、NPのどの問題もクリーク問題に多項式時間還元でき、クリーク問題はNP困難です。 さらに、クリーク問題自身もNPに属します。なぜなら、「この \(k\) 個の頂点がクリークである」 という解の候補が与えられたとき、すべての頂点ペア間に辺があるかを確認するだけで済み、 これは \(\text O(k^2)\) 時間で検証できるからです。 よって、クリーク問題もまたNP完全であることが証明されました。

クリークは「全員が互いに知り合いのグループ」でした。では、その正反対の概念を考えてみましょう。

グラフの中で、どの2頂点も辺で結ばれていないような頂点の集合を「独立集合」と呼びます。人間関係に例えるなら、「グループ内の誰も互いに面識がない」という状態です。

上の図では、色のついた頂点の集合が独立集合です。どの2頂点を取っても、その間に辺がないことを確認してください。

これもクリーク問題と同様に、Yes/Noで答える決定問題です。

独立集合問題は、意外にも多くの実問題に隠れています。

独立集合問題がNP完全であることを証明するために、「補グラフ」という概念を導入します。

あるグラフ \(G\) の補グラフ \(\bar G\) とは、元のグラフの辺の有無を完全に反転させたグラフです。

上の図は、グラフ \(G\) とその補グラフ \(\bar G\) の例です。元のグラフで結ばれていたペアが補グラフでは離れ、元のグラフで離れていたペアが補グラフでは結ばれています。

補グラフの定義から、次の重要な性質が導かれます。

なぜでしょうか？

補グラフでは辺の有無が反転するので、「すべて結ばれている」状態が「すべて結ばれていない」状態に変わります。つまり、クリークが独立集合に、独立集合がクリークに変身するのです。

この双対性を利用すると、クリーク問題から独立集合問題への還元はとても簡単です。

この還元が正しいことを確認しましょう。

したがって、クリーク問題と還元後の独立集合問題は、常に同じ答え（YesかNo）を返します。

この還元は多項式時間で実行できるでしょうか？

補グラフの計算では、すべての頂点ペアについて辺の有無を反転させます。頂点数を \(n\) とすると、頂点ペアの総数は \(\frac{n(n-1)}{2}\) です。各ペアについて辺の有無を反転する操作は定数時間で行えるため、補グラフ全体の計算は \(\text O(n^2)\) 時間で完了します。

これは入力サイズの多項式なので、この還元は確かに多項式時間還元です。

以上から、次のことが示されました。

1と2を合わせて、独立集合問題はNP完全であることが証明されました。