Dinic Algorithm

個人的メモ

最大流アルゴリズムとして Ford Fulkerson のアルゴリズムがよく知られているが, こちらは計算量が流量に比例するので流量が大きい場合に計算時間がとてもかかってしまう. 実際に辺の容量を整数に限った場合でも入力サイズについて指数回更新を繰り返す例が構成できる.
余談だが辺の容量が整数の場合は最大流となる整数フローが存在するという整数流定理が成り立つ(有向グラフの接続行列の完全単模性みたく言える).
上記の問題を解消するため, 残余ネットワーク上の $s$ -> $t$ 間増加道を辺数最小のパスとするアルゴリズムが Dinc と Edmonds, Karp によって独立に考えられた(冷戦時代にはこのようにアメリカ, ロシアで独立に考えられていた系の話が多い気がする).
Edmonds, Karp のアルゴリズムでは毎回辺数最小のパスを幅優先探索を用いて計算しているのに対し, Dinic のアルゴリズムの方は初めに幅優先探索を行い $s$ からの最短経路 DAG を構築し, そのグラフ上で $s$ -> $t$ 間増加道が取れなくなるまで深さ優先探索を繰り返すという手法をとる. このとき辺数最小の増加道に沿ってフローを流しても $s$ から各頂点までの距離が短くなることはないことが重要である. $s$ -> $t$ 間増加道が取れなくなるまで探索を続ける期間をフェーズと呼ぶことにすると, フェーズごとに最短の増加道の長さが少なくとも $1$ 以上増加することが示せるためフェーズの数は $\O(n)$ となる..
Dinic のアルゴリズムでは $1$ 回のフェーズにかかる計算量が Edmonds Karp($\O (m^2)$) とは異なり $\O (nm)$ であるため後者のほうが高速に動作する. 各頂点についてそのフェーズでどの辺まで探索したかを表す iter を保持しておく. すると dfs において高々 $n$ 回の辺の探索後にはある頂点の iter が少なくとも $1$ 増えることが分かる. 「$e.cap > 0$ && $level[v] < level[e.to]$」 を満たさない辺が見つかればすぐに iter は増えるし, そのような辺が見つからなければ $s$ から $t$ への増加道(長さ $n-1$ 以下) が見つかったことになり増加道上の少なくとも $1$ つ以上の辺の容量が $0$ となりその部分で iter が $1$ つ進む. 各フェーズにおいて iter の総増加回数はもちろん $\O (m)$ なので各フェーズは $\O (nm)$ で終了する。
結局のところ時間計算量は $\O (n^2 m)$ となるが, 実測ではとても高速に動作することが多い(しかしもちろん最悪ケースでは遅いのでその場合は こちら のアルゴリズムや容量スケーリング版(補足 2) を用いるとよい).

（補足 1)
アルゴリズムの正当性に 「残余ネットワーク上に増加道が存在しない ⇔ $f$ が最大流である」 という事実を用いている. 「残余ネットワーク上に増加道が存在しない ⇒ $f$ が最大流である」 の向きが分かりにくいが, これは残余ネットワーク上で $s$ からたどれる頂点集合を $V_s$ としたとき $V_s$ から外に出るすべての辺 $e$ について $f(e) = e.cap$, $V_s$ に入るすべての辺 $e$ について $f(e) = 0$ が成り立つという事実から $(V_s, V \setminus V_s)$ は $G$ の $s$ - $t$ カットとなっていて, 最大流は $s$ - $t$ カット以下である(弱双対性)ことは少し端折るとまあそうなので $f$ が最大流となっている.
また上記から $s$ - $t$ 最大流と $s$ - $t$ 最小カットは一致することも分かりこのアルゴリズムは最小カットを求めるアルゴリズムとしても用いることができる.
最大流を線形計画問題で書き下したときの双対問題が最小カットの線形計画問題にあたり両者は強双対性より等しいといった流れでも示すことができる(が双対問題が最小カット問題を意味していることが分かりにくい).

(補足 2)
Dinic 法は 2 部グラフのマッチングに応用でき計算量は $\O (m \sqrt{n})$ で動作する(詳しくは こちら). また辺容量がすべて同じ場合計算量は $\O (\min(n^{2/3}, m^{1/2}) m)$ に落ちる(多重辺は無いものとする). 以下これを説明する(参考).
辺の容量はアルゴリズム中常にすべて等しいため $s$ -> $t$ 増加道を見つけたら, それに沿ってフローを流すとそのパス上の辺が全て saturated になることに注意する. またこれより 1 回のフェーズで $s$ -> $t$ 増加道として同じ辺が 2 度使われることはないので 1 回のフェーズ は $\O (m)$ で終了する.
$\sqrt{m}$ 回目のフェーズにおける残余グラフに注目する. $s$ からの最短距離が $d$ となる頂点集合を $V_d$ としたとき $s, t$ 距離は $\sqrt{m}$ 以上であることから $(V_d, V_{d+1})$ 間の辺の個数が $\O (\sqrt{m})$ となるような $d$ が存在する. よって残りの増加回数は $\O (\sqrt{m})$ となり, 全フェーズ数 $\O (\sqrt{m})$ 回. 同じように $\O (n^{2/3})$ 回目のフェーズにおける残余グラフに注目すると $V_d, V_{d+1}$ で $|V_d|, |V_{d+1}|$ が $\O (n^{1/3})$ となるような $d$ が存在する. ここで多重辺を持たないという条件のもとで間の辺の個数が $\O (n^{2/3})$ となり, 全フェーズ数が $\O (n^{2/3})$ 回になる. ゆえに上記の計算量となる.
ちなみに, 容量が全て等しいなら高速に動作するという話をより発展させたのが Goldberg, Rao[1998](Binary blocking flow) であり整数容量のネットワークにおける最大流をより良い計算量で求めることが可能である.

