劣モジュラな2次擬似ブール関数の最小化問題 #4

劣モジュラな2次擬似ブール関数の最小化問題は、フローネットワークの最大フロー問題を介して効率的に解けるそうです。専門用語だらけでぎょっとしますが、概要をいくつかの記事で解説したいと思います。

解説記事のラインアップ

「劣モジュラな2次擬似ブール関数の最小化問題は、フローネットワークの最大フロー問題を介して効率的に解ける」ことの概要を下記の順で記事にします。
①2次疑似ブール関数とその劣モジュラ性
②劣モジュラな2次疑似ブール関数が持つ特徴
③劣モジュラな2次疑似ブール関数を表すフローネットワーク
④劣モジュラな2次疑似ブール関数を表すフローネットワークの最大フローと、元の関数の最小値の対応

この記事では、「④劣モジュラな2次疑似ブール関数を表すフローネットワークの最大フローと、元の関数の最小値の対応」を解説します。

おさらいと前振り

前回の記事では、2次疑似ブール関数を式変形する方法と式変形後の関数からフローネットワークを構成する方法を、天下り的に紹介しました。本記事では、構成されたフローネットワークの最大フローが2次疑似ブール関数の最小値と対応することを説明します。

そのために本記事では、フローネットワークの「カット」という概念を紹介します。このカットという概念を経由すると、フローネットワークの最大フローと、2次疑似ブール関数の最小値が対応することが示せるからです。

もう少しだけ詳細を述べます。フローネットワークのカットで定義されるカット容量と呼ばれるものと、式変形後の関数の値が対応します。そこから、最小のカット容量と式変形後の関数の最小値が対応することが示せます。そしてこの最小のカット容量とフローネットワークの最大フローは一致します。これら結果と、変形後の式と2次疑似ブール関数は同じという事実から、構成されたフローネットワークの最大フローが2次疑似ブール関数の最小値が対応するという結果が導けます。

ではよろしくお願いいたします。

フローネットワークのカット

フローネットワークのカット$${({\mathbb S},{\mathbb T})}$$はノードの集合のペアです。集合$${\mathbb S}$$と集合$${\mathbb T}$$は、フローネットワークに現れるノード全体を２つのグループに分けたものとなっています。ですので、$${{\mathbb S}\cup {\mathbb T}}$$はフローネットワークに現れるノード全体と一致し、$${{\mathbb S}\cap {\mathbb T}}$$は空集合となります。そしてカットの別の要件として、$${\mathbb S}$$はノードSを含み、$${\mathbb T}$$はノードTを含みます。

次に、カット容量を説明します。カット容量とは、ノードの集合$${\mathbb S}$$からノードの集合$${\mathbb T}$$へ流せるモノの総量です。以下で定義されます。

$$
\sum_{u\in{\mathbb S}, v\in{\mathbb T}} c(u,v)
$$

ここで、$${c(u,v)}$$は、ノード$${u}$$から$${v}$$へのエッジがあるとき、そのエッジのキャパシティとします。ノード$${u}$$から$${v}$$へのエッジがないときは0とします。

例として以下のフローネットワークを見てみましょう。

フローネットワークの例

例えば、$${(\{S, x_2\}, \{x_1,x_3,T\})}$$はこのフローネットワークのカットです。上で書きましたカットの条件に合うのがわかります。そして、このカットで定義されるカット容量は2となります。以下の図で示す通り、集合$${\{S, x_2\}}$$から集合$${\{x_1,x_3,T\}}$$へのエッジとして、「$${S}$$から$${x_1}$$へのエッジ」と「$${x_2}$$から$${x_3}$$へのエッジ」があり、それらのキャパシティの和が2となるからです。

カットの情報を追記したフローネットワークの例

カット容量と式変形後の関数の値は対応

このカット容量と式変形後の関数の値は対応します。引き続き例で見てみましょう。以下の式変形後の関数から以下のフローネットワークが構成できます。

$$
(1-x_1)+(1-x_2)+2x_3+2x_1(1-x_2)+x_2(1-x_3)
$$

フローネットワークの例 (再掲)

そして前節で見た通り、このネットワークのカットが$${(\{S, x_2\}, \{x_1,x_3,T\})}$$のとき、カット容量は2となります。

