RCO アルゴリズムイントロダクション輪読会 26. 最大フロー 3

前回のページ

kenkoooo.hatenablog.com

内容は大体かぶってます。

プッシュ再ラベルアルゴリズム

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

頂点 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 は最大フローである。

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|)$ である。

計算量

$O(V^2E)$