最大フローと最小カット

1950 年代の中頃、米空軍の研究者 Theodore E. Harris (セオドア・E・ハリス) と米陸軍退役将校 Frank S. Ross (フランク・S・ロス) は、ソ連とその衛星国を結ぶ東ヨーロッパの鉄道ネットワークに関する機密レポートを作成しました。ネットワークは頂点を 44 個持つ辺に重みの付いたグラフとしてモデル化され、頂点が地域を、辺の重みが地域の間を輸送できる資源の量を表します。彼らは本質的には総当たりと変わらない方法を使って、ネットワークにおいてロシアからヨーロッパへ輸送できる資源の最大量、および最低限の辺を削除 (具体的に言うと、線路を爆破) してネットワークを崩壊させる方法を発見しました。この爆破すべき線路のことは「ボトルネック (bottleneck)」と呼ばれました。彼らのレポートに含まれる図を次に示します。このレポートの機密指定が解かれたのはやっと 1999 年のことです¹。

これは最大フロー (maximum flow) 問題と最小カット (minimum cut) 問題の記録に残っている範囲で最も古い応用の一つです。両方の問題において入力は有向グラフ \(G=(V,E)\) とソース (source) 頂点 \(s\) と シンク (sink) 頂点 \(t\) の三つです。直感的に言えば、最大フロー問題は \(s\) から \(t\) に輸送できる資源の最大量を計算し、最小カット問題は \(s\) と \(t\) を切り離すために必要なダメージの最小値を計算します。

フロー

\(\pmb{(s, t)}\)-フロー (ソースとシンクが明らかな場合には単にフロー) とは、関数 \(f:E \rightarrow \mathbb{R}\) であって \(s,t\) 以外の全ての頂点 \(v\) において次の保存条件 (conservation constraint) が満たされるものを言います: \[ \sum_{u} f(u \rightarrow v) = \sum_{w} f(v \rightarrow w) \]

保存条件を言葉を使って言い換えれば、全ての頂点 \(v\) に対して \(v\) に入るフローと \(v\) から出るフローが等しいということです。記法を単純にするために、辺 \(u \rightarrow v\) が存在しない場合には \(f(u \rightarrow v) = 0\) と定義します。フロー \(f\) の値 (value) \(|f|\) とはソース頂点 \(s\) から出るフローの和です: \[ |f| := \sum_{w} f(s \rightarrow w) - \sum_{u} f(u \rightarrow s) \]

\(|f|\) がシンク頂点 \(t\) へ向かうフローの和とも等しいことを示すのは難しくありません。記法を単純にするために、\(\pmb{\partial f(v)}\) で頂点 \(v\) から出るフローを表すことにします: \[ \partial f (v) := \sum_{w} f(v \rightarrow w) - \sum_{u} f(u \rightarrow v) \] 保存条件から \(s, t\) 以外の頂点 \(v\) について \(\partial f(v) = 0\) であり、したがって \[ \sum_{v} \partial f(v) = \partial f(s) + \partial f(t) \] です。一方で全てのフローはある頂点から出て他の頂点に入るので \(\sum_{v} \partial f (v) = 0\) であり、したがって \(|f| = \partial f(s) = - \partial f(t)\) が成り立ちます。

ここでグラフの辺に非負の容量 (capacity) を割り当てるもう一つの関数 \(c: E \rightarrow \mathbb{R}_{\geq 0}\) が追加で与えられたとします。フロー \(f\) が容量 \(c\) に対して実現可能 (feasible) であるとは、全ての辺 \(e\) に対して \(0 \leq f(e) \leq c(e)\) が成り立つことを言います。フローを考えると言った場合に通常考えるのは、何らかの固定された容量関数 \(c\) に対する実現可能なフローです。またフロー \(f\) と容量関数 \(c\) について、辺 \(e\) で \(f(e) = c(e)\) が成り立つならば \(f\) は \(e\) を 飽和 (saturate) させると言い、\(f(e) = 0\) ならば \(f\) は \(e\) を避ける (avoid) と言います。

最大フロー問題 (maximum flow problem) とは、与えられた有向グラフと容量関数に対する実現可能な \((s,t)\)-フローであって値が最大のものを計算する問題です。

カット

