Edmonds と Karp のアルゴリズム

Ford と Fulkerson のアルゴリズムは残余グラフのどの路を増加させるかを指定しません。このアルゴリズムの最悪計算時間がひどいのは、増加路の選び方をいくらでも悪くできるのが原因です。1970 年代前半、Jack Edmonds (ジャック・エドモンズ) と Richard Karp (リチャード・カープ) は増加路を選ぶための二つの自然な方法を解析し、どちらを使った場合でもより効率の良いアルゴリズムが得られることを示しました。

最幅増加路

Edmonds と Karp が解析した一つ目の規則を次に示します。この規則を使ったアルゴリズムは本質的に貪欲アルゴリズムとなります:

ボトルネックの値が一番大きい増加路を選ぶ。

Jarník の最小全域木アルゴリズムまたは Dijkstra のアルゴリズムに似た "最良優先探索" アルゴリズムを使えば、有向グラフの最大ボトルネック \((s,t)\)-路を \(O(E \log V)\) 時間で計算できます。このアルゴリズムは \(T = \lbrace s \rbrace\) から始めて \(T\) から伸びる容量の一番大きい辺を \(T\) に加えていくことで \(s\) を根とする有向木 \(T\) を成長させ、\(T\) に \(t\) が追加されたらその時点で終了するというものです。あるいは Kruskal のアルゴリズムに似たもの ――容量の降順に辺を木に追加していき、\(s\) から \(t\) への路が完成するまで続ける―― を使っても同じ処理はできますが、グラフが有向である場合にはこのアプローチは低速になります。

フローアルゴリズムの実行時間解析を完了させるには、アルゴリズムが停止するまでの反復回数の上限が必要です。実は、容量が実数だとこのアルゴリズムが停止しない場合があります (練習問題 10.19 で扱います)。しかし容量が整数なら、実行時間は最大フローの値 \(|f^{\ast}|\) を使うことで次のように解析できます。

\(f\) を \(G\) の任意のフローとし、\(f^{\prime}\) を現在の残余グラフ \(G_{f}\) における最大フローとします (例えばアルゴリズムが始まった時点では \(G_{f} = G\) および \(f^{\prime} = f^{\ast}\) です)。前に示した \(f^{\prime}\) が最大 \(E\) 個の路と閉路に分解できるという事実と平均値を使った簡単な議論から、この分解に含まれる少なくとも一つの路には \(|f^{\prime}| / E\) 以上のフローが流れることが分かります。よって \(G_{f}\) に含まれる最も幅の大きい \((s,t)\)-路は \(|f^{\prime}| / E\) 以上の幅を持ちます。

したがって \(G_{f}\) に含まれる最大ボトルネック路で \(f\) を増加させると、残余グラフ \(G_{f}\) の最大フローの値は \(1 - 1/E\) 倍以下になります。これを言い換えると、残余最大フローの値は反復回数に対して指数的に小さくなるということです。\(E \cdot \ln |f^{\ast}|\) 回の反復の後、\(G_{f}\) に含まれる最大フローの値は \[ |f^{\ast}| \cdot (1 - 1/E)^{E \cdot \ln |f^{\ast}|} < |f^{\ast}| e^{-\ln |f^{\ast}|} = 1 \] を満たすので (この \(e\) は Euler の定数です。ごめんなさい)、\(E \cdot |f^{\ast}|\) 回の反復によって残余最大フローの値は \(1\) より小さくなります。もし容量が整数ならば残余最大フローの値も整数となるので、この値は \(0\) 、すなわち \(f\) は最大フローです！

まとめると、整数の容量を持つグラフに対する Edmonds-Karp の "最幅路" アルゴリズムの実行時間は \(\pmb{O(E^{2} \log E \log |f^{\ast}|)}\) となります。何も工夫をしない Ford-Fulkerson の最悪実行時間と違って、このアルゴリズムの実行時間は入力サイズの多項式で抑えられます。

Ford-Fulkerson のアルゴリズムと同じように、この "最幅路" アルゴリズムに任意の実数の容量を持つネットワークを入力すると無限ループになってスタックすることがあります。しかしここで述べた解析から、アルゴリズムが止まらない場合でもフロー \(f\) が極限において最大フローに限りなく近づくことが分かります。

最短増加路

Edmonds と Karp が解析した二つ目の規則を次に示します。この規則は Ford と Fulkerson が最大フローアルゴリズムを示した論文においても実用上のヒューリスティックとして提案されていました。またロシア人数学者 Yefim Dinitz (イェフィム・ディニッツ) も同じ規則に対する考察を Edmonds と Karp とは独立に 1979 年に発表しています¹。

辺の数が最小の増加路を選ぶ。

残余グラフに含まれる最短の増加路は幅優先探索によって \(O(E)\) 時間で見つけられます。意外にも、この規則を使ったアルゴリズムは辺の容量の値に関係なく多項式回の反復の後に停止します！

\(f_{i}\) を \(i\) 回の増加ステップの後のフローとし、\(G_{i}\) を \(f_{i}\) に対応する残余グラフとします。例えば \(f_{0}\) は全てがゼロのフローであり、\(G_{0} = G\) です。全ての頂点 \(v\) に対して、\(G_{i}\) における \(s\) から \(v\) への重み無し最短路の長さを \(\pmb{level_{i}(v)}\) とします。同じことですが、\(level_{i}(v)\) を \(s\) を根とする \(G_{i}\) の幅優先探索木における \(v\) の「高さ (level)」と定義することもできます。\(G_{i}\) において \(s\) から \(v\) への路が無い場合には \(level_{i}(v) = \infty\) となります (\(\min \varnothing = \infty\) だからです)。アルゴリズムの多項式上界の証明は残余グラフの変化に関する二つの観察を利用します。

