最大フローの計算量に関する知見

０、はじめに

最大フロー問題について考える。

最大フロー問題とは、
容量を持つ有向グラフについて、
ある地点からある地点に最大どれだけの流量を流せるかを考える。
最大フロー問題ともいうし最大流量問題ともいう。

最大フロー問題は２部マッチング問題を解く場合にも使える。
２部マッチング問題とは例えばA群とB群にそれぞれ人がいたとするとき、
A群のある人はB群の複数のある人とペアを組めるという条件がある。
最大のペアを作るにはどうするかという問題である。

最大フロー問題は最小カット問題を解く場合にも使える。
最小カット問題とは有向グラフにおいて始点から終点への複数のルートがあるとき、
最小で何箇所のエッジを切れば全てのルートが無くなるかを求める問題。
これは最大のフロー数が最小のカット数に等しくなるので最大フローが使える。

最大フローの基本的な考え方を理解するためにフォード・ファルカーソンを調べる。
また、適当にグラフを描いてみて計算量を検証してみる。
次に、Dinicがフォード・ファルカーソンをどう改善しているかを調べる。
Dinicでどれくらい計算量が少なくなるかを検証してみる。

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

１、グラフの表記

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

3 3
0 1 3
1 2 2
0 2 1

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

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

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

２、フォード・ファルカーソンを考える

フォード・ファルカーソンは原理が簡単である。
次のような有向グラフを考える。

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

0から3まで流量を流すことを考える。
以上では容量を持った5本のエッジを持っているが、
その逆方向に容量0のエッジを5本用意しておく。
ノードは数の小さいほうから探索するようにしている。

まず、0→1→2→3という探索が発生する。

このとき再帰で探索しエッジの最も少ない流量を記録していき、
戻ってくるときにもともとのエッジから流量を引いて逆方向のエッジに足す。

すなわち、0→1と1→2と2→3で最も容量が小さいのは2→3の3である。
よって、2→3の流量は3引いて3→2に3足す。
また、1→2の流量は3引いて2→1に3足す。
0→1の流量は3引いて1→0に3足す。

逆方向のエッジに発生した容量は以降で使用することができる。

次に、0→1→3という探索が発生する。

0→1の容量は1になってしまったので0→1→3では流量が1流れる。
更新すると、1→3の流量は1、3→1の流量は1になる。
また、0→1の流量は0、1→0の流量は4となる。

最後に、0→2→1→3という探索が発生する。

この探索の最小の容量は1→3の1なので流量は1が流れます。
更新では、1→3の容量が0、3→1の容量が2となり。
また、2→1の容量は2となり、1→2の容量は4となります。
0→2の容量は1となり2→0の容量は1です。

これ以上は1→3の容量が0、2→3の容量が0のため、
流量を増やせるような探索は発生しません。

よって、エッジ5本のグラフに対して3回フローを流したことになります。
流すことのできた最大流量は5になります。

このときの計算量を見積もってみます。
最悪の場合に1回の探索で全てのエッジを評価するとします。
また最悪の場合に流せる流量は1ずつしか増やせないとします。
ただし、流量は必ず1以上は増えることが保証されます。

よって、エッジをE本、流す流量をFとすると計算量はO(FE)とできる。

３、フォード・ファルカーソンの計算量の実際

フォード・ファルカーソンの計算量はO(FE)だが実際はそれより早い。
どのようなケースが計算量が最悪になるか想像がつかないが、
全ての容量が同じということはないだろうから、バラけたほうが良いだろう。
また、エッジは張れるだけ張っておいたほうが良いだろうと考えます。

乱数を使ってエッジを張ってみていろいろ計算量を求めてみました。

N=50 容量が1のみのとき、フロー50回程度、計算量100000程度。
N=50 容量が1〜100のとき、フロー1000回程度、計算量1500000程度。
N=50 容量が1〜10000のとき、フロー1500回程度、計算量2000000程度。
N=50 容量が1〜1000000000のとき、フロー1500回程度、計算量2000000程度。

N=100 容量が1〜1000000000のとき、フロー10000回程度、計算量50000000程度。

N=300 容量が1のみのとき、フロー300回程度、計算量20000000程度。
N=300 容量が1〜100のとき、フロー15000回程度、計算量1000000000程度。
N=300 容量が1〜10000のとき、フロー150000回程度、計算量10000000000程度。

N=500 容量が1のみのとき、フロー500回程度、計算量100000000程度。

N=1000 容量が1のみのとき、フロー1000回程度、計算量1000000000程度。

ノード数は50ならどのようなエッジでも余裕でいけそうですね。
ノード数が100ならどのようなエッジでもなんとかいけそうです。
ノード数が300だと容量が1のみのエッジならなんとかいけそうです。
ノード数が500を超えてくると容量1のみでもエッジを減らさないと難しい。

エッジが容量1のみだとノード数O(N^3)くらいで見積もって良さそうですかね？
エッジの容量が増えると計算量は増えますが比例して増えるというほどではなさそうです。

最悪のケースはエッジを探索する順番がわかっているのであれば意図的に作れそうです。
ただし、それぞれの解法が必ずしも同じ順番でエッジを探索しないでしょうし、
最も探索順番として多そうなノードの番号順で探索すると最悪のケースで落ちて、
順番を適当に変えると最悪のケースを通らないので正解するというのも問題があるように思います。
ギリギリで時間が間に合わない場合はダメ元で探索順を変えてみるのはいいかもしれません。

