容量スケーリング：最大流

各辺の容量が整数で、最大容量が $U$ であるようなネットワークの最大フロー問題を考えます。

最大増加パス

最大フローを一つ取り $f^*$ とすると、$f^*-f$ は残余ネットワーク $G_f$ 上の最大フローです。フロー分解定理より、$f^*-f$ は高々$|E|$ 個の $s$-$t$ パスと、いくつかのサイクルで書けます。従って、$f^*, f$ の流量をそれぞれ $\alpha, \alpha^*$ と置くと、流量が $(\alpha^*-\alpha)/|E|$ 以上の増加パスが存在します。流量最大の増加パスを加えることを $|E|$ 回繰り返すと、残余ネットワークの最大フローの流量は少なくとも $$(1-1/|E|)^{|E|} \leq e^{-1}$$倍されます。 $|E|(\lceil \log U \rceil + 1)$ 回繰り返すと、残余ネットワークの最大フローの流量は $$e^{-\lceil \log U\rceil + 1}(\alpha^*-\alpha) < 1$$ 以下になるので最大流が求まります。

容量スケーリング

計算量を抑えるため、流量最大の増加パスを求める代わりに、流量 $\Delta$ 以上の増加パスを求めることにします。これは、残余容量 $\Delta$ 以上の辺のみからなる残余ネットワーク $G_{f}^\Delta$ 上でDFSすればよいです。流量 $\Delta$ 以上の増加パスがなくなると、残余ネットワーク上の最大流の容量は $\Delta|V|$ 未満になります。これは$G_f^\Delta$ で頂点 $s$ から到達可能な頂点の集合を $V$ とすると、カット $E(V, \overline{V})$ が残余容量 $\Delta$ 未満の辺からなることから分かります。流量$\Delta$の増加パスが見つからなくなったら $\Delta \leftarrow \Delta / 2$ とします。残余ネットワークの最大フローの流量が $2|E|\Delta$ で抑えられていることから、流量 $\Delta$ 以上の増加パスは高々 $2|E|$ 回しか見つかりません。従って、初期値 $\Delta=2^{\lfloor \log U \rfloor}$ として $\Delta = 1 / 2$ となるまで操作を繰り返すと $O(|E|^2\log U)$ で最大流が求まります。

距離ラベル

距離ラベルによって、計算量を改善できます。次の二つの条件を満たす関数 $d$ を距離ラベルと呼びます。

辺 $(u, v) \in E(G_f)$ のとき $d(u) \leq d(v)+1$
$d(t) = 0$

このとき $d(v) \leq \mathrm{dist}(v, t)$ が成り立ちます。従って、残余ネットワーク上の距離ラベルが $d(s) \geq |V|$ を満たせば、$s$-$t$ 増加パスが存在しないため最大流が得られています。$d(u)=d(v)+1$ を満たす辺を許容辺を呼ぶことにします。

流量 0 の下、$G_f$ 上で BFS して $d(v) = \mathrm{dist}(v, t)$ とすることで距離ラベルが一つ求まります。
次の二つの操作で距離ラベルが壊れないことに着目しましょう。

プッシュ : 許容辺を逆向きにする。
ラベル更新 : $d(v) \leftarrow 1 + \min_{u \in N(v)} d(u)$

許容辺を選び続けることで距離ラベルが狭義単調減少して $s$-$t$ パスが得られます。許容辺が存在しない頂点に到達した場合は、距離ラベルの更新を行い、構築中のパスを一つ短くして一つ前の頂点に戻ります。一つ前の頂点に戻る回数は距離ラベルの更新回数で抑えられます。距離ラベルは更新されるたびに1以上増加し、$|V|-1$ 以上になると、二度と更新されることがありません。これは、$d(s) < |V|$ およびパス上の距離ラベルが狭義単調減少することから分かります。

許容辺が増加するのは距離ラベルを更新したときだけなので、各頂点について、その頂点を始点とする許容辺のキューを距離ラベルの更新時に構築して、プッシュで必要になった時に許容辺かどうか判定すればならし $O(1)$ で許容辺が得られます。

以上より $O(|V|)$ で増加パスが得られました。容量スケーリングでは、各 $\Delta$ において増加パスが $O(|E|)$ 回しか見つからないことから、それらを $O(|E||V|)$ で見つけられます。従って全体の計算量は $\sum_{\Delta} O(|E||V|) = O(|E||V| \log U)$ となります。