问题求解（三） Open Topic 11 笔记

Posted on In ,

OT：除福特-法尔克森算法外，最大流问题还有很多其它算法，例如 Edmonds-Karp 算法、Dinitz 算法、Push-Relabel 算法等，请调研至少2种算法（其中至多1种来自上述例子），结合例子介绍算法的设计与分析，与福特-法尔克森算法比较异同并分析优劣。

slide

任意图上 \(O(nm)\) 的网络最大流算法

引言

[1] (Orlin, 2013) 给出了一种在任意图上 \(O(nm)\) 的网络最大流算法。

前置结果和本文贡献

[1] 中的若干证明用到了一些前置结果：

  • [2] (King et al., 1994) 给出了强多项式 \(O(nm\log_{m/(n\log n)})\) 的算法。对于任意 \(m=\Omega(n^{1+\epsilon})\)，该算法都是 \(O(nm)\) 的。
  • [3] (Goldberg & Rao, 1998) 给出了弱多项式的算法，每轮将 \(\Delta\) bounded 的最大流问题转化为 \(\Delta/2\) bounded 的最大流问题，每轮时间为 \(O(\min\lbrace n^{2/3}, m^{1/2}\rbrace\cdot m\log (n^2/m))\)。

可以发现，需要攻克的仅在于 \(m\) 不超过多项式地渐进大于 \(n\) 时。

本文提出 \(O(nm+m^{31/16}\log^2n)\) 的算法。当 \(m=O(n^{(16/15)-\epsilon})\) 时，该结果是 \(O(nm)\) 的。

和上文第一个结果相结合，得到了对任意图 \(O(nm)\) 的网络最大流算法。

主要思路

主要利用某种方法套用了 Goldberg 的结果：若最大流为 \(U\)，则时间为 \[ T(n)=\tilde O(\min\lbrace n^{2/3}, m^{1/2}\rbrace\cdot m\log U). \]

  • 若 \(\log U\le m^{7/16}\)，则有

\[ T(n)=\tilde O(m^{1/2}\cdot m\cdot m^{7/16})=\tilde O(m^{31/16}), \]

已然满足条件。

  • 若 \(\log U\le m^{7/16}\)，则在每轮前，把原图压缩成 \(C\) 顶点、\(O(C^2)\) 边的图。平均 \(C=O(m/\log U)\)，则单轮中 \(n'=C, m'=O(C^2)\)，带入有单轮时间为

\[ \tilde O(C^{2/3}\cdot C^2)=\tilde O(C^{8/3}). \]

于是 \(O(\log U)\) 轮总时间为

\[ T(n)=\tilde O(C^{8/3}\log U)=\tilde O(m^{8/3}\log^{-5/3}U)=\tilde O(m^{8/3}\cdot (m^{7/16})^{-5/3})=\tilde O(m^{16/31}). \]

故问题的核心在于：要寻求一种压缩方式使得平均 \(C=O(m/\log U)\)，且对于流的影响较小。

基本方法

[1] 提出的算法同样由 \(O(\log U)\) 构成，每轮的步骤是：

  1. 收缩(comtraction)。

  2. 压缩（算法的核心）。

  3. 运行 Goldberg。

  4. 恢复对应到原图。

Abundant Arc

每轮算法的输入和输出都表示为 \((r, S, T)\)，其中 \(r\) 是残余网络，\(C_{S, T}\) 是一组源汇割。可知在残余网络中至多还可以增长 \(c(S, T)\) 的流，记作流上限 \(\Delta=c(S, T)\)（和 Goldberg 中的 \(\Delta\) 同义）。

Abundant Arc: 若有一边 \(r(e)\ge 2\Delta\)，则称其为 \(\Delta\)-Abundant Arc.

