最小極大マッチング問題

このページでは、最小極大マッチング問題と呼ばれるNP困難な問題をイジングモデルで表現する方法について述べます。 (参考文献の問題の定義は誤っているので修正しておきました。)

問題の定式化 #

無向グラフ \(G = (V, E)\) が与えられます。 この無向グラフの辺数最小の極大マッチングは何でしょうか？ すなわち、 \(D\) の任意の辺は端点を共有しないという条件を満たす辺部分集合 \(D \subseteq E\) であって、極大かつ要素数最小のものは何でしょうか？ （極大というのは、これ以上一つでも辺を付け加えるとこの条件を満たさなくなってしまうということです。）

問題の具体例 #

以下の図のようなグラフを考えます。 図の右側の２種類の辺の選び方は、どちらも赤い辺をこれ以上追加すると赤い辺同士で端点を共有してしまうため極大マッチングになっています。 しかし、右上の図では辺が３本選択されており、右下の図では辺が２本選択されているため、右下だけが最小極大マッチングになっています。 よってこの問題の答えは図の右下の赤い辺の集合です。

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

この問題を解くイジングモデルのエネルギー関数は以下のように構築されます。

まず、各辺 \(e \in E\) に対してその辺がマッチング \(C\) に含まれるかどうかを表すバイナリ変数 \(x_e\) を導入しておきます。 また、各頂点 \(v\) に対して、 \(\partial v\) を \(v\) を端点に持つ辺の集合とします。 そして、各頂点に対して以下の式で定義される変数 \(y_v\) を定義します。

\(x_e = 1\) となる辺の集合 \(D\) がグラフのマッチングである時、 \(y_v\) は頂点 \(v\) がマッチングの辺の端点である場合に１、そうでない場合に０を取る変数になります。 また、 \(A, B, C\) を正の定数とし、 \(\frac{A}{\Delta - 2} > B > C\) を満たすこととします。ここで、 \(\Delta\) はグラフの最大次数です。

すると、エネルギー関数は以下のようになります。

エネルギー関数の最小化により最小極大マッチング問題が解けるのは何故か #

エネルギー関数の最小化を通して最小極大マッチング問題が解けるのはなぜでしょうか？ それは以下のようにして確かめることができます。

最小化によって \(H_A = 0\) が達成されたとしましょう。 この時、各頂点 \(v\) に対して、その頂点を端点とする辺が２つ以上 \(x_e = 1\) となることがありません。 すなわち、 \(x_e = 1\) となる辺 \(e\) の集合を集めて \(D\) を作ると \(D\) はグラフのマッチングになっています。

上記のもとで、さらに最小化によって \(H_B = 0\) となったとしましょう。 \(D\) がグラフのマッチングであるとき \(y_v=0\) または \(y_v=1\) をとるため、 各辺 \(e\) に対して、その両端点 \(u\) と \(v\) について \(y_u = y_v = 0\) となることはありません。 すなわち、 \(u\) と \(v\) の少なくとも一方について、その頂点を端点に持つ辺がマッチングの辺集合に含まれているはずです。 ゆえに、この条件により得られるマッチングの極大性が保証されます。

ここで、 \(\frac{A}{\Delta - 2} > B \) である理由を説明します。 \(H_A\) を無視して \(H_B\) の最小化を優先すると、 \(y_u>1\) や \(y_v>1\) となり \(D\) がグラフのマッチングではなくなってしまいます。 そのため、 \(H_A\) の最小化は \(H_B\) よりも優先する必要があります。具体的には、 \(y_v>1\) のとき、頂点 \(v\) まわりのエネルギーについて \(H_{A_v}+H_{B_v}>0\) となるように \(A,B\) の値を定めます。 頂点 \(v\) と隣接する \(m\) 個の頂点が \(y_u=0\) であるとき、 \(H_{A_v}+H_{B_v}=A\sum_{e1, e2 \in \partial v} x_{e1} x_{e2}+B \sum_{e = uv \in E} (1 - y_u)(1 - y_v)\) を考えます。 \(y_v=2,m=\Delta-2\) のときがワーストケースであり、このとき \(A>(\Delta-2)B\) を得ます。

最後に、 \(H_C\) を最小化することは辺集合 \(D\) の要素数が最小化することになります。

ここで、 \(H_C\) を最小化することに意味があるのは \(H_A=0,H_B=0\) であるときですから、 \(H_A=0,H_B=0\) のもとで \(H_C\) を最小化するように \(A,B,C\) の値を定める必要があります。 まず \(H_A,H_C\) の関係ですが、 \(H_C\) を小さくすることと \(H_A=0\) にすることは矛盾しないので、 \(H_A,H_C\) の関係からは \(A,C\) の関係は定まりません。

次に、 \(H_B,H_C\) の関係を考えます。 ここで、 \(B \leq C\) とすると不都合なことが起こります。 \(H_A=0,H_B=0\) を満たす最適解 \(D\) が存在すると仮定し、辺 \(a \in D\) が頂点 \(u,v\) を結ぶとします。 辺 \(a\) を \(D\) から取り除いたときのエネルギーの変化量は \(dH=dH_A+dH_B+dH_C=0+B-C \leq 0\) となり、 \(D\) が最適解であるとき \(H_B=0\) とならず制約を満たさなくなってしまいます。 よって \(B>C\) という関係が得られ、 \(A,B,C\) は \(\frac{A}{\Delta - 2} > B > C\) を満たす必要があると分かります。

以上のようにして、エネルギー関数を最小化することで、マッチングが求まり（ \(H_A = 0\) ）、それが極大で（ \(H_B = 0\) ）、なおかつ変数最小（ \(H_C\) の最小化）のものになるということが示されました。

参考文献 #

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