(補足 3)
フロー界隈ではスケーリングを用いて計算量を $\log$ に落とすという手法がよく用いられ、 実際に Dinic 法も各辺の容量が整数の場合これを用いて $\O (nm \log U)$ ($U$ は辺容量の上限とする) に落とすことができる. これは実測でも例えば普通の Dinic だと性能が悪く出るようなグラフでは特に有効な高速化となる(実際 Dinic 1975 msec, Dinic(容量スケーリング版) 175 msec という結果になった).
アルゴリズム自体はとても簡単でフローを残余グラフ上で $2^k$ 単位で流すという操作を $k = \lfloor \log U \rfloor, \cdots, 0$ についてスケールダウンするように行うと最終的に最大流が求まる. 以下で正当性や計算量の証明を行う.
まずはじめに各辺が整数容量のグラフにおける Dinic アルゴリズムの計算量は, 最大流の流量が $|F|$ である場合 $\O (nm + n|F|)$ であることを示す. 上記の dfs における辺の $iter$ の増加回数をより細かく見るために現在位置のレベル(始点 $s$ からの距離) $level$ に着目する. dfs で探索するとき, 辺を $1$ つ見るごとに "$iter$ が $1$ つ進む" もしくは "$level$ が $1$ つ増加する" が起こる. このとき $iter$ の総増加回数および $level$ の総増加回数を抑えることで, 辺を見る回数が $\O (nm + n|F|)$ となることを示す.
まず全フェーズにおける $iter$ の総増加回数は明らかに $\O (nm)$ である. 次に $level$ の総減少回数を考えると, 新しく増加道が見つかったことにより dfs 関数を return する回数($level$ が減少する回数) は増加道の長さが $\O(n)$ より 1 回につき $\O (n)$ である. つまり, 最大流の流量が $|F|$ である場合全フェーズ合わせても $\O (n |F|)$ 回となる. また新しく増加道が見つかることなく dfs 関数を return する回数($level$ が減少する回数) は直後にその前の頂点の $iter$ が 1 増加するので全フェーズ合わせても $\O (nm)$ 回で抑えられる. よって $level$ の総増加回数は $\O (nm)$ 回で抑えられる. ゆえに辺を見る回数は $\O (nm + n|F|)$ で抑えられる. 各フェーズの最初の幅優先探索にかかる時間は合計すると $\O (nm)$ なので結局 $\O (nm + n|F|)$ となる. ちなみにフェーズの数はもちろん $\O (|F|)$ なので $iter$ の総増加回数および幅優先探索にかかる時間は $\O (m |F|)$ で抑えることができ $\O ((n + m)|F|)$ とも書ける.
本題に入ると, 正当性は最終的に $k = 0$, つまりフローを $1$ 単位で流していることから整数流定理と合わせて最大流が求まることが分かる. 計算量については今 $k = t$ の操作を始めるとする. $k = t+1$ の時点では $2^{t+1}$ 単位のフローのみを考慮した場合の最大流が求まっている. このときの対応するカット(こちらも $2^{t+1}$ 単位の意味でのカット)を $(S, V \setminus S)$ としたとき残余グラフ上で $S$ から $V \setminus S$ には $2^{t+1}$ 単位のフローは流せない. ここで $k = t$ の場合, つまり $2^t$ 単位のフローを考えたとき $S$ から $V \setminus S$ に向かう辺 $e$ は $e.cap < 2^{t+1}$($2^{t+1}$ 単位のフローは流せない) かつカットの辺は $\O (m)$ 個であることから $k = t$ における増加回数は $\O (m)$ 回である. 言い換えると $2^t$ 単位のフローで見たときに最大流の流量は $\O (m)$ であるので各 $k$ における計算量は上での結果と合わせて $\O (nm)$ となる. ゆえに計算量は $\O (nm \log U)$.
実装では各 $k$ で $2^k$ 単位ではなく $2^k$ 以上のフローを流すというようにしている(こうやっても上の証明は回るので特に問題はない).