\(\pmb{(s, t)}\)-カット (ソースとシンクが明らかな場合は単にカット) とは、頂点集合の互いに素な二つの部分集合 \(S, T\) への分解であって \(s \in S\) かつ \(t \in T\) を満たすものを言います。\(S\) と \(T\) が互いに素とは \(S \cup T = V\) かつ \(S \cap V = \varnothing\) ということです。

容量関数 \(c:E \rightarrow \mathbb{R}_{\geq 0}\) が与えられたとき、カットの容量 (capacity) が \(S\) から \(T\) に向かう辺の容量の和として定義されます: \[ \| S, T \| = \sum_{s \in S} \sum_{t \in T} c(s \rightarrow t) \] (ここでも辺 \(v \rightarrow w\) が存在しない場合には \(c(v \rightarrow w) = 0\) とします) この定義が非対称なことに注意してください。\(T\) から \(S\) に向かう辺はカウントしません。

最小カット問題 (minimum cut problem) とは、容量が最小の \((s,t)\)-カットを計算する問題です。

直感的に言えば、最小カットとは \(s\) から \(t\) への全てのフローを断ち切るための一番安価な方法です。フローとカットに関する次の関係を示すのは難しくありません:

この命題から、もし \(|f| = \| S, T \|\) ならば \(f\) が最大フローで \((S, T)\) が最小カットであることが分かります。

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

意外なことに、任意のフローネットワークは \(|f| = \| S, T \|\) を満たす \((s,t)\)-フロー \(f\) と \((s,t)\)-カット \((S, T)\) を必ず持ちます。これが有名な最大フロー最小カット定理 (Maxflow-Mincut Theorem) です。この定理は Lester Ford (レスター・フォード、最短路アルゴリズムで知られる) と Delbert Fulkerson (デルバート・ファルカーソン) によって 1954 年に初めて証明され、1956 年には Peter Elias (ピーター・イライアス) と Amiel Feinstein (アミエイ・ファインスタイン) と Claude Shannon (クロード・シャノン、迷路を解くロボットと情報理論で知られる) によって独立に証明されています。

これから示すのは Ford と Fulkerson が行った証明です。\(G\) を任意のグラフ、\(s, t\) を \(G\) の適当な頂点、\(c:E \rightarrow \mathbb{R}_{\geq 0}\) を容量関数とします。証明はグラフが既約 (reduced) であること、つまり \(u\) と \(v\) の間には最大でも一つの辺しかないことを仮定すると簡単になります。既約という条件を言い換えると、任意の \(u \rightarrow v\) について \(c(u \rightarrow v) = 0\) または \(c( v \rightarrow u) = 0\) の少なくとも一方が必ず成り立つということです。この仮定は任意のグラフに対して簡単に強制できます: \(G\) の全ての辺に対して新しい頂点 \(x\) を追加し、 \(u \rightarrow v\) という辺を \(u \rightarrow x \rightarrow v\) という路に入れ替え、\(c(u \rightarrow x) =\) \(c (x \rightarrow v) = \) \(c(u \rightarrow v)\) と定義すると、改変されたグラフは元のグラフと同じ最大フローの値と最小カットの容量を持つ既約なグラフとなるためです。

\(G\) における任意の実現可能な \((s,t)\)-フローを \(f\) とし、\(f\) に対応する新しい容量関数 \(c_{f} : V \times V \rightarrow \mathbb{R}\) を次のように定義します。この容量関数を残余容量 (residual capacity) と呼びます: \[ c_{f} (u \rightarrow v) = \begin{cases} c(u \rightarrow v) - f (u \rightarrow v) & \text{if } u \rightarrow v \in E \\ f(v \rightarrow u) & \text{if } v \rightarrow u \in E \\ 0 & \text{それ以外} \end{cases} \] 直感的に言えば、ある辺の残余容量は現在その辺に流れている値に追加して流すことのできるフローの量を表します。\(f \geq 0\) かつ \(f \leq c\) なので残余容量の値は非負です。

元のグラフ \(G\) に辺 \(u \rightarrow v\) が存在しなかったとしても \(c_{f}(u \rightarrow v) > 0\) となることがあり得ます。そのため \(E_{f}\) を残余容量が正である辺の集合とすると、\(G_{f} = (V, E_{f})\) は (\(G\) と異なるグラフである)残余グラフ (residual graph) を定義します。ほとんどの場合において、残余グラフは既約ではありません。具体的には \(0 < f ( u \rightarrow v) < c(u \rightarrow v) \) が成り立つとき、残余グラフ \(G_{f}\) には辺 \(u \rightarrow v\) と辺 \(v \rightarrow u\) の両方が含まれます。

