Karger 随机收缩算法

算法 ​

为求全局最小割公理库全局最小割问题Global minimum cut在无向非负加权图中寻找任意非平凡顶点划分的最小割容量。，在无向多重图中均匀随机选一条当前边，收缩其两端为超点，删除自环但保留平行边；直到剩两个超点，输出它们之间所有平行边形成的割。保留 multiplicity 才等价于从原边均匀抽样。

固定最小割存活概率 ​

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

$$\prod _{r=3}^n(1-\frac{2}{r})=\frac{2}{n(n-1)}.$$

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

平行边图像 ​

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

放大与边界 ​

单次随机收缩到输出候选割时，基础算法已经完整；独立重复属于外层成功率放大。重复 $R=\mathrm{\Theta }(n^2\log \left(1/\delta \right))$ 次并取最小输出，可把失败率降至 $\delta$。算法是 one-sided Monte Carlo：可能输出较大割，但绝不会小于真实最小割。加权图需按权重采样或等价展开；负权不符合割容量模型。Karger–Stein 的递归收缩有更高成功率，不等同于本基础算法。

原边数组上的收缩状态 ​

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

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

条件在“仍跨分量”上的拒绝采样仍均匀选择当前多重边，而且平行原边自然保留 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.