Dinic法の計算量を真面目に調べた話

この記事でやること
はじめに（茶番）
注意点
Dinic法の概要
実用上の高速化ポイント
- BFSは頂点t に到達した時点で打ち切る
- 実は頂点s からDFSするより頂点t からDFSした方が速い（らしい？）
二部マッチングにおけるDinic法の計算量
おわりに
参考文献

この記事でやること

Dinic法の仕組みの概略解説
一般のグラフに対するDinic法の計算量と、実用上の高速化が期待できる基本的なポイントの考察
二部グラフの最大マッチング問題でのDinic法の計算量の考察

はじめに（茶番）

AtCoder Beginner Contest 285 にて、二部グラフのマッチングに関する問題が出題されました。

atcoder.jp

自力では解法が思いつけなかったので（精進不足）解説を開いてみると、どうやら「2」と書かれた頂点を全て含むようなマッチングが存在するか？という問題に帰着されるらしい。なるほど確かに。

あとは最小流量制限付きのフローが存在するかを判定すればいいので、昔書いたDinic法のライブラリを引っ張り出してきて…グラフを構築して…ソイヤ！！

いやいや待て待て、さすがにちょっと適当過ぎたか…。よく考えてみればここらへんとかこんな感じに書けばいいか…あーここは書き直した方がいいなぁ…。こんな感じか？ダメか…こうか？こうすればいいのか？

というとても悲しい事件が起きたので、Dinic法と大真面目に格闘して知ったこと・考えたことを備忘録として残しておきます。

注意点

計算量解析については参照元が英語なので、私のガバガバ英訳＆補完となっていることをご了承ください。間違っていたらごめんなさい。（どなたか査読して頂けると非常に助かります。）
一応Python3.8.3によるソースコードを掲載しておりますが、かなり汚いです。なので、具体的な実装例を参照したい方は他の方のソースコードを漁ってみることをお勧めします。

Dinic法の概要

全体像としては、下記の記事が非常にわかりやすいです。

Dinic法 - tkw’s diary

概略

Ford-Fulkerson法によると、「残余ネットワーク上で $s-t$ パスを見つけて流す」を繰り返せば最大流が求まるので、「いい感じの順番で $s-t$ パスを見つけて流す」ことでループ回数を抑えたい。
その手順は、
1. 残余ネットワーク上でBFSにより各頂点の $s$ からの（辺の重みを全て1とした場合での）最短距離 $\text{dist}$ を記録する。
2. $\text{cap} \gt 0$ かつ $\text{dist} [ u ] \lt \text{dist} [ v ]$ 」を満たす辺 $(u, v)$ のみを見るDFSで $s-t$ パスを見つけ流せるだけ流すことを、 $s-t$ パスが見つからなくなるまで繰り返す。
3. BFSで $s-t$ パスが見つからなくなるまで1, 2を繰り返す。

という感じです。

また、2のDFSを繰り返すパートでは配列

$\text{search_from}[v] := 頂点v から出る辺について, 探索中の辺の\text{index}$

を管理することで、（BFS基準での同一パート内で）次回以降のDFSで既に探索済みの辺は参照しないようにします。具体的な処理としては、「DFSで戻ってきたとき、かつ頂点 $t$ にまだ到達できていないとき」にインクリメントすればよいです。

実装例

(Python3.8.3)

from collections import deque