ここで考えるべきケースが二つあります。一つは残余グラフに \(G_{f}\) にソース頂点 \(s\) からシンク頂点 \(t\) までの有向路が存在する場合で、もう一つはそのような有向路が存在しない場合です。

まず残余グラフ \(G_{f}\) に \(s\) から \(t\) への有向路 \(P\) が存在するとします。このような路 \(P\) を増加路 (augumenting path) と呼びます。\(P\) に流せる最大のフローを \(\displaystyle F = \min_{u \rightarrow v \in P} c_{f} (u \rightarrow v)\) とし、(元のグラフにおける) 新しいフロー \(f^{\prime}: E \rightarrow \mathbb{R}\) を次のように定義します: \[ f^{\prime}(u \rightarrow v) = \begin{cases} f(u \rightarrow v) + F & \text{if } u \rightarrow v \in P \\ f(u \rightarrow v) - F & \text{if } v \rightarrow u \in P \\ f(u \rightarrow v) & \text{それ以外} \end{cases} \]

この新しいフロー \(f^{\prime}\) が元の容量 \(c\) に対して実現可能であること、つまり全ての辺に対して \(f^{\prime} \geq 0\) かつ \(f^{\prime} \leq c\) であることをこれから示します。元のグラフ \(G\) における辺 \(u \rightarrow v\) に対する三つのケースを考えます:

• \(P\) が \(u \rightarrow v\) を含むならば、\(f\) が実現可能なことより \[ f^{\prime} (u \rightarrow v) = f(u \rightarrow v) + F > f(u \rightarrow v) \geq 0 \] であり、また \[ \begin{aligned} f^{\prime} (u \rightarrow v) & = f(u \rightarrow v) + F && [f^{\prime} \text{ の定義}] \\ & \leq f(u \rightarrow v) + c_{f}(u \rightarrow v) && [F \text{ の定義}] \\ & = f(u \rightarrow v) + c(u \rightarrow v) - f(u \rightarrow v) && [c_{f} \text{ の定義}] \\ & = c(u \rightarrow v) && [\text{やったぜ}] \end{aligned} \] も成り立つ。

• \(P\) が \(u \rightarrow v\) の逆 \(v \rightarrow u\) を含むならば、ここでも \(f\) が実現可能なことから \[ f^{\prime} (u \rightarrow v) = f(u \rightarrow v) - F < f(u \rightarrow v) \leq c(u \rightarrow v) \] であり、また \[ \begin{aligned} f^{\prime}(u \rightarrow v) & = f(u \rightarrow v) - F && [f^{\prime} \text{ の定義}] \\ & \geq f(u \rightarrow v) - c_{f}(v \rightarrow u) && [F \text{ の定義}] \\ & = f(u \rightarrow v) - f(u \rightarrow v) && [c_{f} \text{ の定義}] \\ & = 0 && [\text{やったぜ}] \end{aligned} \] も成り立つ。

• 最後に \(u \rightarrow v\) も \(v \rightarrow u\) も増加路に含まれないなら \(f^{\prime}(u \rightarrow v) = f(u \rightarrow v)\) だから、 \(f\) が実現可能なことより \(0 \leq f^{\prime}(u \rightarrow v) \leq c(u \rightarrow v)\) が成り立つ。

よって \(f^{\prime}\) は実現可能です。

最後に、増加路で \(s\) から離れる辺は最初の辺だけなので \(|f^{\prime}| = |f| + F > |f|\) であり、したがって \(f^{\prime}\) は \(f\) よりも大きな値を持つ実現可能なフローです。以上より、残余グラフ \(G_{f}\) に \(s\) から \(t\) への路が存在するならば \(f\) は最大フローではないと言えます。

