最大宽度增广求最大流

发表于 2023-06-18 分类于学习笔记

一种可以在 $O(m\log |f| (m + n) \log m)$ 时间复杂度内求解最大流的诡异方法，其中 $|f|$ 是最大流流量。方法名称是我自己胡乱翻译的，原名叫：The Fattest Augmenting Path Heuristic。

求解最大流通常使用的是 Ford-Fulkerson 方法，但是各个方法找增广路的方式有所区别。 Edmonds-Karp 找的是最短的增广路，Dinic 则是建立的分层图找增广路，还有其他更多的算法。

本文介绍的找增广路的方法是，找到路径上边权最小值最大的增广路，称为最大宽度增广路。

以下均假设图 $G=(V,E,c,S,T)$ ，且 $n=|V|,m=|E|$ ，且容量限制均为整数（有理数与实数可以通过整数扩充）。

找到源点与汇点之间的最大宽度路径可以使用魔改 Dijkstra 最短路算法完成，时间复杂度为 $O((m + n) \log m)$ 。

我们的首要任务是证明：

命题 $1$ ：这样找增广路径则增广次数为 $O(m\log |f|)$ 级别，其中 $|f|$ 为最大流流量。

为此我们先证明一个引理：

引理 $1$ ：对于任意一个流网络图 $G=(V,E,c,S,T)$ ，设其最大流流量为 $|f|$ ，则 $G$ 中存在一条可行流流量至少是 $|f|/|E|$ 。

证明：为证明此结论，我们尝试把最大流进行分解。

设图 $G$ 的最大流为 $f:E\to \mathbb R$ （也就是说 $f$ 是一个映射，给出了最大流中边对应的流量），而最大流的流量为 $|f|$ 。

我们按照如下方式讲流进行分解：

值得注意的是只要有当前残量网络的最大流大于 $0$ ，就一定可以找到这样的路径。

这样我们就分解出了若干个可行流 $f_1,f_2,\ldots,f_k$ ，这些流并起来是 $f$ 。

注意到每次找到一个 $f_i$ ，都会使得至少一条边的 $f$ 变为 $0$ ，所以 $k\le |E|$ 。

又因为 $|f_1|+\cdots + |f_k|=|f|$ ，所以存在一个 $1\le i\le k$ ，使得 $|f_k|\ge |f|/|E|$ ，得证。 $\Box$

那么这时再回到原命题：

证明：设第 $i$ 次增广完当前的流量为 $f_i$ ，对饮的残量网络为 $G_i$ 。则 $G_i$ 上的最大流显然是 $r_i=|f|-f_i$ 。

根据引理 $1$ 有： $f_{i+1}\ge f_i+\dfrac{r_i}{2m}$ （除 $2m$ 是因为残量网络上是有反向边的）。

所以： $r_{i+1}=|f|-f_{i+1}\le |f|-f_i-\dfrac{r_i}{2m}=r_i\left(1-\dfrac 1{2m} \right)$ 。

初始时有： $f_0=0,r_0=|f|$ ，所以：

r_i\le r_0\left(1-\dfrac 1{2m} \right)^2=|f|\left(1-\dfrac 1{2m} \right)^2\le |f|\text{e}^{-i/2m}

故当 $i>2m\ln |f|$ 时有 $r_i<1$ ，又因为 $r_i$ 是整数，所以 $r_i=0$ 。

所以增广次数级别为 $O(m\log |f|)$ ，得证。 $\Box$

其实上述证明方法还可以用来证明集合覆盖朴素贪心解法的近似优越性。

集合覆盖问题如下：给定正整数 $n$ 与集合 $\{1,2,\ldots,n\}$ 的 $m$ 个子集 $S_1,S_2,\ldots,S_m$ ，找到最少的集合，使得其全部并起来是 $\{1,2,\ldots,n\}$ 。

朴素的贪心想法就是选择当前可以新覆盖最多点的集合，以下命题说明这一算法的近似优越性。

命题 $2$ ：如果最优解要取 $k$ 个集合，则使用如上贪心策略取的集合数量不会超过 $k\ln n$ 。

证明：记 $r_i$ 为执行完第 $i$ 步后还未被覆盖的点个数。则因为最优解是 $k$ ，所以一定有一个集合覆盖了其中至少 $r_i/k$ 个点。那么之后的证明和命题 $1$ 的证明无二致。 $\Box$

实际上根据 PCP 理论，我们有：任何多项式算法都不可能得到上界为 $o(k\ln n)$ 的解，除非 $\text P=\text{NP}$ 。