Dinic法について

理解にかなり手間取った&面白かったのでメモ。

アルゴリズム

やっていることは、「長さが短い順に増加路を使っていく」というだけ。
以下、頂点数 V 、辺数 E 、始点 S 、終点 T のネットワークを考える。

残余グラフを構築しておく。
増加路がなくなるまで、以下を繰り返す。この一回の繰り返しを「1ステップ」とする。

  • BFSで、「容量正の辺のみを使った時の、 S から v までの最短路長」 level_v を求める。
  • 長さ level_T の増加路がなくなるまで、DFSで増加路を選び、フローを増やす。 level_v=level_u+1 なる辺 (u,v) 以外はないものとして扱えば、増加路は全て長さ level_T になる。
  • DFSの際には、「その辺を使ったフローがこれ以上流せない」状態になった辺を記録し、以降の探索では無視するようにする。つまり、その辺を使おうとしたが、 T に辿り着けなかった時と、容量が0になった時、辺は死ぬ。

なお、辺が死んでも1回のステップが終わったら復活する。

計算量(一般のグラフの場合)

最短路の長さは O(V) で、1回で level_T は1以上減るので、全体のステップ数は O(V) 回。

BFSは何の工夫もしていないので、計算量は普通に O(E)

問題はDFSの計算量。このDFSは、Ford-Fulkerson法とは違い、同じ頂点/辺を何度も使うのが厄介。
辺が死ぬタイミングに注目する。
ある辺が死ぬのは、

  • T に到達後、戻ってきた時で、この辺の容量が0になる時(この時、寄り道せずに S まで戻っていく)
  • T に到達できず、戻ってきた時(この辺を使うフローはもう流せないので)

である。
つまり、1回DFSの末端まで到達して戻り始めたら、それに対応して1つ以上の辺が死ぬということが分かる。
1度戻り始めてから次に戻り始めるまでの動く回数は、全部 2V 回以下に収まる。戻るのも進むのも連続して高々 V 回しかできないからである。
これで、辺が死んでから次の辺が死ぬまでの動く回数が O(V) 回であることが言えた。
最初に辺が死ぬまでと最後に辺が死んでからの回数も同様に O(V) 回なので、DFSの計算量は O(VE)

これで、Dinic法の計算量が O(EV^2) であることが分かった。

計算量(二部グラフの最大マッチングを求める場合)

二部グラフの最大マッチングは、新たに頂点 ST を追加して、最大フローが最大マッチングと等しくなるように適当に容量1の辺を張り、フローを流すことで求められる。
この際、グラフの形が特殊なことから、Dinic法が更に高速になる。

まず、1ステップの計算量が O(E) であることが言える。
残余グラフの生きている辺の容量が全て1なので、ある増加路を見つけた時点で、増加路上の辺は全て死ぬ。また、増加路を見つけられなかった時も、戻る時に死ぬ(これは一般グラフの場合と同様)。
よって、辺を2度以上通ることがないので、計算量は O(E)

次に、ステップ数が O(\sqrt{V}) 回であることも言える。
今までで \sqrt{V} ステップが行われたとする。このとき、残余グラフの S-T パスの長さ( =level_T )は \sqrt{V} 以上。
元のグラフの現在のフローを F 、最大フローを F' とすると、残余グラフでは F'-F だけフローが流せるはず。
ここで、残余グラフの容量は全て1で、かつ入次数または出次数のいずれかが1である(場合分けをすると分かる)から、残余グラフに流れるフローは ST を除いて頂点を共有しないことが分かる。
つまり、残りのフローで使われる頂点数は (F'-F) \times \sqrt{V} で下から抑えられる。
(F'-F) \times \sqrt{V} \leq V より、 F'-F \leq \sqrt{V} なので、これ以降のステップ数が \sqrt{V} で抑えられた。
よってステップ数は全体で O( \sqrt{V}) 回。

以上を合わせて、この場合の計算量は、 O(E \sqrt{V})であることが分かった。

いかがでしたか?

非自明な計算量解析って面白いですね!