一方で残余グラフ \(G_{f}\) に \(s\) から \(t\) への有向路が含まれないとします。このとき \(G_{f}\) で \(s\) から到達可能な頂点の集合を \(S\) とし、さらに \(T = V \backslash S\) と定めると、分割 \((S, T)\) は明らかに \((s,t)\)-カットとなります。さらに任意の \(u \in S\) と \(v \in T\) について \(c_{f}(u \rightarrow v) = 0\) なことから \[ \begin{cases} c(u \rightarrow v) - f (u \rightarrow v) = 0 & \text{if } u \rightarrow v \in E \\ f(v \rightarrow u) = 0 & \text{if } v \rightarrow u \in E \end{cases} \] が成り立ちます。これを言い換えると、考えているフロー \(f\) は \(S\) から \(T\) へ向かう辺を全て飽和させ、\(T\) から \(S\) に向かう辺を全て避けるということです。よって 命題 10.1 より \(|f| = \|S,T\|\) であり、 \(f\) が最大フローで \((S, T)\) が最小カットであることが分かります。

証明はこれで完了です！ \(\Box\)

Ford と Fulkerson の増加路アルゴリズム

Ford と Fulkerson が示した最大フロー最小カット定理の証明から、最大フローを計算するアルゴリズムが直ちに手に入ります: 空のフローから始め、残余グラフにおける \(s\) から \(t\) への任意の増加路を使ってフローを増加させる処理を増加路が無くなるまで繰り返すというものです。

このアルゴリズムについての次の系は簡単に示せますが、重要です:

実際の最大フローを \(f^{\ast}\) とすると、辺の容量が整数のネットワークに対する Ford-Fulkerson のアルゴリズムは大きく見積もっても最大 \(|f^{\ast}|\) 回の反復の後に停止します。各反復においてこのアルゴリズムは増加路を見つけるための何か優先探索と残余グラフ \(G_{f}\) の構築を \(O(E)\) 時間で行うので、この設定における最悪実行時間は \(\pmb{O(E|f^{\ast}|)}\) です。

Jack Edmonds と Richard Karp はこの実行時間解析が本質的に厳密であることを証明しました。次の図にある四つの頂点を持つネットワークを考えます。ここで \(X\) はとても大きい整数を表します。このネットワークにおける最大フローの値は明らかに \(2X\) です。しかし Ford-Fulkerson のアルゴリズムは増加路 \(s \rightarrow u \rightarrow v \rightarrow t\) を使って \(1\) だけフローを増加させ、その後増加路 \(s \rightarrow v \rightarrow u \rightarrow t\) を使って \(1\) だけフローを増加させるという処理を繰り返すかもしれません。この場合実行時間は \(\Theta(X) = \Omega(|f^{\ast}|)\) となります。

現実のデータから作られるグラフの多く、あるいは \(|f^{\ast}|\) が小さいという条件においては、Ford-Fulkerson のアルゴリズムはとても高速に動作します。しかし増加路に制限を設けなければ、最悪計算時間が効率的だとは言えません。Edmonds と Karp が示した上記のネットワークは \(O(\log X)\) ビットで表現できるので、Ford-Fulkerson の実行時間は実は入力サイズに対して指数的だからです。

無理数の容量

では容量が整数でなかったら？ 容量に (正の) 定数をかければ最大フローは同じだけ大きくなるので、辺の重みが有理数の場合には Ford-Fulkerson のアルゴリズムを使って最大フローを求められます。ただしこの場合でも計算時間は (入力を表現するためのビット長に対して) 指数的です。

一方で無理数の容量がある場合、アルゴリズムがどんどん小さくなる増加路を選び続けて停止しないことがあります。さらに悪いことに、この増加していくフローの無限列が最大フローに収束しない、さらには最大フローからかけ離れた値に収束することがあります！ この悪い振る舞いをするネットワークの最小の例は 1993 年に Uri Zwick (ユリ・ツウィック) によって発見されました³:

このネットワークに含まれる 9 個の辺のうち 6 個にはとても大きい整数の重み \(X\) が付いており、2 個には重み \(1\) が、1 個には重み \(\phi = (\sqrt{5} - 1) / 2 \approx 0.618034\) が付いています。\(\phi\) は \(1 - \phi = \phi^{2}\) を満たすように選ばれています。Ford-Fulkerson のアルゴリズムがスタックすることを示すために、アルゴリズムが進行するにつれて三つの水平な辺の残余容量がどのように変化するかに注目します (他の 6 つの辺の残余容量は常に \(X - 1\) 以上です)。

