クリーク判定問題

このページでは、クリーク判定問題と呼ばれるNP完全な問題をイジングモデルで表現する方法について述べます。

問題の定式化 #

無向グラフ \(G = (V, E)\) と自然数 \(K\) が与えられます。 \(G\) には大きさ \(K\) のクリークが存在するでしょうか？

なお、この問題の最適化問題版はNP困難な問題として知られています。（無向グラフの大きさ最大のクリークを求める問題です。）

問題の具体例 #

以下の図の左側のグラフを考えます。いま、大きさ \(K=4\) のクリークが存在するかを判定することにします。すると、図の右側の赤枠の部分が \(K=4\) のクリークであることを発見しました。よってこの問題の答えはYESです。問題の具体例

イジングモデルへの変形 #

この問題を解くイジングモデルのエネルギー関数は以下のように構築されます。

まず、各頂点 \(v \in V\) に対してイジングスピン変数 \(s_v = \pm 1\) を導入します。ただ、エネルギー関数の設計においてはイジングスピン変数よりもバイナリスピン変数（０か１を取る変数）を用いた方が都合がよいので、各 \(s_v\) を以下のように変数変換した \(x_v\) を用いることにします。 \[ x_v = \frac{s_v + 1}{2} \] また、 \(A\) と \(B\) はともに正の定数とします。するとエネルギー関数は \[ H = A \left( K - \sum_{v \in V} x_v \right)^2 + B \left[ \frac{K(K-1)}{2} - \sum_{uv \in E} x_u x_v \right] \] となります。

エネルギー関数の最小化によりクリーク判定問題が解けるのは何故か #

先ほど定義したエネルギー関数を最小化することで、本当にクリーク判定問題が解けているのでしょうか？これは次のようにして確かめることができます。

エネルギー関数の最小化により、 \(H = 0\) となったとしましょう。この時、エネルギー関数の第1項が０であることから、 \(n\) 個の頂点のうちちょうど \(K\) 個の頂点の \(x_v\) が１になっています。さらに、第２項を見ると、辺の両端点の \(x_v\) が１であるような辺はちょうど \(\frac{K(K-1)}{2}\) 本存在することがわかります。つまり、 \(x_v = 1\) となっている頂点の集合を作ると、これは大きさ \(K\) のクリークをなすことがわかります。これで、エネルギー関数が最小化を通して０にできれば、大きさ \(K\) のクリークが見つかることが示されました。

おまけ #

実は、上の正当性の証明は嘘をついています。というのも、もしエネルギー関数の第１項が正であっても、第二項が負になることで \(H = 0\) が実現するかもしれないからです。したがって、 \(H = 0\) だからといって第１項、第２項がともに０であるとは限りません。しかし実は \(A > KB\) が成り立っている限りそのようなことは有り得ず、 \(H = 0\) であるならば第１項、第２項がともに０になることを示すことができます。参考文献に示された論文の７ページ最終行～８ページ５行目までに詳細が書いてあります。
上に示した問題は判定問題でしたが、以下のようにしてこの問題の最適化問題バージョンを作ることができます。考えたい問題は「与えられた無向グラフに対して、大きさ最大のクリークを求める。」というものです。そのためには、エネルギー関数を以下のように修正すればよいです。ただし、各 \(i = 2, 3, \ldots, \Delta\) に対して、大きさ \(i\) のクリークが存在するときに１、そうでないときに０を取るような補助変数 \(y_i\) を導入しておきます。（ここで \(\Delta\) は無向グラフの頂点の最大次数です。） \[ H = H_A + H_B + H_C \] \[ H_A = A \left( 1 - \sum_{i=2}^\Delta y_i \right) ^2 + A \left( \sum_{i=2}^\Delta i y_i - \sum_{v \in V} x_v \right)^2 \] \[ H_B = B\left[ \frac{1}{2} \left( \sum_{i=2}^\Delta i y_i \right) \left( \sum_{i=2}^\Delta i y_i - 1 \right) - \sum_{uv \in E} x_u x_v\right] \] \[ H_C = - \sum_{v\in V} x_v \] こうして作られるエネルギー関数の最小化で最適化問題が解けていることを示すことは容易です。詳しくは参考文献に示された論文の８ページを読んでください。

参考文献 #

A. Lucas, “Ising formulations of many NP problems” (open access)