一つ目の観察は \(level\) の非減少性です。

命題 10.2 全ての頂点 \(v\) と整数 \(i > 0\) について \(level_{i}(v) \geq level_{i-1}(v)\)。

証明 \(i > 0\) を任意の整数、\(v\) を適当な頂点とする。\(level_{i}(v)\) に対する帰納法で示す (\(i\) に対する帰納法ではない)。帰納法の仮定から、\(level_{i} (u) < level_{i} (v)\) を満たす任意の頂点 \(u\) について \(level_{i} (u) \geq level_{i-1} (u)\) が成り立つ。\(v\) について考えるべきケースは三つある:

\(v = s\) の場合、 \(level_{i}(s) = 0 \geq 0 = level_{i-1}(s)\) となって成り立つ。
\(G_{i}\) に \(s\) から \(v\) への路が無い場合、\(level_{i} (v) = \infty \geq level_{i-1}(v)\) となって成り立つ。
それ以外の場合、\(G_{i}\) における \(s\) から \(v\) への任意の最短路を \(s \rightarrow\) \(\cdots \rightarrow\) \(u \rightarrow v\) とする。この路が最短路であることから \(level_{i}(v) = level_{i}(u) + 1\) であり、帰納法の仮定から \(level_{i} (u) \geq level_{i-1} (u)\) なので、\(level_{i-1}(u) \geq level_{i-1}(v) - 1\) を示せばよい。\(u \rightarrow v\) について考えるべきケースがさらに二つある。
- \(G_{i-1}\) において \(u \rightarrow v\) が辺の場合、\(level_{i-1}(\cdot)\) は幅優先探索によって定義されることから \(level_{i-1}(v) \leq level_{i-1} (u) + 1\) が成り立つ。
- そうでなくて \(u \rightarrow v\) が \(G_{i-1}\) において辺でない場合、その逆 \(v \rightarrow u\) は \(i\) 番目の増加路に含まれる。今考えている規則からこの増加路は \(G_{i-1}\) における \(s\) から \(t\) への最短路だから、\(level_{i-1} (v) = \) \(level_{i-1} (u) {\color{red}{}-{}} 1 \leq \) \(level_{i-1} (u) {\color{red}{}+{}} 1\) が分かる。

よっていずれの場合でも \(level_{i} (v) = \) \(level_{i} (u) + 1 \geq \) \(level_{i-1} (u) + 1 \geq \) \(level_{i-1}(v)\) が成り立つ。 \(\Box\)

この証明で重要なのは、フローを追加すると増加路のボトルネック辺が残余グラフから消失し、増加路に含まれる辺のいくつかはその逆が残余グラフに (再び) 出現するという事実です。二つ目の観察はこの消失と出現の回数の上界に関するものです。

命題 10.3 Edmonds-Karp の最短増加路アルゴリズムにおいて、任意の辺 \(u \rightarrow v\) は最大でも \(V/2\) 回しか \(G_{f}\) から消失しない。

証明 \(u \rightarrow v\) が二つの残余グラフ \(G_{i}\) と \(G_{j+1}\) \((i < j)\) に現れ、その間の残余グラフ \(G_{i+1},\ldots, G_{j}\) には表れないとする。このとき \(u \rightarrow v\) が \(i\) 番目の増加路に含まれることから \(level_{i} (v) = level_{i} (u) + 1\) であり、\(v \rightarrow u\) が \(j\) 番目の増加路に含まれることから \(level_{j}(v) = level_{j}(u) - 1\) である。これと命題 10.2 より \[ level_{j}(u) = level_{j} (v) + 1 \leq level_{i} (v) + 1 = level_{i} (u) + 2 \] つまり \(u \rightarrow v\) が消失してもう一度出現すると、\(s\) から \(u\) への距離は少なくとも 2 増える。全ての頂点 \(v\) に対して \(level_{i} (v)\) は \(V\) より小さいかそうでなければ無限大なので、消失の回数は最大でも \(V/ 2\) 回である。 \(\Box\)

以上の観察から反復の回数の上界を求められます。全ての辺は最大でも \(V/2\) 回消失することから、全ての辺の消失の回数は \(EV/2\) 回以下です。一度の反復で消失することが保証されている辺は一本だけなので、このアルゴリズムは停止するまでに最大 \(EV/2\) 回だけ反復します。各反復には \(O(E)\) 時間がかかることから、アルゴリズム全体の実行時間は \(\pmb{O(VE^{2})}\) です。

Dinitz が発見した最大フローアルゴリズムはこれよりももっと複雑です。当時彼は Georgy Adelson-Velsky (ゲオルギー・アデルソン・ヴェルスキー、AVL 木の"AV") が担当するアルゴリズムの講義を受ける学生であり、Dinitz はそのアルゴリズムを練習問題の答として考案しました。このアルゴリズムも最短路に沿ってフローを追加していきますが、追加の情報を保持することで実行時間を \(O(VE^{2})\) から \(O(V^{2}E)\) に落としています。^[return]