Ford-Fulkerson のアルゴリズムが最初に上図の上部にある増加路を選んだとします。このとき三つの水平な辺の残余容量は左から順に 1, 0, \(\phi\) となります。ある整数 \(k\) に対して三つの水平な辺の残余容量が \(\phi^{k-1}\), \(0\), \(\phi^{k}\) であると帰納的に仮定すると、このとき

1. 増加路 \(B\) に沿ってフローを \(\phi^{k}\) だけ増加させると、残余容量は \(\phi^{k+1}\), \(\phi^{k}\), \(0\) となる。

2. 続いて増加路 \(C\) に沿ってフローを \(\phi^{k}\) だけ増加させると、残余容量は \(\phi^{k+1}\), \(0\), \(\phi^{k}\) となる。

3. 続いて増加路 \(B\) に沿ってフローを \(\phi^{k+1}\) だけ増加させると、残余容量は \(0\), \(\phi^{k+1}\), \(\phi^{k+2}\) となる。

4. 続いて増加路 \(A\) に沿ってフローを \(\phi^{k+1}\) だけ増加させると、残余容量は \(\phi^{k+1}\), \(0\), \(\phi^{k+2}\) となる。

が成り立ちます。よって帰納法により、\(4n + 1\) 回の増加ステップの後には残余容量が \(\phi^{2n-2}\), \(0\), \(\phi^{2n-1}\) となることが分かります。増加の回数を無限大にすると、フローの値は \[ 1 + 2 \sum_{i=1}^{\infty} \phi^{i} = 1 + \frac{2}{1 - \phi} = 4 + \sqrt{5} < 7 \] に収束します。しかし最大フローの値は明らかに \(2X + 1 \gg 7\) です。

実際の実装を考える読者は、なぜそもそも無理数の容量なんてものを考えるのかと不思議に思うかもしれません。コンピューターが正確に表現できるのは (小さな) 整数と (小さい、二進の) 分数だけなのにどうして、と。いい質問です！ この質問に対する数学者の答えは「容量の整数への制限は文字通り人工的だから」です。容量が整数にしかならないというのはコンピューターのハードウェア (あるいはハードウェアに関連する物理法則) が作り出した人為的な制限であって、抽象的な計算問題が持つ本質的な特徴ではありません。より実際的な理由としては、無理数の入力に対するアルゴリズムの振る舞いを見ることで、浮動小数点数を含んだ入力に対する最悪ケースにおける振る舞いが分かるからというのがあります ――つまり、ひどいのです。常識的な容量を持つインスタンスであっても、よく考えずに Ford-Fulkerson のアルゴリズムを実装すると、浮動小数の切り捨て誤差だけが原因で無限ループに入ってしかも正しい答えに近づかないことがあります。

フローの合成と分解

フローの定義は頂点における保存条件が満たされるグラフの辺を入力とする関数であるのが普通ですが、他の定式化もあります。この定式化の方がより自然で有用なこともあります。

任意のグラフ \(G\) とソース頂点 \(s\) とシンク頂点 \(t\) が与えられたとして、\(G\) の適当な \((s,t)\)-フロー \(f, g\) と実数 \(\alpha, \beta\) を取り、次の関数 \(h: E \rightarrow \mathbb{R}\) を考えます: \[ h(u \rightarrow v) := \alpha \cdot f(u \rightarrow v) + \beta \cdot g(u \rightarrow v) \] ここで \(u \rightarrow v\) は任意の辺です。この定義は単純に \(h = \alpha f + \beta g\) とも書けます。定義を追っていくと、\(h\) もまた \((s,t)\)-フローでありその値は \(|h| = \alpha |f| + \beta |g|\) であることが分かります。これをより一般的に言うと、\((s,t)\)-フローの線形結合は \((s,t)\)-フローだということです。

よって任意の \((s,t)\)-フローは特殊な構造を持つフローの重み付き和として表現できます。\(s\) から \(t\) への任意の有向路 \(P\) について、対応する路フロー (path flow) を次のように定義します: \[ P(u \rightarrow v) = \begin{cases} 1 & \text{if } u \rightarrow v \in P \\ -1 & \text{if } v \rightarrow u \in P \\ 0 & \text{それ以外} \end{cases} \] 定義を追っていくと \(P: E \rightarrow \mathbb{R}\) は値が \(1\) の \((s, t)\) フローであることが簡単に示せます。ここでは路に流す一単位のフローとその路の両方を意図的に同じ記号 \(P\) で表しています。

