Push-Relabel による最大フローアルゴリズム - 宇宙ツイッタラーXの憂鬱

はじめに

この記事はCompetitive Programming （その2） Advent Calendar 2016 - Adventarの23日目の記事として書かれました。

最初に、一般的なフローネットワークについて触れてます。これは始点と終点を除く頂点について、入ってくるフローと出ていくフローが常に等しい状態であるもので、Ford-Fulkerson 法などを理解するために必要です。最小カット最大フローの定理についても触れます。

次に、条件を緩和して過剰フローを許したプリフローについて考えます。高さ関数制約を導入してプッシュ操作と再ラベル操作を定め、Generic-Push-Relabel のアルゴリズムを考えます。プリフローネットワークに対して処理をしていくと最終的に最大フローが得られることを確認し、再ラベル操作、飽和プッシュ操作、非飽和プッシュ操作の回数の上界を調べます。

さらに、開栓操作を加えた Relabel-To-Front を考えることで、計算量を $O(V^3)$ に改善します。ここに Highest-Label Rule を導入して、 $O(V^2 \sqrt{E})$ まで改善します。

最後に実装も載せました。

この記事に書いてあることは "Introduction to Algorithms" という本にそのまま書いてあります。

フローネットワーク

各辺 $(u, v) \in E$ が、容量 $c(u,v) \geqq 0$ を持つ有向グラフである。入り口 s と出口 t が設定されている。

非負の値を取る量 $f(u,v)$ を頂点 u から頂点 v へのフローと呼ぶ。

フローは以下の 2 条件を満たす。

容量制限: 全ての $u,v \in V$ に対して、 $0 \leqq f(u,v) \leqq c(u,v)$ でなければならない。
フロー保存則: 全てのに対して、でなければならない。
- 頂点 u に入ってくるフローと、頂点 u から出ていくフローの量が等しい。

最大フロー問題は s から t への最大の値を持つフローを求める問題である。

逆平行辺

f:id:kenkoooo:20161021042256j:plain

逆平行辺を持つネットワークは簡単に逆平行辺を持たないグラフに構成し直すことが出来るので、議論を簡明にするため逆平行辺を禁止することにする。

複数の入口と出口

f:id:kenkoooo:20161021041928j:plain

複数の入口があっても超入口を作ってそこから各入口に容量無限の辺を張れば、入口 1 つのネットワークとして扱える。出口についても同様。

残余ネットワーク

辺 (u, v) に追加でどのくらいフローを流すことが出来るかを残余容量 $c_f(u, v)=c(u,v)-f(u,v)$ で表す。

$(v,u) \in E$ にフローが f(v, u) 流れているとき、フローを削減できることを表現するため、 $c_f(u,v)=f(v,u)$ と表せる。

これをまとめると、
$c_f(u,v) = \begin{cases} c(u,v)-f(u,v) & (u,v) \in E \\ f(v,u) & (v,u) \in E \\ 0 & それ以外 \end{cases}$

増加

f(u,v) 流れているフローを変化させることを考える。f を G におけるフロー、f' を残余容量からなる残余ネットワーク $G_f$ のフローとすると、変化後のフローは以下のように表される。

