Dinic Algorithm

個人的メモ

最大流アルゴリズムとして Ford Fulkerson のアルゴリズムがよく知られているが, こちらは計算量が流量に比例するので流量が大きい場合に計算時間がとてもかかってしまう. 実際に辺の容量を整数に限った場合でも入力サイズについて指数回更新を繰り返す例が構成できる.
余談だが辺の容量が整数の場合は最大流となる整数フローが存在するという整数流定理が成り立つ(有向グラフの接続行列の完全単模性みたく言える).
上記の問題を解消するため, 残余ネットワーク上の $s$ -> $t$ 間増加道を辺数最小のパスとするアルゴリズムが Dinc と Edmonds, Karp によって独立に考えられた(冷戦時代にはこのようにアメリカ, ロシアで独立に考えられていた系の話が多い気がする).
Edmonds, Karp のアルゴリズムでは毎回辺数最小のパスを幅優先探索を用いて計算しているのに対し, Dinic のアルゴリズムの方は辺数最小パスの長さは更新後に短くなることはないことから初めに最短経路グラフを構築し, そのグラフ上で深さ優先探索を行い, $s$ -> $t$ 間増加道が取れなくなるまで探索を繰り返すという手法をとっている. $s$ -> $t$ 間増加道が取れなくなるまで探索を続ける期間をフェーズと呼ぶ.
一見両者は変わらないように見えるが Dinic のアルゴリズムでは $1$ 回のフェーズにかかる計算量が $\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) を用いるとよい).
(追記) こちら で dinic の worst case を自分なりに作ってみた.
（補足 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})$ 回になる. ゆえに上記の計算量となる.