同様に、任意の閉路 \(C\) に対応する閉路フロー (cycle flow) を次のように定義します: \[ C(u \rightarrow v) = \begin{cases} 1 & \text{if } u \rightarrow v \in C \\ -1 & \text{if } v \rightarrow u \in C \\ 0 & \text{それ以外} \end{cases} \] ここでも \(C: E \rightarrow \mathbb{R}\) が値の \(0\) の \((s, t)\) フローであることは簡単に示せます。

前述の議論から任意の路フローと閉路フローの線形結合もまたフローとなることが証明でき、この線形和をフロー分解 (flow decomposition) と呼びます。さらに、任意の非負フローには次の構造を持つフロー分解が存在します:

証明 \(f\) に含まれるゼロでないフローを持つ辺の数に関する帰納法で示す。直感的に言うと、Ford-Fulkerson のアルゴリズムを逆回しにしたのがこの証明である。

\(f\) において少なくとも一つの辺が正のフローを持っているならば、その辺を通る \((s,t)\)-路あるいは負閉路が存在する。よってその路または閉路を \(f\) から引けるだけ引くことで少なくとも一つの辺を \(f\) から消すことができる。こうするとゼロでないフローを持つ辺の数が減るので、あとは再帰の妖精が残りの分解をしてくれる。