カットの情報を追記したフローネットワークの例 (再掲)

このカット容量と式変形後の関数の値が対応することを見るために、ここで式変形後の関数の値を見てみましょう。変数への付値ですが、カットの$${\mathbb S}$$に属する変数を1に、$${\mathbb T}$$に属する変数を0にします。つまり、$${x_1=0}$$,$${x_2=1}$$,$${x_3=0}$$とします。そうすると、関数の値は以下の通り2となり、カット容量と一致します。

$$
\begin{array}{l}
(1-x_1)+(1-x_2)+2x_3+2x_1(1-x_2)+x_2(1-x_3)\\
=(1-0)+\cancel{(1-1)}+\cancel{2\cdot 0}+\cancel{2\cdot 0(1-1)}+1\cdot(1-0)\\
=2
\end{array}
$$

なぜカットに合わせて代入した後の関数の値とカット容量が一致するのでしょうか？カットに合わせて関数内の変数に代入したら、「0になる項」と「0にならない項」ができます。この「0にならない項」と対応するエッジが、(カット容量の構成要素となる)集合$${\mathbb S}$$から$${\mathbb T}$$へのエッジとなっているからです。

上の例ですと、代入後「0にならない項」として、$${(1-x_1)}$$と$${x_2(1-x_3)}$$が残ります。前回の記事で説明しました通り、項$${(1-x_1)}$$に合わせて足されたエッジはノードSから$${x_1}$$へのエッジで、項$${x_2(1-x_3)}$$に合わせて足されたエッジは$${x_2}$$から$${x_3}$$へのエッジです。そしてこれらエッジが集合$${\mathbb S}$$から$${\mathbb T}$$へのエッジとなっていることがわかります。

この例だけでなく、任意のカットを持ってきても、カット容量と式変形後の関数の値は対応します。集合$${\mathbb S}$$から集合$${\mathbb T}$$へのエッジに対応する関数内の項は代入後も0とならず関数の値となり、集合$${\mathbb S}$$から集合$${\mathbb T}$$へのエッジとは異なるエッジに対応する関数内の項は代入後0となるからです。

集合$${\mathbb S}$$から集合$${\mathbb T}$$へのエッジを考えます。エッジはノード$${x_i}$$からノード$${x_j}$$へ伸びているとします。カットに従い関数内の変数に代入しますと、$${x_i=1}$$,$${x_j=0}$$になります。その結果、$${x_i(1-x_j)}$$を含む項が0とならず、関数の値の一部となります。エッジがノードSからノード$${x_i}$$へ伸びているときは、関数内の変数に代入すると変数$${x_i=0}$$となり、結果、$${(1-x_i)}$$を含む項が0とならず、関数の値の一部となります。エッジがノード$${x_i}$$からノードTへ伸びているときは、関数内の変数に代入すると変数$${x_i=1}$$となり、結果、$${x_i}$$を含む項が0とならず、関数の値の一部となります。

次に、集合$${\mathbb S}$$から集合$${\mathbb T}$$へのエッジ、以外のエッジを考えます。このようなエッジに対応する項は代入後0となります。このようなエッジには、集合$${\mathbb S}$$内のノード間のエッジと、集合$${\mathbb T}$$内のノード間のエッジと、集合$${\mathbb T}$$から集合$${\mathbb S}$$へのエッジがあります。同じ集合内の変数を表すノード間のエッジは、$${x_i(1-x_j)}$$を含む項に対応していて、$${x_i=x_j}$$なので代入後0となります。ノードSから変数ノードへのエッジは、$${(1-x_i)}$$を含む項に対応していて、$${x_i=1}$$となるため代入後0となります。変数ノードからノードTへのエッジは、$${x_i}$$を含む項に対応していて、$${x_i=0}$$となるため代入後0となります。集合$${\mathbb T}$$から集合$${\mathbb S}$$へのエッジは、$${x_i(1-x_j)}$$を含む項に対応していて、$${x_i=0}$$,$${x_j=1}$$となるため、代入後0となります。

以上から、代入後0とならなかった「ネットワークのエッジに対応する関数内の項」の和と「カット容量」が一致することがわかりました。「代入後の関数の値」はそれら「ネットワークのエッジに対応する関数内の項」と式変形後の関数に残っている定数項の和となります。したがってカット容量と関数の値の対応は、