$(f \uparrow f')(u,v) = \begin{cases} f(u,v) + f'(u,v) - f'(v,u) & (u,v) \in E \\ 0 & それ以外 \end{cases}$

補題 26.1

$|f \uparrow f'| = |f|+|f'|$ である。

証明

まず、容量制限を満たすことを示す。
$\begin{eqnarray} (f \uparrow f')(u,v) &=& f(u,v)+f'(u,v)-f'(v,u) \\ &\geqq& f(u,v)+f'(u,v)-f(u,v) \\ &=& f'(u,v) \\ &\geqq& 0 \end{eqnarray}$

$\begin{eqnarray} (f \uparrow f')(u,v) &=& f(u,v)+f'(u,v)-f'(v,u) \\ &\leqq& f(u,v)+f'(u,v) \\ &\leqq& f(u,v)+c_f(u,v) \\ &=& f(u,v) +c(u,v) -f(u,v) \\ &=& c(u,v) \end{eqnarray}$

http://www.cs.dartmouth.edu/~thc/clrs-bugs/pages/pp-718-720.pdf

全ての $u\in V$ について以下の式が成り立つことを示す。
$\sum_{v \in V}(f\uparrow f')(u,v)- \sum_{v \in V}(f\uparrow f')(v,u) = \sum_{v \in V}f(u,v)-\sum_{v \in V}f(v,u)+\sum_{v \in V}f'(u,v)-\sum_{v \in V}f'(v,u)$

u から出る辺のもう一方の端点の集合を $V_1(u) = \{ v:(u,v) \in E \}$ と表す。
また、u へ向かう辺のもう一方の端点の集合を $V_2(u) = \{ v:(v,u) \in E \}$ と表す。

G には逆平行辺を含まれないので、 $V_1(u) \cap V_2(u)=\emptyset$

$\begin{cases} (f \uparrow f')(u,v)>0 & v \in V_1(u) \\ (f \uparrow f')(v,u)>0 & v \in V_2(u) \end{cases}$

$\begin{eqnarray} \sum_{v \in V}(f\uparrow f')(u,v)&-& \sum_{v \in V}(f\uparrow f')(v,u)\\ &=& \sum_{v \in V_1(u)}(f\uparrow f')(u,v)- \sum_{v \in V_2(u)}(f\uparrow f')(v,u) \\ &=& \sum_{v \in V_1(u)}(f(u,v)+f'(u,v)-f'(v,u))- \sum_{v \in V_2(u)}(f(v,u)+f'(v,u)-f'(u,v)) \\ &=& \sum_{v \in V_1(u)}f(u, v) - \sum_{v \in V_2(u)}f(v, u) + \sum_{v \in V_1(u)}f'(u, v) + \sum_{v \in V_2(u)}f'(u, v) - \sum_{v \in V_1(u)}f'(v,u) - \sum_{v \in V_2(u)}f'(v, u) \\ &=& \sum_{v \in V_1(u)}f(u, v) - \sum_{v \in V_2(u)}f(v, u) + \sum_{v \in V_1(u) \cup V_2(u)}f'(u, v) - \sum_{v \in V_1(u) \cup V_2(u)}f'(v,u) \end{eqnarray}$

$\begin{eqnarray} |f \uparrow f'| &=& \sum_{v \in V}(f \uparrow f')(s,v) -\sum_{v \in V}(f \uparrow f')(v,s) \\ &=& \sum_{v \in V}f(s,v)- \sum_{v \in V}f(v, s) + \sum_{v \in V}f'(s,v)- \sum_{v \in V}f'(v, s) \\ &=& |f|+|f'| \end{eqnarray}$

増加可能経路

残余ネットワーク $G_f$ 上での s から t への経路。

増加可能経路 p の各辺に沿って増やすことの出来るフローの最大値を p の残余容量とし、以下のように定義する。
$c_f(p) =min\{c_f(u,v): (u, v) は p 上にある \}$

補題 26.2

関数 $f_p$ を以下のように定義する。

$f_p(u, v)= \begin{cases} c_f(p) & (u,v) が p 上にあるとき \\ 0 & それ以外 \end{cases}$

このとき、 $f_p$ は $G_f$ のフローで $|f_p|=c_f(p) > 0$ である。

$| f \uparrow f_p| =|f|+|f_p| > |f|$ より、 $f_p$ を $f$ に加えると、より最大値に近い f を得られる。

フローネットワークのカット

V を $s \in S$ と $t \in T$ を満たす S と T=V-S に分割する。これをカット (S, T) とする。

カット(S,T) と交差する純フローを
$f(S,T) =\sum_{u\in S} \sum_{v\in T}f(u,v) -\sum_{u\in S} \sum_{v\in T}f(v,u)$
と定義する。

カットの容量は $c(S,T)=\sum_{u\in S}\sum_{v\in T} c(u,v)$ である。

最小カットは、カット(S, T)の中で、容量が最小のカットである。

補題 26.4

カット(S, T)と交差する純フローは f(S, T)=|f| である。

証明

$\begin{eqnarray} | f | &=& \sum_{v \in V}f(s,v) - \sum_{v \in V}f(v,s)\\ &=& \sum_{v \in V}f(s,v) - \sum_{v \in V}f(v,s) +\sum_{u \in S-\{s\} }\big( \sum_{v\in V}f(u,v)- \sum_{v\in V}f(v,u) \big)\\ &=& \sum_{v \in V}f(s,v) - \sum_{v \in V}f(v,s) +\sum_{u \in S-\{s\} } \sum_{v\in V}f(u,v)- \sum_{u \in S-\{s\} }\sum_{v\in V}f(v,u) \\ &=& \sum_{v \in V} \big( f(s,v) +\sum_{u \in S-\{s\} } f(u,v)\big) - \sum_{v \in V} \big( f(v,s) +\sum_{u \in S-\{s\} } f(v,u)\big) \\ &=& \sum_{v \in V} \sum_{u\in S}f(u, v)- \sum_{v \in V} \sum_{u\in S}f(v, u) \\ &=& \sum_{v \in S} \sum_{u\in S}f(u, v) + \sum_{v \in T} \sum_{u\in S}f(u, v) - \sum_{v \in S} \sum_{u\in S}f(v, u) - \sum_{v \in T} \sum_{u\in S}f(v, u) & (V=S \cup T かつ S \cap T = \emptyset だから)\\ &=& \sum_{v \in T} \sum_{u\in S}f(u, v) - \sum_{v \in T} \sum_{u\in S}f(v, u) +\big( \sum_{v \in S} \sum_{u\in S}f(u, v) - \sum_{v \in S} \sum_{u\in S}f(v, u) \big) \\ &=& \sum_{v \in T} \sum_{u\in S}f(u, v) - \sum_{v \in T} \sum_{u\in S}f(v, u) \\ &=& f(S,T) \end{eqnarray}$

系 26.5

G の任意のフロー f の値は G の任意のカット容量によって上から抑えられる。

証明

$\begin{eqnarray} |f| &=& f(S,T)\\ &=& \sum_{v \in T} \sum_{u\in S}f(u, v) - \sum_{v \in T} \sum_{u\in S}f(v, u)\\ &\leqq& \sum_{v \in T} \sum_{u\in S}f(u, v) \\ &\leqq& \sum_{v \in T} \sum_{u\in S}c(u, v) \\ &=&c(S, T) \end{eqnarray}$

定理 26.6 最大フロー最小カットの定理

fはGの最大フローである。
残余ネットワーク Gf は増加可能経路を含まない。
Gのあるカット(S,T)に対して|f|=c(S,T) である。

証明

最大フローであるにも関わらず増加可能経路を持つと仮定すると、 $f_p$ が定まり、|f| より値が大きいGのフローが得られるので矛盾する。

Gf が増加可能経路を持たないとき、Gfにはsからtへの道が存在しない。

$S=\{ v \in V: G_f に s から v への道が存在する \}, T=V-S$ と定義する。

明らかに $s\in S$ であり、 $G_f$ にはsからtへの道が存在しないので $t\not\in S$ である。よって、この分割(S,T)はカットである。

$u\in S$ かつ $v\in T$ かつ $(u,v) \in E$ であるようなu, v を考える。
$f(u,v)\not= c(u,v)$ ならば $(u,v)\in E_f$ であり、 $v\in S$ となり矛盾する。よって $f(u,v)= c(u,v)$ である。

$f(v,u)\not=0$ ならば $c_f(u,v)=f(v,u)$ で $(u,v)\in E_f$ だから $v\in S$ となり矛盾する。よって $f(v,u)=0$

$\begin{eqnarray} f(S,T) &=& \sum_{u\in S}\sum_{v\in T}f(u,v)-\sum_{u\in S}\sum_{v\in T}f(v,u) \\ &=& \sum_{u\in S}\sum_{v\in T}c(u,v)-\sum_{u\in S}\sum_{v\in T}0 \\ &=&c(S,T) \end{eqnarray}$

全てのカット(S, T) に対して $|f| \leqq c(S,T)$ である。よって $|f| = c(S,T)$ はfが最大フローであるための十分条件である。

過剰量とプリフロー

今までは頂点にフローを溜め込むことができない条件のみを考えてきた。

頂点 u に流入するフローと頂点 u から流出するフローの合計が等しかった。
$\begin{eqnarray} \sum_{v \in V-\{s\}} f(v,u) - \sum_{v \in V-\{s\}}f(u,v) = 0 \end{eqnarray}$

これを緩和して、流入量が流出量を超えることが出来るものとする。
$\begin{eqnarray} \sum_{v \in V-\{s\}} f(v,u) - \sum_{v \in V-\{s\}}f(u,v) \geq 0 \end{eqnarray}$

このような条件でのフローをプリフローと呼ぶ。

この過剰量を e(u) とする。

$u\in V-\{s\}$ について、
$\begin{eqnarray} e(u) = \sum_{v \in V} f(v,u) - \sum_{v \in V}f(u,v) \end{eqnarray}$

$e(u)>0$ となるような頂点 $u \in V-\{s,t\}$ をオーバーフロー頂点と呼ぶ。

高さ関数

$h(s)=|V|, h(t)=0$ であり、残余辺 $(u,v)\in E_f$ について、 $h(u)\leq h(v)+1$ が成り立つような高さ関数 h を考える。

プッシュ操作

以下の条件を満たす残余辺 (u, v) について、u から v にフローをプッシュする。
$\begin{eqnarray} \begin{cases} h(u)=h(v)+1 \\ c_f(u,v)>0 \\ e(u) > 0 \end{cases} \end{eqnarray}$

Push(u, v)
    # 適用条件: u がオーバーフロー頂点で、c_f(u, v) > 0 かつ h(u) = h(v) + 1
    df = min(e(u), c_f(u, v))
    if (u, v) in E
        (u, v).f = (u, v).f + df
    else
        (v, u).f = (v, u).f - df
    e(u) -= df
    e(v) += df

プッシュ後に $c_f(u,v)=0$ となるようなプッシュを飽和プッシュと呼ぶ。

再ラベル操作

$e(u)>0$ かつ $(u,v) \in E_f$ の全ての v について $h(u) \leq h(v)$ であるとき、u の高さを上げる。

Relabel(u)
    # 適用条件: u がオーバーフロー頂点、かつ、h(u) <= h(v)
    h(u) = 1 + min([h(v) for (u, v) in E_f])

基礎アルゴリズム

Initialize-Preflow(G, s)
    for v in V
        h(v) = 0
        e(v) = 0
    for (u, v) in E
        (u, v).f = 0
    h(s) = |V|
    for v in G[s]
        (s, v).f = c(s, v)
        e(v) = c(s,v)
        e(s) -= c(s, v)

これによって s から出る全ての辺に容量上限までフローを流す。
つまり、s から出る辺は残余グラフに含まれなくなる。
よって全ての残余辺 $(u,v) \in E_f$ について $h(u) \leq h(v)+1$ が成り立つ。
（全ての $u \in V-\{s\}$ について $h(u)=0$ だから）

Generic-Push-Relabel(G)
    Initialize-Preflow(G, s)
    while 適用可能な push か relabel がある
        適用可能な push か relabel を選び、実行する

Push-Relabel の正当性

アルゴリズムが停止したときプリフロー f が最大フローであることと、アルゴリズムが停止することを示す。

補題 26.14

u がオーバーフロー頂点であれば、push か relabel が実行可能である。

証明

u から push が実行可能でない場合、全ての残余辺 $(u, v) \in E_f$ について、 $h(u) < h(v)+1$ である。
このとき、 $h(u) \leq h(v)$ であり、relabel が実行可能である。

補題26.15

Generic-Push-Relabel の実行中、h(u) は減少しない。

証明

h(u) は relabel 以外では変化せず、relabel では適用のたびに必ず 1 以上増える。

補題26.16

Generic-Push-Relabel は h を高さ関数として維持する。

証明

初期状態では h が高さ関数制約を満たしている。

u から出る辺 (u, v) を考える。
Relabel(u) を行った後は $h(u) \leq h(v)+1$ が保証される。

u に入る辺 (w, u) を考える。
Relabel(u) の前に $h(w) \leq h(u) +1$ が成立していたならば、操作後は $h(w) < h(u) +1$ が成立する。

よって Relabel(u) は高さ制約を維持する。

Push(u, v) を実行することを考える。

Push(u, v) によって $f(v, u)$ が減少するとき、 $c_f(v,u)$ が増加する。
これは $E_f$ に (v, u) が加わると考えられる。
このとき $h(u)=h(v)+1$ だから $h(v)=h(u)-1< h(u)+1$ である。
新しい残余辺 (v, u) について $h(v) \leq h(u)+1$ が成り立つ。

Push(u, v) によって $c_f(u,v)$ が減少するとき、 $E_f$ から (u, v) が取り除かれると考える。
このときは、制約が取り除かれるので、再び h は高さ関数である。

補題26.17

f をプリフローとする。このとき残余グラフ $G_f$ には s から t への道はない。

証明

矛盾を導くために $G_f$ における s から t への道 $p = < v_0,v_1,...,v_k >$ が存在すると仮定する。
$v_0=s, v_k=t$ である。
一般性を失うことなく $k<|V|$ と仮定する。

$i=0,1,...,k-1$ に対して $(v_i,v_{i+1}) \in E_f$ である。
$i=0,1,...,k-1$ に対して $h(v_i)\leq h(v_{i+1}) +1$ である。
よって $h(s)\leq h(t)+k$ である。
ここで $h(t)+k=0+k=k$ だから $h(s)\leq k <|V|$ となり、高さ関数制約 $h(s)=|V|$ に矛盾する。

補題26.18

Generic-Push-Relabel を実行して停止したとき、プリフロー f は最大フローである。

証明

Initialize-Preflow 実行後の f はプリフローである。

while ループ内では push と relabel が実行される。
relabel は f に影響しない。
push 実行前に f がプリフローならば、実行後も f はプリフローである。

補題 26.14 より、停止したときは $V-\{s,t\}$ にオーバーフロー頂点は存在しない。
よって $v \in V-\{s,t\}$ について e(v)=0 である。
よって、プリフロー f はフローである。

補題 26.17 より、残余ネットワーク $G_f$ には s から t への道が存在しない。
よってフロー f は最大フローである。

Generic-Push-Relabel の解析

補題 26.19

f をプリフローとする。この時、残余ネットワーク $G_f$ の任意のオーバーフロー頂点 u から s への単純道が存在する。

証明

オーバーフロー頂点 x について、 $U=\{v: G_f において xからvへの単純道がある\}$ とする。
s が U に含まれることを示す。

矛盾を導くために $s \not\in U$ を仮定する。
$\overline{U}=V-U$ とする。

$\begin{eqnarray} e(u) = \sum_{v \in V} f(v,u) - \sum_{v \in V}f(u,v) \end{eqnarray}$
より、
$\begin{eqnarray} \sum_{u\in U}e(u) &=& \sum_{u\in U}\big( \sum_{v \in V} f(v,u) - \sum_{v \in V}f(u,v) \big) \\ &=& \sum_{u\in U}\big( \big( \sum_{v \in U} f(v,u) + \sum_{v \in \overline{U}} f(v,u) \big) - \big( \sum_{v \in U} f(u,v) + \sum_{v \in \overline{U}} f(u,v) \big) \big) \\ &=& \sum_{u\in U}\sum_{v \in U}f(v,u)+ \sum_{u\in U}\sum_{v \in \overline{U}}f(v,u)-\sum_{u\in U}\sum_{v \in U}f(u,v)- \sum_{u\in U}\sum_{v \in \overline{U}}f(u,v)\\ &=& \sum_{u\in U}\sum_{v \in \overline{U}}f(v,u)- \sum_{u\in U}\sum_{v \in \overline{U}}f(u,v)\\ \end{eqnarray}$

$e(x)>0, x \in U$ かつ、s以外のすべての頂点が非負の過剰を持ち、 $s\not\in U$ だから、 $\sum_{u\in U}e(u)>0$ である。

したがって
$\begin{eqnarray} \sum_{u\in U}\sum_{v \in \overline{U}}f(v,u)- \sum_{u\in U}\sum_{v \in \overline{U}}f(u,v) > 0 \end{eqnarray}$

フローは非負だから
$\begin{eqnarray} \sum_{u\in U}\sum_{v \in \overline{U}}f(v,u) > 0 \end{eqnarray}$

よって $f(v',u')>0$ となる $u' \in U, v' \in \overline{U}$ が存在する。
よって残余ネットワーク $G_f$ には残余辺 $(u',v')$ が存在する。

よって道 $x\leadsto u' \to v'$ が存在する。これは $v' \in U$ となり矛盾。

補題 26.20

Generic-Push-Relabel 実行中はすべての頂点 u で $h(u) \leq 2|V| -1$ が成り立つ。

証明

h(s)=|V|, h(t)=0 なので、 $u \in V-\{s,t\}$ となる頂点 u について考える。

u から s への単純道 $p=< v_0, ..., v_k >$ にを考える。ここでは $v_0=u, v_k=s$ である。pは単純道なので $k< |V|-1$ である。

$h(v_i)\leq h(v_{i+1})+1$ だから

$h(v_0)=h(v_0) \leq h(v_k)+k \leq h(s)+(|V|-1)=2|V|-1$

系 26.21

relabel の回数は頂点当たり高々 $2|V|-1$ 回である。

証明

各頂点の高さ関数 h(u) は最大で $2|V|-1$ 回上がる。はい。

補題 26.22

飽和プッシュ回数は $2|V||E|$ 回未満である。

証明

u から v への飽和プッシュが発生するとき、 $h(v)=h(u)-1$ である。
同様に v から u への飽和プッシュが発生するとき、 $h(v)=h(u)+1$ である。
つまり、u から v への飽和プッシュが起こった後、v から u への飽和プッシュが起こるまでに h(v) は少なくとも 2 増加する。
h(v) の最大値は 2|V|-1 なので、u と v の間に起こる飽和プッシュの回数は 2|V| 回未満であり、辺の本数を考えると全体で 2|V||E| 未満である。

補題 26.23

非飽和プッシュ回数は $4|V|^2(|V|+|E|)$ 回である。

証明

ポテンシャル関数 $\Phi$ を定義する。

$\begin{eqnarray} \Phi = \sum_{v :e(v)>0} h(v) \end{eqnarray}$

頂点 u の relabel によって $\Phi$ は高々 2|V|-1 だけ増加する。
頂点 u からの飽和プッシュによって $\Phi$ は高々 2|V|-1 だけ増加する。

頂点 u から v への非飽和プッシュを考える。
この操作により e(u)=0 となるので、h(u) は和の対象から外れ、 $\Phi$ は正確に h(u) だけ減少する。
v がもともとオーバーフロー頂点だったとき、 $\Phi$ の増加量は 0 である。
v が新たにオーバーフロー頂点となる場合、 $\Phi$ は h(v) だけ増加する。
h(u)=h(v)+1 だから、 $\Phi$ は少なくとも 1 減少する。

relabel 回数の上界が (2|V|-1)(|V|-2) 回、飽和プッシュ回数の上界が 2|V||E| 回、だから、relabel の上界を $2|V|^2$ として、 $\Phi$ の増加量の上界は
$(2|V|)(2|V|^2)+(2|V|)(2|V||E|) = 4|V|^2(|V|+|E|)$ である。

$\Phi$ は非飽和プッシュによって減少するので、非飽和プッシュ回数の上界は $4|V|^2(|V|+|E|)$ である。

許容辺

c_f(u, v) > 0 かつ h(u) == h(v) + 1 を満たすとき、辺(u, v)を許容辺という。

補題26.27

辺(u,v)へのプッシュ操作push(u,v)は新たな許容辺を作らない。

証明

(u,v)へプッシュ可能なとき、h(u)=h(v)+1である。(u,v)へのプッシュ操作によって唯一新たに残余辺(v,u)が生成しうるが、h(v)=h(u)-1であるためこれは許容辺ではない。よってプッシュ操作では新たな許容辺は作られない。

補題26.28

頂点uがオーバーフロー頂点で、uから外に向かう許容辺がなければrelabel(u)が適用できる。また、この操作の後、少なくとも1本はuから外へ向かう許容辺が存在し、uに入る許容辺は存在しない。

証明

uがオーバーフロー頂点なら、補題26.14よりプッシュかリラベル操作ができる。uから外へ向かう許容辺がないときプッシュ操作ができないので、リラベル操作ができる。リラベル操作終了後は $h(u) = 1+\{h(v) : (u,v)E_f\}$ となり、辺(u,v)が許容辺となるような頂点vが存在し、uからvへ向かう許容辺が出来る。

リラベル操作終了後に、vからuに入る許容辺(v,u)が存在していると仮定すると、h(v)=h(u)+1であることから、リラベル操作終了前にはh(v)>h(u)+1であったことになる。しかし、高さが2以上違う頂点の間には残余辺が存在しないので、矛盾する。

オーバーフロー頂点での開栓

Discharge(u):
    while e(u) > 0:
        it = G[u].next()
        if it is None:
            Relabel(u)
            it = G[u].iterator()
        elif c_f(u, v) > 0 and h(u) == h(v) + 1:
            Push(u, v)
        else:
            it = G[u].next()

補題26.29

discharge(u)がrelabel(u)を呼び出すとき、uに対してリラベル操作が可能である。

証明

relabel(u)が呼び出されるとき、uから外に向かう許容辺が存在しないことを示す。

relabel(u)が呼び出されるとき、uから外へ向かう辺のうち許容辺であるものは全てプッシュ操作が適用された後である。補題26.27より、これらのプッシュ操作およびグラフ内で起こった別のプッシュ操作によって新たに許容辺が作られることはない。別の discharge(v)によってrelabel(v)が起こった場合、補題26.28よりvに入る許容辺が新たに生成されることはないため、uから外へ出る許容辺が新たに生成されることはない。

よって、relabel(u)が呼び出されるとき、uから外に向かう許容辺が存在しない。

アルゴリズム

Relabel-To-Front(s, t):
    Initialize-Preflow()
    L = []
    for u in G:
        if u != s and u != t:
            L.append(u)
    it = L.iterator()
    u = it.next()
    while u != None:
        old = h(u)
        Discharge(u)
        if h(u) > old:
            u を L の先頭に移動
            it = L.iterator()
        u = it.next()

任意の順番で頂点を見ていって、dischargeして高さが変わっているならその頂点をリストの先頭に持っていってリスタート、という感じである。

定理26.30

計算量は $O(V^3)$ だよ。

証明

リラベル操作とリラベル操作の間をフェーズと呼ぶことにする。

リラベル操作は $O(V^2)$ 回行われるので、 $O(V^2)$ 回のフェーズがある。dischargeがrelabel操作を呼び出さないとき、dischargeはリストを順番に見ていくので、高々|V|回行われる。一方、dischargeがrelabelを呼び出すと、その次に実行されるdischargeは別のフェーズのものとなる。よって、各フェーズで呼び出されるdischargeは高々|V|回であり、dischargeの総呼び出し回数は $O(V^3)$ 回である。

飽和プッシュの回数は全部で $O(VE)$ である。非飽和プッシュが行われるとdischargeは直ちに終了する。よって非飽和プッシュの総実行回数は $O(V^3)$ である。

よって、計算量は $O(V^3)$ だよ。

Highest-Label Rule

オーバーフロー頂点のうち、高さの最も高い頂点で開栓し続ければ良い。

https://resources.mpi-inf.mpg.de/departments/d1/teaching/ws09_10/Opt2/handouts/lecture4.pdf
https://www.cs.princeton.edu/courses/archive/spring13/cos528/PreflowPushBiggestLabelSelectionAnalysis.pdf

補題4.2

非飽和プッシュ回数は $O(V^2\sqrt{E})$

証明

ポテンシャル関数
$\begin{eqnarray} \Phi = \sum_{u :e(u)>0} |\{v | h(v)\leq h(u)\}| \end{eqnarray}$ を定義する。

リラベル操作や飽和プッシュ操作によって $\Phi$ は最大Vだけ増加する。リラベル操作は全部で $O(V^2)$ 回、飽和プッシュ操作は全部で $O(VE)$ 回行われるので、全体で $\Phi$ の増加量は $O(V^2E)$ である。

オーバーフロー頂点のうち、高さが最大のものをuとする。h(u)を変化させるリラベルの間に起こった非飽和プッシュたちをフェーズと呼ぶことする。リラベル操作を行ったり、uの過剰フローを次の高さの頂点に全てプッシュし終えたりするとフェーズは終了する。各頂点ごとに必ず1回は非飽和プッシュが存在し、最大でも $4V^2$ 回のフェーズがある（リラベル操作の2倍の回数）。

k回以上の非飽和プッシュが行われるフェーズをbigとし、それ以外のフェーズをsmallとする。smallフェーズでは最大でk回の非飽和プッシュが行われるので、全体で $4kV^2$ 回行われる。bigフェーズでは高さが最大の頂点がk個以上存在するので、1回の非飽和プッシュで少なくともポテンシャルはk減少する。全体で $\Phi$ の増加量は $O(V^2E)$ であるから、bigフェーズの非飽和プッシュは全体で $O(V^2E/k)$ 回である。よってbigとsmallの非飽和プッシュの回数は合計で $O(V^2E/k + V^2k)$ である。ここで $k=\sqrt{E}$ とすると、 $O(V^2 \sqrt{E})$ となる。

実装

import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;

public class RelabelToFront {
  class Edge {
    int from, to, rev;
    long flow, cap;
    Edge(int from, int to, long cap, int rev) {
      this.from = from;
      this.to = to;
      this.cap = cap;
      this.rev = rev;
      this.flow = 0;
    }
  }

  private int N;
  private ArrayList<ArrayList<Edge>> graph = new ArrayList<>();
  private long[] excess;
  private int[] height;
  private int[] seen;
  private PriorityQueue<int[]> queue = new PriorityQueue<>(Comparator.comparingInt(o -> -o[0]));

  RelabelToFront(int N) {
    this.N = N;
    for (int i = 0; i < N; i++) graph.add(new ArrayList<>());
    excess = new long[N];
    height = new int[N];
    seen = new int[N];
  }

  public void addEdge(int from, int to, long cap) {
    graph.get(from).add(new Edge(from, to, cap, graph.get(to).size()));
    graph.get(to).add(new Edge(to, from, 0, graph.get(from).size() - 1));
  }

  private void push(Edge e) {
    int u = e.from;
    int v = e.to;

    long send = Math.min(excess[u], e.cap - e.flow);
    e.flow += send;
    graph.get(v).get(e.rev).flow -= send;
    excess[u] -= send;
    excess[v] += send;

    if (excess[v] > 0) queue.add(new int[]{height[v], v});
    if (excess[u] > 0) queue.add(new int[]{height[u], u});
  }

  private void relabel(int u) {
    int minHeight = N * 2;
    for (Edge e : graph.get(u))
      if (e.cap - e.flow > 0)
        minHeight = Math.min(minHeight, height[e.to]);
    height[u] = minHeight + 1;

    queue.add(new int[]{height[u], u});
  }

  private void discharge(int u) {
    while (excess[u] > 0) {
      if (seen[u] < graph.get(u).size()) {
        Edge e = graph.get(u).get(seen[u]);
        if (e.cap - e.flow > 0 && height[u] == height[e.to] + 1)
          push(e);
        else
          seen[u] += 1;
      } else {
        relabel(u);
        seen[u] = 0;
      }
    }
  }

  public long maxFlow(int source, int sink) {
    height[source] = N;
    for (Edge e : graph.get(source)) {
      excess[source] += e.cap;
      push(e);
    }

    while (!queue.isEmpty()) {
      int[] q = queue.poll();
      int u = q[1];
      if (u == source || u == sink) continue;
      discharge(u);
    }

    long maxFlow = 0;
    for (Edge e : graph.get(source)) maxFlow += e.flow;

    return maxFlow;
  }
}

終わりに

くぅ～疲れましたw これにて完結です！
実は、会社の輪読会で最大フローの章を担当したのが始まりでした
本当はRelabel-To-Frontに辿り着く前に力尽きてしまったのですが←
ご厚意を無駄にするわけには行かないので流行りのアドベントカレンダーで挑んでみた所存ですw
以下、Mi_Sawaさんのみんなへのメッセジをどぞ

「動的木を使うともっと速くなります」

追記

ぼくからのみんなへのメッセジ, どちらかというと, 「3つくらいヒューリスティックを入れるともっと速くなります」ですかね. (動的木使うくらいならアルゴリズム変える)
— みさわ (@Mi_Sawa) 2016年12月22日