最小帰還辺集合問題

このページでは最小帰還辺集合問題と呼ばれるNP完全・NP困難な問題をイジングモデルで表現する方法について述べます。

問題の定式化 #

有向グラフ $G = (V, E)$ が与えられます。 このとき部分グラフ $(V,E-F)$ が無閉路であるような $F \subset E$ のうち $|F|$ が最小のものを求めます。 これはNP困難な問題として知られています。

問題の具体例 #

以下のような８個の頂点と１１本の有向辺から構成されるグラフを考えます。 このとき、この問題の答えは図の右側の赤い辺の集合で、最小の要素数２を達成します。 実際に、任意の水色の頂点からスタートし元の頂点に戻るような全ての経路について、赤い辺を少なくとも1回通ることが確認できます。このような辺の集合の要素数を最小化する問題です。

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

部分グラフ $(V,E-F)$ が無閉路であることは、 辺 $uv \in E-F$ に対して $h(u)<h(v)$ であるよう各頂点 $v \in V$ の高さを決められることと必要十分です。 この考えに則ってエネルギー関数を構成します。

各頂点 $v$ に対して、 高さが $i$ であるときに1をとり、そうでないとき0をとるバイナリ変数 $x_{v,i}$ を定義します。 次に、各辺 $uv \in E$ に対して、 $uv \in F$ のとき0をとり、そうでないとき1をとるバイナリ変数 $y_{uv}$ を定義します。 また、 $y_{uv}=1$ かつ頂点 $u$ の高さが $i$ のとき1をとり、そうでないとき0をとるバイナリ変数 $x_{uv,i}$ を定義します。

A,Bを正の定数とします。 このとき、エネルギー関数は以下のようになります。 $H = H_A + H_B$ $H_A = A \sum_{v \in V} \left( 1 - \sum_{i} x_{v,i} \right)^2 + A \sum_{uv \in E} \left( y_{uv} - \sum_{i} x_{uv,i} \right)^2 + A \sum_{uv} \sum_{i} x_{uv,i} \left( 2 - x_{u,i} - \sum_{j>i} x_{v,j} \right)$ $H_B = B \sum_{uv \in E} (1 - y_{uv})$

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

それぞれのエネルギー関数の各項はどのような制約を課しているでしょうか？

まず $H_A$ の第１項は、 各頂点 $v$ についてただ一つの高さ $i$ が存在するという制約を課しています。

また、 $H_A$ の第２項は、 各辺 $uv$ に対して、 $uv \in E-F$ ならばただ一つの高さ $i$ を持ち、そうでないときは高さを持たないという制約を課しています。

最後に、 $H_A$ の第３項は、 各辺 $uv$ が高さ $i$ を持つとき、頂点 $u$ の高さが $i$ かつ頂点 $v$ の高さ $j$ が $j>i$ であるという制約を課しています。

以上の制約により、部分グラフ $(V,E-F)$ に対して各頂点 $v \in V$ の高さを決めることができます。 よって、エネルギー関数の最小化により $(V,E-F)$ が無閉路であるような $F$ を得ることが出来ます。

$H_B$ は帰還辺集合の大きさを最小化するためのものです。 $uv \in F$ なる辺が少ないほどエネルギー関数が小さくなります。 このとき、帰還辺集合の大きさの最小化よりも制約の遵守を優先するので $B<A$ である必要があります。

参考文献 #

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