最小費用流の計算量に関する知見

０、はじめに

最小費用流問題について考える。

最小費用流問題とは、
容量と1容量を流すコストを持つ有向グラフについて、
ある地点からある地点に指定した流量を流すことを考えるとき、
最小のコストで流量を流すためのコストを求める問題である。

最大フローの場合と同じく組み合わせの問題を解くのに使える。

２部マッチングであっても重み付きの場合は最大フローではなく最小費用流問題である。

注意として、
検証はほとんど前知識の無い個人が実験的に行ったものであるので、
参考程度にしていただけたらと思います。

１、グラフの表記

図を描くのが面倒なので以下のような入力でグラフを表現することに統一する。

3 3
0 1 3 2
1 2 2 3
0 2 1 3

最初の行はノードの数、エッジの数。
それ以降はエッジの数だけ行がある。
例えば「0 1 3 2」はノード0からノード1へ容量3、コスト2のエッジがあるとする。

以下のサイトに貼れば自動で描いてくれるので便利。

https://csacademy.com/app/graph_editor/

２、プライマル・デュアル法を考える。

プライマルデュアル法をまず簡単な方法で考えてみる。

例えば次のような有向グラフを考える。

3 3
0 1 2 2
1 2 1 1
0 2 2 4

ここに流量1を流すことを考える。
すべてのエッジについて流れる最大の流量は1なので流量の制限は無いに等しい。
ではコストを最小にするにはどうしたら良いだろうか？
これはダイクストラ法を使ってコストを距離に置き換えたときの最短距離に等しい。
この場合は0→1→2とするとコストは3、0→2ならコストは4である。
よって、0→1→2を使ったほうがコストは小さくなることがわかった。
どうやら最小費用流を求めるのにダイクストラ法が使えそうである。

では、流量2を流すときはどうすれば良いだろうか？
まず、すべてのエッジについて容量0、コストは順方向のコストを負にした逆方向辺を用意します。
ダイクストラによって0→1→2の経路が最小コストとわかりました。
しかしここには容量1の流量しか流せなないので流量1だけ流すことにします。
このとき順方向辺の容量を1減らし逆方向辺の容量を1増やします。
ゆえに、0→1の容量は1、1→0の容量は1、1→2の容量は0、2→1の容量は1となる。
ちなみに、このときにかかるコストは3です。
さて、これで1→2の容量はなくなったので探索できなくなりました。
次にもう一度ダイクストラをすると0→2の経路が選択されて、
流量1、コスト4のフローができると思われます。
ゆえに最終的な最小コストは3+4=7とできます。

しかし、ここで１つ問題があります。
1→0、2→1の辺のコストは負の値です。
負の値があってはダイクストラが使えません。
ここでベルマンフォードを使う方法もあるのですが、
なんとこれ以降もダイクストラを使い続ける技があります。

ポテンシャルという概念を用います。
ポテンシャルは各ノードが1つ持つ数値で最初は0です。
ポテンシャルはダイクストラをするたびにそのノードまでの最小距離を引きます。

さて、ポテンシャルを使ってコストの更新をしてみます。

修正後コスト＝修正前コストー始点ポテンシャル＋終点ポテンシャル

このようにして順方向、逆方向のコストを更新します。
このようにするとコストが負になりません。

すべての流量を流し終わるまでダイクストラと容量、コストの更新を繰り返します。

最初から負のコストがある場合はポテンシャルを使う方法は使えません。
よって、内部でダイクストラではなくベルマンフォードを使わざるを得ません。
すると、計算量はO(FVE)となります。

もし、最初から負のコストが無ければダイクストラを使う方法が可能なので、
この場合の計算量はO(FElogV)となります。

３、プライマル・デュアル法の計算量の実際

Nはノード数でエッジは全てのノード間に張ってあります。
エッジの容量は指定した範囲内で乱数で設定しました。
コストに関しては計算量に関係しないはずなので一定値です。

ダイクストラのみ使う場合、

N=100 容量が1のみで流量1を流すとき、フロー1回程度、計算量20000程度。
N=100 容量が1のみで流量10を流すとき、フロー10回程度、計算量200000程度。
N=100 容量が1のみで流量50を流すとき、フロー50回程度、計算量1000000程度。
N=101 容量が1のみで流量100を流すとき、フロー100回程度、計算量2000000程度。

N=100 容量が1〜100で流量1を流すとき、フロー1回程度、計算量20000程度。
N=100 容量が1〜100で流量10を流すとき、フロー1回程度、計算量20000程度。
N=100 容量が1〜100で流量50を流すとき、フロー3回程度、計算量60000程度。
N=100 容量が1〜100で流量100を流すとき、フロー6回程度、計算量120000程度。
N=100 容量が1〜100で流量1000を流すとき、フロー32回程度、計算量640000程度。
N=100 容量が1〜100で流量3000を流すとき、フロー100回程度、計算量2000000程度。

N=100 容量が1〜10000で流量1000を流すとき、フロー1回程度、計算量20000程度。
N=100 容量が1〜1000000000で流量1000を流すとき、フロー1回程度、計算量20000程度。

N=201 容量が1のみで流量200を流すとき、フロー200回程度、計算量20000000程度。
N=301 容量が1のみで流量300を流すとき、フロー300回程度、計算量60000000程度。
N=501 容量が1のみで流量500を流すとき、フロー500回程度、計算量300000000程度。

考察すると、

容量が十分あるときに流す流量が少ないとダイクストラの回数が減る。
容量に対して流す流量が多くなってくると流量に比例してダイクストラの回数が増える。

N=100〜200くらいだと余裕を持って使えそう。
N=300を超えてくると危なくなってくる。
N=500だとエッジの数を減らさないと厳しいかもしれない。

ベルマンフォードであれば、N=100でギリギリくらいと見積もれるだろう。

４、線形計画問題を考える

例えば次のような有向グラフを考える。

4 5
0 1 4 2
0 2 2 1
1 2 6 1
1 3 2 3
2 3 3 1

最終的にi番目のエッジに流れる流量をEiとする。

するとコストは2*E0+E1+E2+3*E3+E4となりこれを最小化することになる。
また、0<=E0<=4、0<=E1<=2、0<=E2<=6、0<=E3<=2、0<=E4<=3である。
また、流量=E0+E1、E0=E2+E3、E1+E2=E4、E3+E4=流量である。

これは線形計画問題として解くことが可能である。

５、最後に

最小費用流の場合負のコストが無ければO(FElogV)となります。
実際にF=V、E=V^2であることが多いことを考えると、
おおよそO(V^3logV)と考えても良いのではないかと思います。
するとN=100かN=200程度に収まらないと難しいように思います。
もし、負のコストを含むのであればダイクストラが使えません。
この場合はおよそO(V^4)になるのでN=50程度が限界なのではないかと思います。

最後にも注意ですが、この文章は参考程度に。