Theorem: 若在某轮算法中，输入为 \((r, S, T): \Delta\)，输出为 \((r', S', T'): \Delta'\)，且若 \(r(e)\ge 2\Delta\) 是 \(\Delta\)-Abundant Arc，则在结束后，\(r'(e)\ge 2\Delta'\) 是 \(\Delta'\)-Abundant Arc.

Proof: 设 \(e\) 增广了 \(x\)，即 \(r(e)-r'(e)=x\)，则有 \(\Delta'\le \Delta-x\)。故而

\[ \begin{align*} r'(e)&=r(e)-x\\ &\ge 2\Delta-x\\ &\ge 2(\Delta'+x)-x\\ &\ge 2\Delta' \end{align*} \]

故而 Abundant Arc 集合只会增加，不会减少。

收缩

对输入 \((r, S, T)\)，可以先将 Abundant Arc 环收缩：在收缩后的图上的流，必然可以满足收缩前的图的流。

对于算法的 3. 运行 Goldberg，为了证明的方便，假设结束后的流 \(\Delta'\le \Delta/(8m)\)。可以发现复杂度只影响对数倍。

四类弧

把图中所有弧分为四类：

  • Little Arc(\(L\))：弧 \(\langle i, j\rangle\) 满足 \(c(\langle i, j\rangle) + c(\langle j, i\rangle)< \Delta/(64m^3)\).
  • Medium Arc(\(M\)): 弧 \(\langle i, j\rangle\) 满足上式 \(\ge \Delta/(64m^3)\)，但正、反向弧都不是 Abundant Edge。
  • Abundant Arc(\(A\))。
  • Anti Abundant Arc(\(A'\))：反向弧在 \(A\) 中的弧。

注意到因为收缩后的图无 Abundant Arc 环，故一条边不能既在 \(A\) 中又在 \(A'\) 中。\(L, M, A, A'\) 构成了弧集的一个划分。

压缩 - 压缩掉一些顶点

如果一个顶点同时满足以下两个条件，则它可以被压缩（Compatible）：

  • 与它相邻的边没有 Medium Arc；
  • 进入它的 Anti Abundant Arc 的残余容量和与离开它的相差不超过 \(\Delta/(16m^2)\)。

换言之：一个顶点保留（是 Criticle）的条件是，满足以下条件之一：

  • 与它相邻的边有 Medium Arc；
  • 进入它的 Anti Abundant Arc 的残余容量和与离开它的相差超过 \(\Delta/(16m^2)\)。

直观理解，当一个顶点旁边的与 Abundant Arc 无关的边都是微不足道的时候，且 Anti Abundant Arc 流入和流出量基本相抵时，它是不重要的。

压缩 - 忽略掉一些路径

如果一条路径 \(P\) 中，存在某条 Little Arc： 则它可以增流的量至多为 \(\Delta/(64m^3)\)，可以忽略。故只需考虑 \(P\) 经过 Medium Arc、Abundant Arc 和 Anti Abundant Arc。

Claim: \(P\) 中若存在 Anti Abundant Subpath 是以 Compatible 顶点为端点，则也可以忽略。

因此，只需考虑的路径是：仅包含 Medium Arc、Abundant Arc、Auti Abundant Path（以 Criticle 顶点为端点）的路径。

于是只需在 Criticle 顶点和以下三种边中运行 Goldberg 最大流算法: 当 \(i, j\) 都是 Criticle 时

  • Medium 边；
  • 伪 Abundant 弧：若在原图中存在 \(i\Rightarrow j\) 的 Abundant Path，则有容量为 \(2\Delta\) 的 \(\langle i, j\rangle\) 弧；
  • 伪 Anti Abundant 弧：若在原图中存在 \(i\Rightarrow j\) 的 Anti Abundant Path，则有容量为所有这样的路径的残余容量和的弧 \(\langle i, j\rangle\)。

复杂度证明

Theorem: Criticle 顶点在全部 \(O(\log U)\) 轮算法中共 \(O(m)\) 个，故每轮平均 \(O(m/\log U)\)，故开头的复杂度分析正确。

Proof: 注意到对于原图中的弧:

  • 对于 Medium Arc，在 \(3\) 次操作后一定会变成 Abundant Arc；
  • 对于所有相邻弧都不是 Medium Arc，但是因为"进入它的 Anti Abundant Arc 的残余容量和与离开它的相差超过 \(\Delta/(16m^2)\)"而不能被压缩的 Criticle 顶点，在 \(4\) 轮后一定会有一条 Anti Abundant Arc 变为 Abundant Arc，进而形成 Abundant Cycle 被收缩。

Dinic 算法

(尽管正确的名字可能是 Dinitz，但就这么叫了)

主要思想

每次对于残余网络 \(r\)，进行一次 BFS，按照从 \(s\) 的距离得到分层图 \(r_d\)。

对于 \(r_d\) 进行若干次 DFS，找出在 \(r_d\) 上 阻塞流，即无法从 \(s\) 到 \(t\) 得到更多的流(不考虑退流)。

1
2
3
4
5
6
7
8
9
10
def Dinic(r, s, t):
    maxflow = 0
    flow = 0
    while bfs() gets a connective graph from s to t:
        while True:
            flow = dfs(s, INF)
            maxflow += flow
            if (flow == 0):
                break
    return maxflow

可以看到 Dinic 算法是 Ford-Fulkerson 增广的一种变种，正确性证明和 FF 算法相同，以下主要考虑其复杂度。

算法复杂度

Theorem 1：对于单轮的分层图，DFS 求出阻塞流的复杂度为 \(O(nm)\)。

Theorem 2: Dinic 算法至多考虑 \(O(n)\) 次分层图。

Theorem 3: 从上述两个定理可知，Dinic 算法的总复杂度为 \(O(n^2m)\)，但对于平均情况（以及特殊网络）有更好的复杂度。

特殊图上的复杂度

  • 若网络中全部弧的容量均为 \(1\)，则 Dinic 算法的复杂度为 \(O(m\cdot \min\lbrace n^{2/3}, m^{1/2}\rbrace)\)。

  • 若网络中全部弧的容量均为 \(1\)，且除源点和汇点外的每个点均满足 \(d^-(u)=1\) 或 \(d^+(u)=1\)，则 Dinic 算法的复杂度为 \(O(m\sqrt n)\)。

对于二分图最大匹配，注意到该复杂度与 Hopcroft-Karp 算法相同。实质上，两个算法的本质是相同的。

参考资料

[1] James B. Orlin. 2013. Max flows in O(nm) time, or better. In Proceedings of the forty-fifth annual ACM symposium on Theory of Computing (STOC '13). Association for Computing Machinery, New York, NY, USA, 765–774. https://doi.org/10.1145/2488608.2488705

[2] V. King, S. Rao, and R. Tarjan. A faster deterministic maximum flow algorithm. J. Algorithms, 23:447–474, 1994.

[3] A. V. Goldberg and S. Rao. Beyond the flow decomposition barrier. Journal of the ACM, 45:783–797, 1998.

[4] https://oi-wiki.org/graph/flow/max-flow/