Karger 随机收缩算法 | Codeboy's Blog

形式陈述

算法与状态模型

经典 Karger 算法是求全局最小割的随机化算法，输入为无权简单图。运行中，每个超点代表一组原顶点；在当前跨超点的多重边中均匀随机选一条，收缩其两个端点，删除由此产生的自环并保留全部平行边。直到只剩两个超点，输出它们之间所有平行边对应的原割。输入仍是基础简单图，收缩后的多重图只是带原边身份的算法状态；保留 multiplicity 才等价于从仍跨分量的原边均匀抽样。

固定最小割存活概率

固定一个大小为 $\lambda$ 的最小割。剩 $r$ 个超点且该割尚存活时，每个超点 degree 至少 $\lambda$ ，故当前边数至少 $r\lambda/2$ 。下一条随机边落在该割上的概率至多 $2/r$ ，避开概率至少 $1-2/r$ 。从 $r=n$ 乘到 3：

\prod_{r=3}^n\left(1-\frac2r\right)=\frac{2}{n(n-1)}.

成功事件是这一个固定最小割始终未被收缩；若图有多个最小割，算法总成功概率只会更大。

直觉

平行边图像

收缩一组顶点后，两个超点之间可能代表许多原边。若把它们合成一条无权边，原来跨割边被抽中的概率会被人为降低，存活分析失真；必须保留多重边或以 multiplicity 作为抽样权重。

算法不尝试识别哪条割最优，而是让某个固定最小割在随机过程中“幸存”。只要从未收缩它的边，最终两个超点间的割就仍包含这条原最小割；度数下界把每一步误伤它的概率压住，连乘后得到一次试验的成功率。这个证明追踪的是一条固定割，不是假定算法预先知道它。

随机收缩割内边后固定最小割幸存，并保留两条平行边的重数 — 安全收缩与最小割幸存

例子与边界

放大、权重与失败保证

单次随机收缩到输出候选割时，基础算法已经完整；独立重复属于外层成功率放大。重复 $R=\Theta(n^2\log(1/\delta))$ 次并取最小输出，可把失败率降至 $\delta$ 。算法是 one-sided Monte Carlo：输出的总是一条真实割，所以可能大于最优值，却绝不会小于真实最小割。

非负整数容量可等价展开为平行边；一般非负实权图则应按当前跨边容量比例采样，并把平行边容量相加计入割值，不能进行不可承受的物理展开。负容量不符合全局最小割的模型与存活证明。若原简单图不连通，最小割已经为零，应先直接返回分量划分。Karger–Stein 的递归收缩提高单次成功率，但不是本基础算法的同义实现。

推论与应用

原边数组上的收缩状态

一种不改写图的实现把所有原边留在数组中，用并查集表示当前超点：

初始化每个顶点为单独分量，分量计数为 $n$ ；
均匀抽一个原边下标，并求其两端当前根；
两根相同说明该边已成自环，本轮拒绝并重抽；
两根不同则 union，分量计数减一；
剩两个分量时扫描原边，跨根的边数就是候选割值。

条件在“仍跨分量”上的拒绝采样仍均匀选择当前多重边，而且平行原边自然保留 multiplicity。接近结束时自环比例可能很高，运行时间取决于拒绝次数；定期重建活跃边数组能控制这一点，却需另计扫描成本。

为输出割而不只是割值，最终还要按两个 DSU 根收集原顶点。每次独立试验保存自己的随机种子与最佳分区；只保留最小数值而丢弃分区，无法交付可验证的割证书。实权图应按当前跨边权重抽样，不能用不可承受的平行边展开模拟。

参考资料

David Karger, Global Min-Cuts in RNC, and Other Ramifications of a Simple Min-Cut Algorithm, SODA, 1993.
David Karger, Clifford Stein, A New Approach to the Minimum Cut Problem, JACM, 1996.

形式陈述 ​

算法与状态模型 ​

固定最小割存活概率 ​

平行边图像 ​

放大、权重与失败保证 ​