ディニッツ法

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

歴史

ディニッツは1969年1月テンプレート:仮リンクの修士課程の生徒としてディニッツ法を編み出した。数十年後、当時のことを以下のように語った: テンプレート:Blockquote

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

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

定義

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

残余容量 $c_f:V\times V\to R^{+}$ は以下のように定義される:

1. もし、$(u,v)\in E$ ならば、

   $c_f(u,v)=c(u,v)-f(u,v)$

2. もし、$(v,u)\in E$ ならば、

   $c_f(u,v)=f(v,u)$

3. そうでなければ、$c_f(u,v)=0$

残余ネットワークは重みなしのネットワーク $G_f=((V,E_f),c_f{|}_{E_f},s,t)$ と定義される。ただし、

$E_f=\{(u,v)\in V\times V:c_f(u,v)>0\}$.

増加路は残余ネットワーク $G_f$ における路 $s$–$t$ である。

$\mathrm{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:\mathrm{dist}(v)=\mathrm{dist}(u)+1\}$

である。

ブロッキングフローは $s$ から $t$ へのフロー $f^{\prime }$ を表し、$G^{\prime }=((V,{E_L}^{\prime }),s,t)$ で定義される。ただし、${E_L}^{\prime }=\{(u,v):f^{\prime }(u,v)<c_f{|}_{E_L}(u,v)\}$ であり、$s$ から $t$ への路は含まれないテンプレート:Efnテンプレート:Sfn。

アルゴリズム

ディニッツ法

入力: ネットワーク $G=((V,E),c,s,t)$

出力: $s$ から $t$ へのフロー $f$ の最大値

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

分析

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

• レベルグラフ $G_L$ は幅優先探索によって計算量 $O(E)$ で求まる。
• レベルグラフ $G_L$ におけるブロッキングフローは計算量 $O(VE)$ で求まるテンプレート:Efn。

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

テンプレート:仮リンクと呼ばれるデータ構造を用いると、各反復におけるブロッキングフローは計算量 $O(E\log V)$ まで減少させることができるため、ディニッツ法の計算量は $O(VE\log V)$ まで改良することができる。

特別なケース

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

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

具体例

ディニッツ法を以下で説明する。レベルグラフ $G_L$ において頂点の赤色の数値は $\mathrm{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を返す。各反復ごとに増加路となる辺の数は一つ前の反復より少なくとも一つ増加することに注意する。

参考文献

• テンプレート:Cite book
• テンプレート:Cite conference
• テンプレート:Cite book
• テンプレート:Cite book

関連項目

• フォード・ファルカーソン法
• 最大流問題