class Dinic:

    def __init__(self, n, inf=float("inf")): # n: 頂点数, inf: minの単位元、十分大の整数にした方が速いかも
        self.V = n
        self.inf = inf
        self.G = [[] for _ in range(n)]
        self.dist = []
        self.search_from = []
    
    def add_edge(self, from_, to, cap): # 容量capの辺(from_, to)をグラフに追加
        self.G[from_].append([to, cap, len(self.G[to])])
        self.G[to].append([from_, 0, len(self.G[from_])-1])

    def _bfs(self, s, t):
        self.dist = [-1]*self.V
        self.dist[s] = 0
        dq = deque([s])
        while dq:
            now = dq.pop()
            for edge in self.G[now]:
                next, cap, _ = edge
                if cap > 0 and self.dist[next] < 0:
                    self.dist[next] = self.dist[now]+1
                    if next == t: return True
                    dq.appendleft(next)
        return False

    def _dfs(self, s, t):
        stack = [t]
        goal = False
        flow = self.inf
        while stack:
            now = stack.pop()
            if now >= 0:
                if now == s:
                    goal = True
                    continue
                i = self.search_from[now]
                while i < len(self.G[now]):
                    self.search_from[now] = i
                    pre, _, rev = self.G[now][i]
                    _, cap, _ = self.G[pre][rev]
                    if cap > 0 and self.dist[now] > self.dist[pre] >= 0:
                        stack.append(~now)
                        stack.append(pre)
                        break
                    i += 1
            else:
                now = ~now
                if goal:
                    i = self.search_from[now]
                    pre, _, rev = self.G[now][i]
                    flow = min(flow, self.G[pre][rev][1])
                    continue
                else:
                    i = self.search_from[now]+1
                    while i < len(self.G[now]):
                        self.search_from[now] = i
                        pre, _, rev = self.G[now][i]
                        _, cap, _ = self.G[pre][rev]
                        if cap > 0 and self.dist[now] > self.dist[pre] >= 0:
                            stack.append(~now)
                            stack.append(pre)
                            break
                        i += 1
        if not goal: return 0
        now = t
        while now != s:
            i = self.search_from[now]
            pre, _, rev = self.G[now][i]
            self.G[now][i][1] += flow
            self.G[pre][rev][1] -= flow
            now = pre
        return flow

    def max_flow(self, s, t): # sからtへの最大流を求める
        flow = 0
        while True:
            if not self._bfs(s, t): return flow
            self.search_from = [0]*self.V
            f = self._dfs(s, t)
            while f > 0:
                flow += f
                f = self._dfs(s, t)

使用例↓

Submission #38339906 - AtCoder Beginner Contest 010

計算量評価

一般のグラフでのDinic法の計算量は $O(V^{2}E)$ となることが知られています：

$\because )$
$\text{dist}[t]$ はBFS毎に狭義単調増加する（※証明は後述）ので、1, 2のループは高々 $V-1$ 回しか発生しません。
BFSは1回あたり $O(V+E)$
DFSでは1回あたり、主に下記の2種類の（BFS基準の同一ループ内で）探索されなくなる辺が存在します：
- $s-t$ パスに含まれず、行き止まりに到達する辺
- $s-t$ パス上に含まれる辺のうち、 $\text{cap}$ が最小の辺*1

よって、BFS基準の同一ループ内でのDFSによる計算量は「全ての辺が探索されなくなるまでの計算量」で評価することにします。
- 前者の辺は一度使用すると $\text{search_from}$ により以降は参照されなくなるため、1本あたりの計算量は $O(1)$ とみなせます。*2
- 後者の辺は1本あたりの計算量を $O(\text{dist}[t]) = O(V)$ とみなせます。
辺は $E$ 本なので、合わせて $O(VE)$ となります。
以上より、全体で $O(V^{2}E)$

（※の証明）
- 現在のBFSパートでの残余ネットワークにおいて、その前のBFSパートでの $\text{dist}$ の振る舞いを考えます。
- 現在の残余ネットワークの任意の辺で、が成立します。・・・①
  - $\because )$
  - $\text{dist}[j]-\text{dist}[i] \gt 1$ を満たす辺 $(i, j)$ が存在すると仮定すると、BFSの性質よりその辺は前BFSパートでは存在しない、つまり、その後のDFSパートで逆辺にフローを流したことになります。
  - DFS時のルールにより $\text{dist}[j]+1 = \text{dist}[i]$
  - $\therefore \text{dist}[j] - \text{dist}[i] = -1$ となり、仮定に矛盾 $\square$
- 現在のBFSパートで見つけた $s-t$ パスにおいて、 $\text{dist}[s] = 0$ であることと①より、このパスの長さの下限は $\text{dist}[t]$ とわかります。
- また、このパスの中にはを満たす辺が少なくとも1つ含まれます。
  - $\because )$
  - 含まれない、すなわち任意の辺 $(i, j)$ で $\text{dist}[j] - \text{dist}[i] = 1$ と仮定すると、これは前DFSパートで見つかるはずの増加パスとなり現在のBFSパートに移っていることに矛盾 $\square$
- よって、このパスの長さの下限は $\text{dist}[t]+1$ となります。 $\square$

辺1本あたりの $\text{dist}$ の増分は高々+1、かつ少なくとも1本は増分+0以下で、 $\text{dist}[t]$ まで増やす必要がある

辺1本あたりの $\text{dist}$ の増分は高々+1、かつ少なくとも1本は増分+0以下で、 $\text{dist}[t]$ まで増やす必要がある

