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 作为抽样权重。

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

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

例子与边界

放大、权重与失败保证

单次随机收缩到输出候选割时，基础算法已经完整；独立重复属于外层成功率放大。对 $0<\delta<1$ ，独立重复 $R=\lceil\tfrac{n(n-1)}2\ln(1/\delta)\rceil$ 次并取最小输出，失败概率至多 $(1-2/[n(n-1)])^R\le\exp(-2R/[n(n-1)])\le\delta$ 。这给出 $O(1+n^2\log(1/\delta))$ 次试验的统一界，也包含只需至少一次试验的边界。若把从当前活跃边中均匀抽取一条视为基本随机操作，单次只执行 $n-2$ 次收缩，可用有界步数实现，具有单侧 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.

形式陈述 ​

算法与状态模型 ​

固定最小割存活概率 ​

平行边图像 ​

放大、权重与失败保证 ​