Abstract 这篇文章扩展了 Stoer-Wagner 算法, 使得算法的每一个 phase 可以用额外的 的时间算出来一个 - max flow, 同时这也是在这个 phase 中算出来的一个 certificate.

无向图 且 , 边权 . 定义 表示 weighted adjacency of to , 其实就是 到 中每个点的 weight 之和.

Stoer-Wagner 算法是这样的: 该算法包含 个阶段, 每一阶段找两个顶点之间的一个 min-cut 然后将它们合并为一个顶点.

的 global min-cut 就是这 个阶段中最小的 cut, 每个阶段的时间为 . 这篇文章给 Stoer-Wagner 算法一个扩展, 每一轮用额外的 的时间再找一个等于 min cut 的 flow.

Stoer-Wagner 用 maximum adjacency search (MA search) 来给顶点编号, 步骤如下: 1. 随机选一个顶点 标为 , ; 2. For from to , , 然后 标为 并放到 里.

这个叫 MA search, 是不是在说这样得到了一个 MA ordering, 不知道.

记 是最后编号的两个顶点, 则 是一个 min - cut. 令 , 现在构造一个 to 的值为 的 flow. 以编号指代所有顶点, 然后 .

得到 ordering 并以编号指代顶点之后, 我们可以直接比较顶点之间的大小, 当我们说某个顶点 大于 时, 实际上是在说 的编号比 大, 在这个 ordering 中排在 的后面.

主要的一个 technical tool 是 -reduction.

Definition 1 (-Reduction, ) 一个 -reduction 将 修改为 , 使得

• 对所有 有 ,
• 对所有 有 .

Lemma 2. 设 如上定义. 则在 上的 MA search 可以产生由 induce 的 node labeling.

Lemma 2 是在说, -reduction 对 weight function 的改变不影响 MA search 的结果.

证明时用归纳法, 只需要证明 -reduction 之后 可以在 之间被 label 就行.

现在定义两条路径 starting from 和 start from :

• 满足: , 被定义为: 满足 且标号大小小于 的具有最大标号的顶点. 这里的标号就是 MA ordering 中的标号, 即 .
• 的定义是类似的.

再定义 --join 是具有最大标号的同时属于 的顶点.

Lemma 3. (1) 对任意 , 如果不存在 使得 出现在 和 上, 则 .

2. 如果 (1) 中定义的 , 则 --join 必然存在, 并且对任意比 --join 大的 , 必然有 .

Lemma 3 是在说什么呢?

将 --join 记作 . 由于 是 和 的公共顶点, 因此考虑这样一条路径 : 以 为起点到 , 再从 沿着 的反向到 , 并设 是 上的最小权边, 那么我们可以从 经过 push 一个大小为 的 flow 到 . 我们现在构造一个 -reduction, 这里的 就是上面定义的 .

我们定义 的 incoming edge 是将 与比 更小的点连起来的那些边, 即 且 . 这个 -reduction 是这样的, 将 的每个 incoming edge 的权重

• reduce 为 , 如果 不在 或者 是 上标号最小的点,
• reduce 为 , 如果 在 上且不是标号最小的点.

这里 是正整数, 所以 就是前文定义的那样.

在 -reduction 的操作下, 什么样子的边不会被 reduce 呢?

这个 -reduction 有下面的性质:

• 上的边的权重都被 reduce 为 (也就是我们在 上创建了一个大小为 的 flow)
• 满足 Lemma 2, 在 MA research 下能够产生和 使用 MA search 相同的 node labeling, 或者说 ordering.
• .

现在描述一个构造一个大小为 的 - flow 的算法, 这个算法是一系列 reduction.

最终给出了这个线性的 implementation.

1. 对每个 , 根据 以增序用桶排在线性时间内排所有的边 , 且 .
2. 对 flow 初始化: 如果边 存在, 则充满 并把它删了. 删了之后令 , 然后以指向 的方向充满所有以 为端点的边, 从 中 push 出一个大小为 的 flow, 优先选择更大的 (从边 流出). 更具体地, 设 表示从 到 的 flow 的大小, 则上面说的过程是:
   • 对任意 , 令
   • 对任意 , 令
3. ,