2019-09-04

最小帰還辺集合問題

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

問題の定式化

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

問題の具体例

以下のような8個の頂点と11本の有向辺から構成されるグラフを考えます。 このとき、この問題の答えは図の右側の赤い辺の集合で、最小の要素数2を達成します。 実際に、任意の水色の頂点からスタートし元の頂点に戻るような全ての経路について、赤い辺を少なくとも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$の第1項は、 各頂点$v$についてただ一つの高さ$i$が存在するという制約を課しています。

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

最後に、$H_A$の第3項は、 各辺$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)