この議論をきちんと行うために、 \(f\) が循環 (circulation) である特殊ケースを考える。フローが循環であるとは、値が \(0\) で \(s,t\) を含む全ての頂点において保存条件が成り立つことを言う。任意のフローネットワークとそれに含まれる循環 \(f\) を固定し、\(f(u \rightarrow v) > 0\) を満たす辺 \(u \rightarrow v\) の数を \(\#f\) とする。\(f\) が最大でも \(\max \lbrace 0, \# f - 1 \rbrace\) 個の閉路の正の線形結合に分解できることを、これから \(\# f\) に関する帰納法で示す。考えるべきケースは三つある:

• \(\# f = 0\) の場合、\(f\) はゼロ個の閉路の線形結合である。

• \(f (u \rightarrow v) > 0\) である辺 \(u \rightarrow v\) 全体が有向閉路を作る場合、\(f\) は一つの閉路の線形結合として表せる。

• そうでない場合、\(f(u \rightarrow v) > 0\) である辺 \(u \rightarrow v\) について、任意の歩道 \(u = v_{0} \rightarrow\) \(v = v_{1} \rightarrow\) \(v_{2} \rightarrow \cdots \) であって全ての添え字 \(i\) について \(f(v_{i-1} \rightarrow v_{i} ) > 0\) であるものを考える。フローの保存条件から全ての頂点に出るフローと入るフローがあるので、この歩道は任意に長くできる。そうした場合二回以上訪れる頂点が存在するので、そのような頂点で一番添え字が若いものを \(v_{j} = v_{k}\) \((j < k)\) とする。このとき \(v_{j} \rightarrow v_{j-1} \rightarrow \cdots \rightarrow v_{k}\) は単純閉路 \(C\) となる。

  \(\displaystyle F := \min_{e \in C} f(e)\) とし、新しい関数 \(f^{\prime}\) を \(f^{\prime} := f - F \cdot C\)、省略せずに書くと \[ f^{\prime}(u \rightarrow v) := \begin{cases} f(u \rightarrow v) - F & \text{if } u \rightarrow v \in C \\ f(u \rightarrow v) & \text{それ以外} \end{cases} \] と定義する。定義を追っていくと \(f^{\prime}\) は値が \(0\) で実現可能な \(G\) の循環であることが分かる。\(F\) の定義よりある \(e \in C\) において \(f(e) = F\) となるので、その \(e\) に対して \(f^{\prime}(e) = 0\) であり、したがって \(\# f^{\prime} \leq \# f - 1\) である。\(f^{\prime}\) は \(f\) より少ない辺しか持たないことから、帰納法の仮定より \(f^{\prime}\) には \(\# f^{\prime} - 1 \leq \# f - 2\) 個以下の閉路を使った分解が存在する。よってこの分解に \(C\) に沿って \(F\) だけフローを流したフローを追加すれば、\(\# f - 1\) 個の路または閉路を使った \(f\) の分解が手に入る。このことを簡潔に書けば \(f = f^{\prime} + F \cdot C\) である。

以上より \(f\) が最大でも \(\max \lbrace 0, \# f - 1 \rbrace\) 個の閉路の正の線形結合に分解できることが示せた。

\(f\) を任意のフローネットワークに対する \(|f| > 0\) を満たす任意の \((s,t)\)-フローとする。ネットワークに \(t \rightarrow s\) という辺を追加し、新しい循環 \(f^{\prime}\) を \(f^{\prime} (t \rightarrow s) = |f|\) およびそれ以外の辺に対しては \(f^{\prime} (u \rightarrow v) = f(u \rightarrow v)\) として定義する。ここで \(\# f^{\prime} = \# f + 1 \geq 2\) である。前述の議論より \(f^{\prime}\) は最大でも \(\#f^{\prime} - 1\) 個の有向閉路の正の線形結合に分解できる。この分解から辺 \(t \rightarrow s\) を取り除いたときに得られるのはフロー \(f\) に対する分解であり、最大でも \(\# f^{\prime} - 1 \leq \# f\) 個の \((s,t)\)-路および閉路しか持たない。具体的には、\(f^{\prime}\) における \(s \rightarrow t\) を含む閉路は \(f\) における \((s,t)\)-路となり、\(f^{\prime}\) における \(s \rightarrow t\) 閉路を含まない閉路は \(f\) においても閉路のままとなる。 \(\Box\)

フロー分解定理の証明から、次の特殊な場合に対する強い結果が得られます:

• 任意の循環は閉路の重み付き和に分解できる。路は必要ない。
• 任意の非巡回 \((s,t)\)-フローは \((s,t)\)-路の重み付き和に分解できる。閉路は必要ない。

さらに、任意のフローから閉路を削除すると同じ値を持つ非巡回フローが手に入ることも分かります。つまり全てのフローネットワークには最大非巡回 \((s,t)\)-フローが存在します。

この証明は \((s,t)\)-フローを路と閉路に分解するアルゴリズムとしても読むことができます。つまり \((s,t)\)-路または有向閉路を現在のフローから見つけてそれをできる限り取り除くという処理をフローが空になるまで繰り返すアルゴリズムであり、 Ford-Fulkerson のアルゴリズムに似ています。次のようにすれば路フローまたは閉路フローを \(O(V)\) 時間で見つけられます:

• \(s\) から出る辺に正のフローを持つものがあるなら、\(s\) から始めて \(t\) に到達する (路フローが手に入る) か同じ頂点に二度到達する (閉路フローが手に入る) まで任意の辺をたどる。

• \(s\) から出る辺に正のフローを持つものが無いなら、正のフローを持つ辺の始点となっている頂点 \(v\) を見つけて \(v\) から始めて同じ頂点に二度到達する (閉路フローが手に入る) まで任意の辺をたどる。

両方の場合においてアルゴリズムがスタックしないことは保存条件から分かります。各反復は \(O(V)\) 時間で行うことができ、フローを引くという処理で少なくとも一つの辺がフローから消えるので、フロー分解アルゴリズム全体の実行時間は \(\pmb{O(VE)}\) です。

フロー分解定理を使うと、路または閉路を一つずつ作る処理を反復する任意の最大フローアルゴリズムの実行時間の下界が分かります。全てのフローは最大でも \(E\) 個の路と閉路に分解でき、それぞれの路と閉路は最大でも \(V\) 個の辺を持つことから、フロー分解全体の複雑性は \(O(VE)\) です。さらに任意のフロー分解が \(\Theta(VE)\) の複雑性を持つフローは簡単に構築できるので、各反復ごとに一つの路または閉路を実際に構築する最大フローアルゴリズム ――具体的には、Ford と Fulkerson の増加路アルゴリズムの全ての実装―― は最悪ケースにおける実行時間が \(\Theta(VE)\) となります。

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\) の非減少性です。

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

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

さらなる進展

最大フローアルゴリズムの物語はこれで終わりでは決してありません。何十年にも渡る高速なアルゴリズムの研究の成果を次の表にまとめます⁵。ここにあるアルゴリズムは全て反復によって最大フローを計算するものであり、ほとんどのアルゴリズムには二つのバージョンがあります: 一つは各反復で総当たりを使う単純なバージョンで、もう一つは洗練されたデータ構造を使ってフローネットワークの全域木を管理することで反復と全域木の更新を対数時間で行うバージョンです。これまでに知られている最速のアルゴリズムが最適であると思ってはいけません。最大フローは現在でも活発に研究が行われている領域です。

現在知られている (purely combinatorial な) 最速の最大フローアルゴリズムは、2012 年に James Orlin (ジェームス・オーリン) によって発表されたものです。実行時間は \(\pmb{O(VE)}\) であり、フロー分解の最悪計算時間と同じです。このアルゴリズムはそれまでに発見されたアルゴリズムやデータ構造をブラックボックスとして使っており、それらのほとんどがとても複雑なので、Orlin のアルゴリズムの詳細はこの本の範囲を大きく超えます。また Orlin のアルゴリズムを拡張すると、具体的なフロー分解を構築しないアルゴリズムが得られます。実際このアルゴリズムは \(O(V)\) 個しか辺を持たないグラフに対しては実行時間が \(O(V^{2} / \log V)\) となります！

しかしもちろん、最大フローアルゴリズムを使うアルゴリズムの解析においては、この実行時間の上界を使って構いません。次の文章をチートシートに書いておいて宿題で使いましょう:

最後に、全ての辺の容量が \(1\) であるような "単位容量" ネットワークに対するさらに高速な最大フローアルゴリズムを紹介します。1973 年、Alexander Karzanov (アレキサンダー・カルザノフ) は Dinitz (ディニッツ) の blocking-flow アルゴリズム ――上の表で一番上にあるもの―― が単位容量という条件の下では \(O(\min \lbrace V^{2 / 3}, E^{1 / 2} \rbrace E)\) 時間で実行されることを示しました (この実行時間はフロー分解に \(\Omega(VE)\) 時間かかるという事実と矛盾するように見えますが、Karzanov の解析からは単位容量のネットワークは \(O(\min \lbrace V^{2 / 3}, E^{1 / 2} \rbrace E)\) 時間で路に分解できることが分かります)。このアルゴリズムは 40 年以上にわたって単位容量のネットワークに対する最速の最大フローアルゴリズムでしたが、この記録は 2014 年 に Aleksander Mądry (アレクサンダー・モドリー) よって破られました。Mądry が示した真に驚くべきアルゴリズムの実行時間は \(O(E^{10/7} \text{polylog } E)\) です。ここでも Mądry のアルゴリズムの詳細はこの本の範囲を大きく超え、正直なところ著者の技量も追いついていません。

練習問題

1. 私はこの話を Alexander Schrijver (アレキサンダー・シュライバー) による素晴らしいサーベイ "On the history of combinatorial optimization (till 1960)" で知りました。Harris-Ross レポートの機密指定は Schrijver による請求があって初めて解かれました。これからすぐに言及することになる Ford と Fulkerson は最大フロー最小カット問題を定式化した人物として Harris をあげていますが、本当に正確な歴史はよく分からない部分があります。というのも、Harris と Ross は "問題の定式化において助力を受けた" として George Danzig をあげているのです。^[return]

2. T[homas] E. Harris and F[rank] S. Ross. Fundamentals of a method for evaluating rail net capacities. The RAND Corporation, Research Memorandum RM-1517, October 24, 1955. 米政府の著作によりパブリックドメイン (http://www.dtic.mil/dtic/tr/fulltext/u2/093458.pdf)^[return]

3. Ford と Fulkerson も 1962 年に同じ悪い振る舞いをするネットワークを示しています。彼らのネットワークは 10 個の頂点と 48 個の辺からなります。^[return]

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

5. 表を小さくまとめるために、実行時間が辺の容量や最大フローの値に依存しているアルゴリズムは意図的に除外しました。この制限を考えたとしても、この表は全く不完全です！^[return]

6. もし just (...だけ) という副詞を使ったなら、あなたは無意識のうちに「私が詳細を詰める気にならないのでこれはまず間違いなく間違っているのだが、まぁとにかく私を信じてくれ」という言葉、あるいは「これはたぶん間違っている」という言葉を省略したと思うべきです。次の言葉にも注意: merely (ただ...)、simply (単純に...)、clearly (明らかに...)、obviously (自明に...)^[return]