图的割稀疏化 | Codeboy's Blog

形式陈述

同时保留所有割

给定有限简单无向图 $G=(V,E,w)$ ，边容量为非负实数，且 $0<\varepsilon<1$ 。一个割稀疏器 $H$ 保留同一顶点集，只选取原图部分边并重新赋予非负权，要求对每个 $S\subseteq V$ 同时满足

(1-\varepsilon)w_G(\delta S) \le w_H(\delta S) \le(1+\varepsilon)w_G(\delta S).

其中 $\delta S$ 是跨越 $S$ 与补集的边集。这个不等式定义近似质量；“稀疏”还需报告 $H$ 的边数，例如下面构造给出的近线性规模。零权边可先删除，孤立顶点保留。

随机构造要求的是一份输出 $H$ 在同一个成功事件上满足全部割的界。对每个固定割分别有较高成功率，是较弱的量词陈述。

独立采样与重权

对每条正权边取 $0<p_e\le1$ ，独立抽取 $\xi_e\sim\operatorname{Bernoulli}(p_e)$ ；采中时赋权 $w_e/p_e$ ，未采中则不保留。固定割的估计由期望的线性性满足

\mathbb E\,w_H(\delta S) =\sum_{e\in\delta S}\mathbb E\!\left[\frac{\xi_ew_e}{p_e}\right] =\sum_{e\in\delta S}w_e.

这一步证明无偏；各概率还必须按图的结构选择，才能控制一次输出的误差。

Benczúr–Karger 使用边强度。对正权边 $e=uv$ ，令

k_e=\max_{U\subseteq V:\,u,v\in U}\lambda(G[U]),

其中 $\lambda(G[U])$ 是诱导子图的全局最小割值。这些 $U$ 至少有两个顶点；取 $U=\{u,v\}$ 可知 $k_e\ge w_e>0$ 。强度只看某个同时包含两端的内部高连通子图，与原图的固定 $u$ – $v$ 最小割值并非同一个参数。

对 $n\ge2$ 、固定常数 $d\ge1$ ，取

\rho=\frac{3(d+3)\ln n}{\varepsilon^2},\qquad p_e=\min\{1,\rho w_e/k_e\}.

Benczúr–Karger 的加权压缩定理保证，以 $1-O(n^{-d})$ 的概率，所有割同时满足上述近似，并且输出有 $O(n\rho)$ 条边。期望边数也至多为 $\rho(n-1)$ 。这里的概率包含边自身的权重因子 $w_e$ ；只有单位权输入才简化成与 $1/k_e$ 成正比。零或单顶点输入直接返回空边图。

直觉

采样不是平均删边。桥边控制一个只能由它跨越的割；对桥 $e$ ， $k_e=w_e$ ，因此上面的规则令 $p_e=1$ 。在高连通区域中，许多边有替代连接，可用较低概率保留，再通过重权补回固定割的期望容量。

把全图容量统一乘正数， $w_e$ 和 $k_e$ 同倍变化，所以 $w_e/k_e$ 及采样概率不变。这符合容量单位转换不应改变抽样结构的要求；只按加权强度的倒数采样就会失去这个性质。

关键割边高概率保留，冗余边按重要性采样并重权形成割稀疏图 — 割稀疏化的重要性采样与重权

图示意保边与重权的作用，不是在逐项执行上述保守常数的采样公式。对小图或很小的误差参数，所有 $p_e$ 都可能截断为一，此时构造保留原图，质量保证仍然成立。

例子与边界

期望正确仍会漏掉细割

若一条桥以概率 $p<1$ 被抽样，采中后赋权 $w/p$ ，其单边割的期望仍是 $w$ ；但以概率 $1-p$ ，该割在输出中变成零，违反任意 $\varepsilon<1$ 的乘性下界。无偏不能替代同时近似的概率定理。

割值为零也要保留。由于 $H$ 只选原图边，原来两个不相连分量间不会凭空出现新边；在成功事件上，原来正容量的割又不能降为零，因此正权支撑的连通分量保持不变。

保留的对象不同，保证也不同

割稀疏化保存跨分区容量，不承诺保留点对最短路；距离近似由 spanner 等结构处理。谱稀疏化控制全部实向量的 Laplacian 二次型，取向量为顶点子集的指示函数便得到割近似，所以其有效电阻采样也是一种割稀疏器构造。反向的同精度保证一般不成立，谱页给出三角形的显式反例。

负权会破坏这些非负容量和集中分析前提。动态图中的 sparsification 框架又需在更新后维护证书；一次静态随机采样没有自动提供这种更新接口。

推论与应用

边数界来自强度总量

加权强度满足 $\sum_e w_e/k_e\le n-1$ ，于是

\mathbb E|E_H|=\sum_ep_e\le\rho\sum_e w_e/k_e\le\rho(n-1).

这个强度引理可用最小割递归理解。对连通正权图，取值为 $\lambda$ 的全局最小割。每条跨割边的强度至少为 $\lambda$ ，因为整个图就是候选诱导子图；又至多为 $\lambda$ ，因为任何包含其两端的诱导子图都受这道割的限制。因此跨割部分的比值之和恰为一。两侧内部边在原图中的强度不小于在各自诱导子图中的强度，分别归纳，再加这一，得到 $n-1$ ；不连通图逐分量处理即可。

概率、构造成本与后续求解

采样部分属于随机化算法。共同成功事件的证明进一步使用强度分层，把图分解到适合割计数与集中界的子问题，再合并这些子问题的失败事件。直接把全部原图割的个别失败概率相加，可能重复累计同一次局部失败指数多次；细致分解负责控制这种重叠。边数的高概率界还需单独对采中边数做集中分析，不能把期望边数当作每次输出的硬上限。

精确求全部 $k_e$ 并非免费。快速构造使用下界估计 $\widetilde k_e\le k_e$ ，并同时保证 $\sum_e w_e/\widetilde k_e=O(n)$ ：前者使采样更保守，后者控制输出规模。只证明估计从不超过真实强度，却让估计任意小，会保住质量但可能完全失去稀疏性。

在共同成功事件上，可以把稀疏图交给后续割／流算法。若 $\widehat S$ 是 $H$ 的最小割， $S^*$ 是 $G$ 的最小割，则

w_G(\delta\widehat S) \le\frac{w_H(\delta\widehat S)}{1-\varepsilon} \le\frac{1+\varepsilon}{1-\varepsilon}w_G(\delta S^*).

因此输出分区有一份明确的原图近似保证；需要实际容量时再扫描原图核算。若后续要保留任意向量能量或做 Laplacian 预条件，应使用谱保证，而不是从割值近似自行推断。

参考资料

András A. Benczúr and David R. Karger, Randomized Approximation Schemes for Cuts and Flows in Capacitated Graphs, SIAM Journal on Computing 44(2), 2015，Lemma 4.11、Theorems 6.2–6.4：加权强度总量、压缩概率及可用的强度下界；§5.2 解释直接逐割求并的局限。
Daniel A. Spielman and Nikhil Srivastava, “Graph Sparsification by Effective Resistances,” SIAM Journal on Computing 40(6), 2011，谱近似及其割近似推论。
David Eppstein et al., “Sparsification—A Technique for Speeding Up Dynamic Graph Algorithms,” JACM, 1997，动态图中的另一类维护框架。

形式陈述 ​

同时保留所有割 ​

独立采样与重权 ​

期望正确仍会漏掉细割 ​

保留的对象不同，保证也不同 ​

边数界来自强度总量 ​

概率、构造成本与后续求解 ​

反向链接