ディニッツ法

ディニッツ法（ディニッツほう、英: Dinic's algorithm, Dinitz's algorithm）とは、1970年にイスラエル（元はソ連）のコンピュータ科学者のイェフィム・ディニッツ（英語版）により提案されたネットワークフローにおける最大流問題に対する強多項式時間（英語版）アルゴリズムである^[1]。ディニッツ法は計算量 $O(|V|^{2}|E|)$ で動作し、同じく最短増加路を求め計算量 $O(|V||E|^{2})$ で動作するエドモンズ・カープ法に類似している。ディニッツ法はレベルグラフとブロッキングフロー^{[注釈 1]}という概念を導入することで上記の計算量を達成している。

歴史

ディニッツは1969年1月ゲオルギー・アデルソン・ヴェルスキー（英語版）の修士課程の生徒としてディニッツ法を編み出した。数十年後、当時のことを以下のように語った^[2]:

アデルソン・ヴェルスキーのアルゴリズムの講義では毎回次週の講義内容に関する問題の課題を出していた。ディニッツ法はこの課題の回答として出来上がったものである。当時（ディニッツ自身は）既に解法として知られていたフォード・ファルカーソン法について知らなかった…。
⋮
無知なことは時に役立つことがある。もし（フォード・ファルカーソン法での）飽和した辺に対する手続きを既に知っていたとしたら、ディニッツ法は生み出されていないだろう。

1970年にディニッツは Doklady Akademii Nauk SSSR に論文を寄稿した。1974年には（ディニッツの博士課程指導学生の）サイモン・イーブン（英語版）およびテクニオン・イスラエル工科大学のアーロン・イタイはディニッツ法やアレキサンダー・カルザノフ（英語版）が考案したブロッキングフローに関する概念に強く興味を抱いた。しかしながら、これらの論文は掲載誌の Doklady Akademii Nauk SSSR に規定されているページ数の制限（4頁）により、論文の内容を理解するのに難儀した。論文の解読を続けたことで、結果として層別ネットワークに対する手続きを除いた論文の内容を三日間で理解することができた。両者は著者の名前を間違えながらも、数年かけてディニッツ法に関する講義を行って世間に知らしめていった。イーブンとイタイは層別ネットワークの代わりに幅優先探索と深さ優先探索を組み合わせたディニッツ法を普及したため、現在ではこの方法によるディニッツ法が一般的に知られている^[2]。

フォード・ファルカーソン法が提案されてから約10年間は無理数の辺容量を持つような一般のネットワークに対する強多項式時間アルゴリズムの存在性は示されていなかった。そのため最大流問題が強多項式時間で解けるかは不明であった。ディニッツ法と（1972年発表の）エドモンズ・カープ法はフォードファルカーソン法において各反復で求まる増加路が最短路であるならば、増加路の長さが単調増加するため、有限の反復回数で必ず終了することをそれぞれ独立して証明した。

定義

ネットワーク $G=((V,E),c,f,s,t)$ において辺容量を $c(u,v)$ 、フローを $f(u,v)$ とする。このとき、

残余容量

c_{f}\colon V\times V\to R^{+}

は以下のように定義される:

もし、 $(u,v)\in E$ ならば、
$c_{f}(u,v)=c(u,v)-f(u,v)$
もし、 $(v,u)\in E$ ならば、
$c_{f}(u,v)=f(v,u)$
そうでなければ、 $c_{f}(u,v)=0$

残余ネットワークは重みなしのネットワーク

G_{f}=((V,E_{f}),c_{f}|_{E_{f}},s,t)

と定義される。ただし、

E_{f}=\{(u,v)\in V\times V\colon \;c_{f}(u,v)>0\}

.

増加路は残余ネットワーク

G_{f}

における路

s

–

t

である。

\operatorname {dist} (v)

は

G_{f}

において始点

s

から頂点

v

への最短路の値を表す。このとき

G_{f}

におけるレベルグラフは

G_{L}=((V,E_{L}),c_{f}|_{E_{L}},s,t)

と定義される。ただし、

E_{L}=\{(u,v)\in E_{f}\colon \;\operatorname {dist} (v)=\operatorname {dist} (u)+1\}

である。

ブロッキングフローは

s

から

t

へのフロー

f'

を表し、

G'=((V,E_{L}'),s,t)

で定義される。ただし、

E_{L}'=\{(u,v)\colon \;f'(u,v)<c_{f}|_{E_{L}}(u,v)\}

であり、

s

から

t

への路は含まれない^{[注釈 2]}^[3]。

アルゴリズム

ディニッツ法

入力: ネットワーク

G=((V,E),c,s,t)

出力:

s

から

t

へのフロー

f

の最大値

各辺 $e\in E$ のフローを $f(e)=0$ とおく。
$G$ における $G_{f}$ から $G_{L}$ を構築する。もし、 $\operatorname {dist} (t)=\infty$ が存在するならば、アルゴリズムは停止し、 $f$ を出力する。
$G_{L}$ におけるブロッキングフロー $f'$ を求める。
$f'$ から増加路 $f$ を求め、ステップ2へ戻る。

分析

反復ごとにブロッキングフローの層の数は少なくとも1ずつ増えることから、ブロッキングフローは最大でも $|V|-1$ の層の数となる。また以下のことが言える:

レベルグラフ $G_{L}$ は幅優先探索によって計算量 $O(E)$ で求まる。
レベルグラフ $G_{L}$ におけるブロッキングフローは計算量 $O(VE)$ で求まる^{[注釈 3]}。