「カット容量」=「代入後の(式変形後の)関数の値」-「式変形後の関数内の定数項」

となります。

記事を通して「カット容量と式変形後の関数の値は"対応"」と書いていたのは、式変形後の関数内に定数項があるためカット容量と関数の値が一致するとは限らないためです。式変形後の関数内の定数項は、フローネットワーク構成時に無視される(フローネットワークに定数項が反映されていない)ためこのようなことが起きます。

上の例では式変形後の関数に定数項が現れないため、カット容量と代入後の関数値がたまたま一致しました。

フローネットワークの最大フローと、元の関数の最小値が対応する理由

フローネットワークの最大フローと、元の関数の最小値が対応する理由をいくつかの事実から導きます。

まずひとつ目の事実として最小のカット容量と「関数の最小値から定数項を引いた値」は一致します。説明のため、最小のカット容量となるカットを考えます。前節で示した通り、与えられたカットに対して、フローネットワークのカット容量と「式変形後の関数の値から定数項を引いたもの」が一致します。ではこの最小の容量となるカットに合わせて代入された関数の値は最小でしょうか？もしより小さな関数値がある場合、実は矛盾が起きてしまいます。なので最小のカット容量となるカットに合わせて代入された関数の値は最小です。以上より、最小のカット容量と「関数の最小値から定数項を引いた値」は一致します

(矛盾の起こし方を説明します。最小のカット容量より小さな関数値がある場合を考えます。その小さな関数値を導く変数の付値に合わせてカットを作ります。そのカット容量は関数値から定数項を引いたものと一致します。この新しく作ったカットのカット容量は、先の最小と定義したカット容量よりも小さくなるので矛盾してしまいます。)

次の事実として、2次疑似ブール関数の最小値と式変形後の関数の最小値が一致します。これは前回の記事で説明した通り、2次疑似ブール関数と式変形後の関数が同じだからです。

最後の事実として、フローネットワークの最大フローと最小カット容量が一致します。最大フロー最小カット定理と呼ばれる性質です。ざっくり理由を言うと、ノードSからノードTに流せる最大量は、ボトルネックとなる流路と一致し、そのボトルネックが最小のカットだからです。

以上をまとめますとフローネットワークの最大フローと元の2次疑似ブール関数の最小値が対応します。以下の通りです。

「フローネットワークの最大フロー」
=「フローネットワークの最小カット容量」
=「式変形後の関数の最小値」-「式変形後の関数の定数項」
=「2次疑似ブール関数の最小値」-「式変形後の関数の定数項」

劣モジュラな2次擬似ブール関数の最小値を、フローネットワークの最大フロー問題を介して効率的に解く

フローネットワークの最大フローを求める手法を使い、劣モジュラな2次疑似ブール関数の最小値を求めることができます。まず2次疑似ブール関数を式変形し、フローネットワークを構成します。そのネットワークの最大フローを求めます。最大フローから式変形後の関数の定数項を足せば、2次疑似ブール関数の最小値となります。

与えられたフローネットワークの最大フローは効率的に求めることができます。(自分は詳細を確認していないですが)「ノードの数×エッジの数」のオーダーで最大フローを求める方法もあるそうです。

まとめ

この記事では、劣モジュラな2次疑似ブール関数を表すフローネットワークの最大フローと、元の関数の最小値が対応することを説明しました。

因みにですが、劣モジュラとは限らない一般の2次疑似ブール関数の最小化問題は、今回のようなフローネットワークの構成方法では、エッジのキャパシティが正となる解くのに都合の良いネットワークができるとは限りません。実際、一般の2次疑似ブール関数の最小化問題は解くのが大変難しい問題となります。

さいごに

これで「劣モジュラな2次擬似ブール関数の最小化問題」記事も最後です。感想ですが、(単発解説記事作成も難しいですが、)複数の記事に渡る解説記事作成もやはり難しかったです。記事を書いている途中に前回記事と整合が合わなくなって、前回記事を書き直すということを何度かやりました。。

わかる部分とわかりにくい部分、ムラがあると思います。。わかりにくいところは指摘いただけましたら、できるだけ追記します。また励ましや指摘など、コメントをいただけるとありがたいです。よろしくお願いいたします。