集合被覆問題

このページでは、集合被覆問題と呼ばれるNP困難な問題をイジングモデルの形に変形して解く方法について述べます。
なお、この問題は参考文献[1]において「不等式付き問題(Problems with Inequalities)」に分類されている問題です。
このタイプの問題はイジングモデルとして定式化し、そのエネルギー関数を量子アニーリングマシンに埋め込む際に、連結度の高いグラフを必要とします。
そのため、現在のハードウェアでは十分に解くことができないタイプの問題であることに注意してください。

問題の定式化

\(n\)点集合\(U = \{ 1, \ldots, n \}\) が与えられます。
また、\(N\)個の\(U\)の部分集合\(V_i\)が、以下を満たすように与えられます。
$$
U = \cup_{i=1}^N V_i
$$
この時、\(V_i\)たちの中からいくつか選んできて部分集合\(R \subseteq \{ V_i \}\)を作って、\(R\)の要素すべての和集合が\(U\)を被覆するようにしたいとします。
そのような\(R\)のうち要素数最小のものを求めてください。
すなわち、以下を満たす\(R\)のうち要素数最小のものを求めてください。
$$
U = \cup_{V_i \in R} V_i
$$

この問題は「精密被覆問題」に非常によく似ています。
しかし、その大きな違いは、Rを構成する一つ一つの\(V_i\)が交わりを持っても良いということです。

問題の具体例

例えば以下の図のように
\(U=\{1,2,3,4,5,6,7,8,9\},V_1=\{1,2,3\},V_2=\{3,6,9\},V_3=\{4,5\},\\\ V_4=\{5,6,8,9\},V_5=\{4,5,7,8\},V_6=\{7\}\)

の場合を考えます。
このとき、部分集合の集合\(R_{ans}=\{V_1,V_2,V_5\}\)は\(U\)のすべての要素を被覆するような部分集合の集合のうち最小の要素数3を達成します。
よって\(R_{ans}=\{V_1,V_2,V_5\}\)はこの問題の解です。

イジングモデルへの変形

この問題を解くイジングモデルのエネルギー関数は以下のようにして作ることができます。

まず、\(x_i\)をバイナリ変数として、各\(V_i\)が\(R\)に含まれるかどうかを表すものとします。
また、\(x_{\alpha, m}\)をバイナリ変数として、各\(\alpha \in U\)が\(m\)個の\(V_i\)に含まれることを表すものとします。
さらに、\(A,B\)を正の定数とします。
この時、エネルギー関数は以下となります。
$$
H = H_A + H_B
$$
$$
H_A = A \sum_{\alpha = 1}^n \left( 1 – \sum_{m=1}^N x_{\alpha, m} \right)^2 + A \sum_{\alpha=1}^n \left( \sum_{m=1}^N m x_{\alpha, m} – \sum_{i: \alpha \in V_i} x_i\right)^2
$$
$$
H_B = B \sum_{i=1}^N x_i
$$

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

ここでは、上で定義したエネルギー関数を最小化することで、なぜ集合被覆問題が解けるのか説明します。

まず、エネルギー関数を最小化することで\(H_A = 0\)となったとしましょう。
この時、\(H_A\)の第1項が0になるためには、各\(\alpha \in \{1, \ldots, n\}\)に対して、ただ一つの\(m \in \{ 1, \ldots, N\}\)が存在して\(x_{\alpha,i}=1\)となり、それ以外の\(m\)に対しては\(x_{\alpha,i}=0\)となるはずです。
すなわち、\(U = \{ 1, \ldots, n\}\)の各要素\(\alpha\)に対し、\(m \in \{ 1, \ldots, N\}\)が一つ決まります。

さらに、\(H_A\)の第2項が0になるためには、各\(\alpha \in \{1, \ldots, n\}\)に対して、第1項を0にする際に決まった\(m\)と、\(\alpha\)を含む\(V_i\)のうち\(x_i=1\)であるものの個数が一致します。
すなわち、\(U = \{ 1, \ldots, n\}\)の各要素\(\alpha\)が、\(m\)個の\(V_i\)に含まれることになります。
したがって、集合被覆問題の制約条件が満たされることになります。

さらに、\(H_B\)を最小化することで、\(x_i=1\)となる\(V_i\)の個数が最小化されることになります。

したがって、エネルギー関数を最小化すれば\(R = \{ V_i \: | \: x_i=1 \}\)とすることで、集合被覆問題が解けたことになるのです。

おまけ

まず、正定数\(A,B\)に関して、\(H_A\)の最小化は\(H_B\)の最小化よりも優先しますから、\(A>B\)でなくてはなりません。

また、必要なスピン数は以下のようになります。
まず\(M\)を\(N\)以下の定数で、以下のように定義します。
$$
M = \max_{\alpha \in U} (\alpha \text{を含む} V_i \text{の数})
$$
すると、\(x_i\)のために\(N\)個、\(x_{\alpha,m}\)のために\(n\lfloor 1 + \log M \rfloor\)個必要なため、合計で\(N +n\lfloor 1 + \log M \rfloor\)個のスピンが必要となります。

参考文献

[1] A. Lucas, “Ising formulations of many NP problems”, arXiv 2013