実用上の高速化ポイント

（言語仕様などによる）実装上の最適化ではなく、アルゴリズム的に実用上の高速化が期待できるポイントを挙げます。

BFSは頂点t に到達した時点で打ち切る

dijkstra等の最短路問題でもよく言われるやつです。DFSで参照する辺の条件から、頂点 $t$ 以降に訪れる頂点は必ず行き止まりとなります。*3

実は頂点s からDFSするより頂点t からDFSした方が速い（らしい？）

$s$ からのDFSでは「（BFS基準の同一ループ内で）初めから行き止まりの頂点」にも訪れてしまいますが、 $t$ からのDFSの場合はそのような頂点には訪れることがありません。*4元から行き止まりが少ない場合は逆辺を参照する回数が増える分ほんの少し遅くなるかもしれませんが、トータルで見れば概ね実行時間は改善されます。（要検証）

Submission #38178001 - AtCoder Beginner Contest 285

（ $s$ からDFS, TLE）

Submission #38177995 - AtCoder Beginner Contest 285

（ $t$ からDFS, AC [2754ms]）

二部マッチングにおけるDinic法の計算量

二部グラフにおける最大マッチングは、下図のようなグラフを構築することで最大流問題に帰着できます。

このグラフにおいては、Dinic法の計算量が $O( (V+E)\sqrt{V})$ となることが知られています。*5正確には、下記の条件を満たすグラフではこの計算量でDinic法が動作します：

$s, t$ を除くすべての頂点について、流せる流量が高々1。すなわち、「出る辺の $\text{cap}$ の和」と「入る辺の $\text{cap}$ の和」のいずれか一方は高々1。
この条件を満たすグラフは以下の2つの性質を持ちます：
1. 増加パスに流せる流量は明らかに1。*6
2. 増加パスにフローを流しても、残余ネットワークは常に条件を満たす。
  - $\because )$
  - 残余ネットワークが条件を満たすとし、新たに増加パスにフローを流したとします。この流量は1です。
  - パス上の $s, t$ を除く各頂点について、流れた流量1のフローにより、入る辺の $\text{cap}$ 1つが出る辺（逆辺）へと変わり、出る辺の $\text{cap}$ 1つが入る辺（逆辺）へと変わります。
  - このとき、 $\text{cap}$ の収支は変わっていないため、条件を満たしたままとなります。 $\square$
この条件を満たすグラフをunit networkと言うらしい…？*7

以下、計算量の証明：

$\because )$
DFSパートで $s-t$ パスを見つけた際、先述の条件よりパスに含まれる辺のうち少なくとも $\text{dist}[t]/2$ 本の $\text{cap}$ は1なので、それらは全て以降のDFSで探索されなくなります。
言い換えると、DFSパートで見つかる $s-t$ パスの総距離は高々 $2E$ となります。つまり、DFSパート1回あたりの計算量は（行き止まりの分も合わせて） $O(E)$ となります。

$s-t$ パス1本で探索されなくなる辺が $\text{dist}[t]/2$ 本となる例

$s-t$ パス1本で探索されなくなる辺が $\text{dist}[t]/2$ 本となる例

更に、BFSパートは回しか発生しないことが示せます：
- $\because )$
- 初めて $\text{dist}[t]$ が $\sqrt{V}$ 以上となったときのBFSパートを考えます。
- $\text{dist}$ の狭義単調増加性より、それまでにBFSパートは $O(\sqrt{V})$ 回しか発生しません。
- このBFSパートに至るまでに流した流量を $f$ 、最終的に得られる最大フローを $F$ とします。このとき、現在の残余ネットワークにおける最大流問題の解、すなわち追加で流せる流量は $F-f$ となります。
- 更に、先述のグラフの性質から $s-t$ の点素なパスが $F-f$ 本あると言い換えられます。
- これらパスの長さは $\text{dist}[t]$ なので、パスに使用する頂点数に関する不等式 $(F-f)(\text{dist}[t]-1) \le V$ が得られます。
- ここで、 $\text{dist}[t] \ge \sqrt{V}$ より $F-f = O(\sqrt{V})$
- ゆえに、BFSパート1回につき少なくともフローを1は流せることからこれ以降のBFSパートは $O(\sqrt{V})$ 回しか発生ないとわかります。
- 以上を合わせると、BFSパートは $O(\sqrt{V})$ 回しか発生しません。 $\square$
以上より、全体で $O( (V+E)\sqrt{V})$ 。 $\square$