このページでは無向帰還頂点集合問題と呼ばれる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困難な最適化問題版を考察することにします。
問題の具体例 #
以下のような８個の頂点と８本の無向辺から構成されるグラフを考えます。
このとき、この問題の答えは図の右側の赤い頂点の集合で、最小の要素数２を達成します。
実際に、任意の水色の頂点からスタートして同じ辺および赤い頂点を通らずに元の頂点へ戻れないことが確認できます。
イジングモデルへの変形 #
部分グラフ \((V- F, \partial (V - F))\) は無閉路であるので全体として森になります。 よって、各木に対して高さを（一意ではありませんが）定めることができます。
各頂点 \(v \in V\) に対して、 \(v\) が帰還頂点集合に含まれるときには1をとり、そうでないときは0をとるバイナリ変数 \(y_{v}\) を定義します。 有向帰還頂点集合問題のときと逆であることに注意してください。
また、各頂点 \(v\) と高さ \(i \in \{ 0, \ldots, N=|V|-1 \}\) に対して、 頂点 \(v\) が高さ \(i\) のときに1をとり、そうでないときは0をとるバイナリ変数 \(x_{v,i}\) を定義します。 ただし、 \(v\) が帰還頂点集合に含まれるときは高さを定義できないので、 すべての \(i\) に対して \(x_{v,i}=0\) になります。
次に、辺 \(uv \in E\) と高さ \(i\) に対して、 辺 \(uv\) が高さ \(i\) のときに1をとり、そうでないときは0をとるバイナリ変数 \(x_{uv,i}\) を定義します。
最後に、各辺 \(uv\) に対して、 頂点 \(u\) が帰還頂点集合に含まれるときに1をとり、そうでないときは0をとるバイナリ変数 \(y_{vu}\) と、 頂点 \(v\) が帰還頂点集合に含まれるときに1をとり、そうでないときは0をとるバイナリ変数 \(y_{uv}\) を定義します。 \(y_{uv}\) と \(y_{vu}\) は別のスピンであることに注意してください。
このとき、エネルギー関数は以下のようになります。ただしA,Bを正の定数とします。
\[ H = H_A + H_B \] \[ H_A = A \sum_{v \in V} \left( 1 - y_{v} - \sum_{i} x_{v,i} \right)^2+ A \sum_{uv \in E} \left( 1 - \sum_{i}(x_{uv,i}+x_{vu,i}+y_{uv}+y_{vu}) \right)^2\ + A \sum_{uv \in E} \left( y_{uv} - y_{v} \right)^2 + A \sum_{v} \sum_{i>0} \left( x_{v,i} - \sum_{u:uv \in E} x_{uv,i} \right)^2+ A \sum_{uv,uv \in E} \sum_{i>0} x_{uv,i} (2-x_{u,i-1} - x_{v,i}) \] \[ H_B = B \sum_{v \in V} y_v \]
エネルギー関数の最小化により問題が解けるのは何故か #
それぞれのエネルギー関数の各項はどのような制約を課しているでしょうか？
まず \(H_A\) の第１項は、 各頂点 \(v\) が帰還頂点集合 \(F\) に含まれるかどうかを決める制約です。 具体的には、各頂点 \(v\) が帰還頂点集合に含まれているか、帰還頂点集合に含まれていないならばただ一つの高さ \(i\) が存在するという制約を課しています。
次に、 \(H_A\) の第２項は、 各辺 \(uv\) が \(\partial (V - F)\) に含まれるかどうかを決める制約です。 具体的には、各辺 \(uv\) が「帰還頂点集合に含まれない2つの頂点 \(u,v\) を結び、高さがただ1つ与えられる」か、「頂点 \(u\) または頂点 \(v\) のうち少なくとも1つが帰還頂点集合に含まれる」という制約を課しています。
次に、 \(H_A\) の第３項は、 \(y_{uv}\) が頂点 \(v\) が帰還頂点集合に含まれるときに1をとり、そうでないときは0をとることを守る制約を課しています。
次に、 \(H_A\) の第４項は、 高さ \(i>0\) である任意の頂点 \(v \in V-F\) に対し、ただ一つの辺 \(uv\) が高さ \(i\) を持つという制約を課しています。
最後に、 \(H_A\) の第５項は、 各辺 \(uv\) が高さ \(i>0\) を持つとき、 頂点 \(u\) が高さ \(i-1\) かつ頂点 \(v\) が高さ \(i\) であるか、頂点 \(v\) が高さ \(i-1\) かつ頂点 \(u\) が高さ \(i\) であるという制約を課しています。
以上の制約により、すべての頂点と辺について部分グラフ \((V- F, \partial (V - F))\) に含まれるかどうかが決まり、部分グラフ \((V- F, \partial (V - F))\) は無閉路になります。
\(H_B\) は帰還頂点集合の大きさを最小化するためのものです。 このとき、帰還頂点集合の大きさの最小化よりも制約の遵守を優先するので \(B<A\) である必要があります。
参考文献 #
A. Lucas, “Ising formulations of many NP problems” (open access)