このことから一回の反復にかかる計算量は $O(E+VE)=O(VE)$ となる。結果として、全体の計算量は $O(V^{2}E)$ となる^[2]。

動的木（英語版）と呼ばれるデータ構造を用いると、各反復におけるブロッキングフローは計算量 $O(E\log V)$ まで減少させることができるため、ディニッツ法の計算量は $O(VE\log V)$ まで改良することができる。

特別なケース

単位容量を持つネットワークにおいては強多項式時間が保たれる。ブロッキングフローは計算量 $O(E)$ で求めることができ、反復も $O({\sqrt {E}})$ もしくは $O(V^{2/3})$ を超えない範囲で終了することが保証されている^{[注釈 4]}。すなわちディニッツ法は計算量 $O(\min\{V^{2/3},E^{1/2}\}E)$ で動作する^[5]。

最大二部マッチング問題に対するネットワークにおいては、反復の上界が $O({\sqrt {V}})$ となることが知られており、計算量は $O({\sqrt {V}}E)$ で動作する。このことはホップクロフト・カープ法（英語版）として知られている。一般的に言えば、ネットワークにおいてシンクおよびソースを除く各頂点を結ぶ辺がすべて容量1の入る辺もしくは容量1の出る辺であり、他の辺の容量がすべて整数値をとる単位ネットワーク上で成り立つ^[3]。

具体例

ディニッツ法を以下で説明する。レベルグラフ $G_{L}$ において頂点の赤色の数値は $\operatorname {dist} (v)$ を表す。また青色の辺からブロッキングフローが求まる。

	$G$	$G_{f}$	$G_{L}$
1.
	ブロッキングフローは以下の路から構成される: フロー4を持つ路: $\{s,1,3,t\}$ フロー6を持つ路: $\{s,1,4,t\}$ フロー4を持つ路: $\{s,2,4,t\}$ それゆえ、ブロッキングフローは 14 となり、フロー $\|f\|$ は $14$ となる。増加路は3つの辺から構成されることに注意する。
2.
	ブロッキングフローは以下の路から構成される: フロー5を持つ路: $\{s,2,4,3,t\}$ それゆえ、ブロッキングフローは 5 となり、フロー $\|f\|$ は $14+5=19$ となる。増加路は4つの辺から構成されることに注意する。
3.
	$G_{f}$ において $t$ に到達することはできないことから、アルゴリズムは終了してフローの最大値19を返す。各反復ごとに増加路となる辺の数は一つ前の反復より少なくとも一つ増加することに注意する。

脚注

[脚注の使い方]

注釈

^ 英: level graph, blocking flow
^ このことは $E_{L}'=\{(u,v)\colon \;f'(u,v)<c_{f}|_{E_{L}}(u,v)\}$ を満たす飽和した辺が取り除かれた部分グラフにおいては $s$ から $t$ への路は存在しないことを意味する。言い換えると、ブロッキングフローには $s$ から $t$ への路の中に少なくとも一つ飽和した辺が含まれている。
^ ブロッキングフローは Advance および Retreat 操作により計算量 $O(E)$ で求めることができる^[4]。
^ 計算量 $O(V^{2/3})$ は、2頂点において同じ向きの多重辺が含まれていないときに成り立ち、計算量 $O({\sqrt {E}})$ についてはこのような仮定無しに保証される。

出典

^ E. A. Dinic (1970). “Algorithm for solution of a problem of maximum flow in a network with power estimation”. Doklady Akademii Nauk SSSR 11: 1277–1280.
^ ^a ^b ^c Dinitz, Yefim (2006). “Dinitz' Algorithm: The Original Version and Even's Version”. In Oded Goldreich; Arnold L. Rosenberg; Alan L. Selman. Theoretical Computer Science: Essays in Memory of Shimon Even. Lecture Notes in Computer Science. 3895. Springer. pp. 218–240. doi:10.1007/11685654_10. ISBN 978-3-540-32880-3
^ ^a ^b Tarjan 1983, p. 102.
^ Salman Abolfathe, Jaime Quinonez (2006年). “Blocking flow”. 4 Advanced Algorithm. 2024年5月22日時点のオリジナルよりアーカイブ。2025年3月3日閲覧。
^ Even, Shimon; Tarjan, R. Endre (1975). “Network Flow and Testing Graph Connectivity”. SIAM Journal on Computing 4 (4): 507–518. doi:10.1137/0204043. ISSN 0097-5397.

参考文献

Dinitz, Yefim (2006). “Dinitz' Algorithm: The Original Version and Even's Version”. In Oded Goldreich; Arnold L. Rosenberg; Alan L. Selman. Theoretical Computer Science: Essays in Memory of Shimon Even. Lecture Notes in Computer Science. 3895. Springer. pp. 218–240. doi:10.1007/11685654_10. ISBN 978-3-540-32880-3
Kadar, Ilan; Albagli, Sivan (18 April 2019). Dinitz's algorithm for finding a maximum flow in a network. Ben-Gurion University. 2023年12月22日時点のオリジナルよりアーカイブ.
Korte, B. H.; Vygen, Jens (2008). “8.4 Blocking Flows and Fujishige's Algorithm”. Combinatorial Optimization: Theory and Algorithms (Algorithms and Combinatorics, 21). Springer Berlin Heidelberg. pp. 174–176. ISBN 978-3-540-71844-4
Tarjan, R. E. (1983). Data structures and network algorithms

歴史

定義

アルゴリズム

分析

特別なケース

具体例

脚注

注釈

出典

参考文献

関連項目