このページでは有向帰還頂点集合問題と呼ばれるNP完全・NP困難な問題をイジングモデルで表現する方法について述べます。
問題の定式化 #
有向グラフ \(G = (V, E)\) が与えられます。 頂点集合の部分集合 \(F \subset V\) が \(G\) の帰還頂点集合であるとは、 部分グラフ \((V- F, \partial (V - F))\) が無閉路、すなわちサイクルを含まない時のことを言います。 ここで、 \(\partial (V-F)\) は \(E\) の部分集合であって、 \(V-F\) 内の頂点同士のみを結ぶ辺全体を表します。 有向帰還頂点集合問題とは、このような帰還頂点集合 \(F\) であって、 決められた自然数 \(k\) に対して \(|F| \le k\) を満たすものが存在するか？という判定問題です。
これはNP完全な問題として知られています。 また、このような帰還頂点集合であって頂点数が最小のものを求める問題はNP困難な問題として知られています。
本稿では、NP困難な最適化問題版を考察することにします。
問題の具体例 #
以下のような８個の頂点と１１本の有向辺から構成されるグラフを考えます。
このとき、この問題の答えは図の右側の赤い頂点の集合で、最小の要素数２を達成します。
実際に、任意の水色の頂点からスタートして赤い頂点を通らずに元の頂点へ戻れないことが確認できます。
イジングモデルへの変形 #
まず、説明に必要な補題を述べておきましょう。
有向グラフが無閉路であることの必要十分条件は、ある”高さ”関数 \(h : V \rightarrow \mathbb{N}\) が 存在して、任意の \(uv \in E\) について \(h(u) < h(v)\) が成り立つことです。 この補題の証明は1 Lucas 2013の20ページ目をみてください。 この補題に基づいて高さ関数を用いて、エネルギー関数を構成します。
各頂点 \(v \in V\) に対して、 \(v\) が帰還頂点集合に含まれるときには0をとり、そうでないときは1をとるバイナリ変数 \(y_{v}\) を定義します。 また、各頂点 \(v\) と高さ \(i \in \{ 1, \ldots, N=|V| \}\) に対して、 頂点 \(v\) が高さ \(i\) のときに1をとり、そうでないときは0をとるバイナリ変数 \(x_{v,i}\) を定義します。
A,Bを正の定数とします。 このとき、エネルギー関数は以下のようになります。
\[ H = H_A + H_B \] \[ H_A = A \sum_{v \in V} \left( y_v - \sum_{i=1}^N x_{v,i} \right)^2+ A \sum_{uv \in E} \sum_{i \ge j} x_{u,i} x_{v,j} \] \[ H_B = B \sum_{v \in V} (1 - y_v) \]
エネルギー関数の最小化により問題が解けるのは何故か #
それぞれのエネルギー関数の各項はどのような制約を課しているでしょうか？
まず \(H_A\) の第１項は、各頂点 \(v\) について、 これが帰還集合に含まれていない（ \(y_v = 1\) ）ならば、 あるちょうど一つの高さ \(i\) が存在するという制約を課しています。
また、 \(H_A\) の第２項は、 各辺 \(uv\) と \(i \ge j\) となる高さの組 \((i, j)\) に対して、 \(x_{u,i}\) と \(x_{v,j}\) の少なくとも一方が0であるという制約を課します。 つまり、帰還集合に含まれていない頂点 \(u\) および頂点 \(v\) に有向辺 \(uv\) が存在し、 頂点 \(u\) の高さが頂点 \(v\) の高さよりも大きいときにペナルティーを課します。 これは、補題の高さ関数の性質を満たすことを要請するものです。
以上の二つの制約により、 バイナリ変数 \(x_{v,i}\) の各値から、 グラフ \((V- F, \partial (V - F))\) の適切な高さ関数が構成され、 上の補題からこれが無閉路であることが保証できます。
最後に、 \(H_B\) は帰還頂点集合の大きさを最小化するためのものです。 このとき、帰還頂点集合の大きさの最小化よりも制約の遵守を優先するので \(B<A\) である必要があります。