４、Dinicを考える

Dinicとはフォード・ファルカーソンの探索と比べると、
容量を流す方向と逆方向について更新するというやり方は同じです。

Dinicの違いは毎回の幅優先探索と終点に到着できないエッジを切り捨てる方法の2つがあります。
フォード・ファルカーソンと仕組みは同じだけれど探索回数をうまく減らしてやる方法と言えます。

まず、幅優先探索は始点から終点に向けて毎回フローを流す前に1回行います。
始点からの距離を求めてフローの探索で終点に近づかない探索は省くのが目的です。
フローを流すと容量0のエッジができるので毎回グラフの形が変わると言えます。
よって、幅優先探索はフローを流し終わったら毎回やり直す必要があります。
幅優先探索が終点にたどり着けなかったらそこで終了です。

また、到着できないエッジは切り捨てる方法があります。
例えば、次のような有向グラフで0から4へ流量を流すことを考えてみます。

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

この場合0→1の流れは終点にたどり着かないのでまったく無駄な探索です。
0→2の探索の前に毎回0→1の探索が発生するのは無駄です。
よって、終点にたどり着かないのであれば、
0からの探索の始まりのインデックスを進めて0→1からではなく0→2にしてしいます。
このような無駄な探索の切り捨てを全てのノードで行います。
このようにすることで無駄な探索が減らせます。

このような工夫を加えることで果たして正しい答えが得られるのかは検証していません。
おそらく正しい答えが求められるのでしょう。

Dinicの計算量はO(V^2E)ということになっていますが、
やはり、グラフの形によって大きく依存してくると言えます。

５、Dinicの計算量の実際

Nはノード数でエッジは全てのノード間に張ってあります。
エッジの容量は指定した範囲内で乱数で設定しました。

N=50 容量が1のみのとき、フロー50回程度、計算量20000程度。
N=50 容量が1〜100のとき、フロー100回程度、計算量30000程度。
N=50 容量が1〜10000のとき、フロー100回程度、計算量30000程度。
N=50 容量が1〜1000000000のとき、フロー100回程度、計算量30000程度。

N=100 容量が1〜1000000000のとき、フロー200回程度、計算量200000程度。

N=300 容量が1のみのとき、フロー300回程度、計算量1000000程度。
N=300 容量が1〜100のとき、フロー1000回程度、計算量2000000程度。
N=300 容量が1〜10000のとき、フロー1000回程度、計算量2000000程度。

N=500 容量が1のみのとき、フロー500回程度、計算量2000000程度。

N=1000 容量が1のみのとき、フロー1000回程度、計算量10000000程度。

フォード・ファルカーソンに比べて流量がそれほど影響しないようですね。
ノード数がN=1000でも容量を気にせず余裕で使えそうです。

ただし、N=2000くらいになると計算量が50000000程度にまでなります。
N=3000だと容量が1のみでも計算量が100000000程度になって厳しいです。

N=2000くらいが使用に耐えるギリギリのラインかもしれません。
エッジの数が減ればその限りではありませんが。

Dinicはフォード・ファルカーソンに比べるとおそらく早いです。
また、流量による計算量の影響が少ないことを考えても使いやすいと言えます。

フォード・ファルカーソンのほうがDinicより早くなるケースは作れそうでしょうか？
Dinicに特有のボトルネックがあるのでしょうか？そこはわかりません。

６、Push Relabelを考える

Dinicの計算量O(V^2E)に対してPush RelabelはO(V^2E^(1/2))である。
単純にDinicよりもPush Relabelのほうが早そうである。

原理は調べていないがコードを拾ってきて実際に動かしてみた。
すると、結果はN=100で容量1のみの有向グラフでも遅いという結果になった。
N=100で適当な容量を割り振ってやるとさらに遅くなり使えない。
おそらく競技プログラミングでよくある2秒制限を超えると思われる。

実装に問題があるのかもしれないがDinicより高速とはいえなかった。

７、復元

復元とは具体的にどのように流量が流れるかを求めること。

最大フロー問題では最大流量は一意に定まるがその経路は複数あることもある。
どのように流れるかを例えば１例挙げることは可能である。
フローを流し終わった時点での逆方向の流量はすなわち順方向に流れた量なので、
最終的な逆方向の流量はすなわち順方向に流れた流量に等しい。

２部マッチングの場合もペアの組み合わせは複数あることがあるだろう。
この場合はペア間に逆方向のフローが流れているかを調べてペアの１例とできる。

最小カットの場合もカット位置は複数あることもある。
最小カットの場合はフローを全て流し終わったグラフについて、
始点からフローを流すことを試み到着できるノードとできないノードの集合を求める。
到着できるノードから到着できないノードへのすべてのエッジが切るべきエッジである。
これもカット位置の１例である。

８、最後に

TopCoderのSRMで最大流量を用いる問題をいくつか探してみました。
するとノード数はだいたいN=1000程度に調節しているようです。
この場合はDinicを使っておくとエッジの数がどうであれ安心できると思います。

AtCoderではエッジ数を減らした問題でN=5000が出ていました。
エッジが減ればN=5000でもいけるのだと思います。

N=100000という制約はよくあるように思いますが、
N=100000であればまずフローで解ける問題ではないと思います。

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