图的割稀疏化

Cut sparsifier 定义 ​

本页把“图稀疏化”限定为 cut sparsification，不把矩阵／谱保证强制进共同入口。对非负加权无向图公理库有限简单无向图Graph · Finite simple undirected graph · 图用有限顶点集合和无序二元边集合表示的简单无向图。 $G=(V,E,w)$，$\epsilon$-cut sparsifier $H$ 通常保留同一顶点集，并要求对所有 $S\subseteq V$ 同时成立

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

量词是全部 $2^{|V|}$ 个割上的一个共同事件，不是每个固定割各自高概率。

重要性采样框架 ​

给边 $e$ 选择概率 $p_e$，采中后在 $H$ 赋权 $w_e/p_e$，未采中则删去；固定割的估计因此无偏。为了 uniform 保证，$p_e$ 需随 edge strength、有效电阻等重要性增大，并用浓缩加割计数/矩阵方法控制所有割。仅让每条边独立均匀采样，即使无偏，也可能漏掉一个细割的唯一关键边。

稠密网络例子 ​

全网遥测图可能有近二次边。cut sparsifier 把边压到近线性规模后，任意数据中心分区的跨区容量仍在 $1\pm \epsilon$ 内，可加速多次 cut/flow 计算；被采边的权重必须放大以补偿低采样率。

相邻概念边界 ​

保留所有割不等于保留所有点对最短路；后者更接近 spanner。Spectral sparsifier 要求所有向量的 Laplacian 二次型近似，通常推出 cut 近似但定义更强。动态 sparsification 是算法框架，不是静态随机抽边的自动性质。负边权会破坏割容量和采样浓缩的标准形式。

Uniform 保证的证明责任 ​

固定割可直接对独立采样边用 Chernoff，但对 $2^{n-1}$ 个割粗暴并集常过大。Benczúr–Karger 分析按割值分层，并利用近最小割数量受控的 cut-counting lemma；高容量割虽更多，却有更强浓缩。这个组合才把“每割高概率”升级成“所有割同时高概率”。

采样概率若用 edge strength 近似值，需证明估计不会把关键边概率低估过多。重权 $w_e/p_e$ 可能增大单边权，尾界参数也必须随之调整。

采样权重与共同事件 ​

若边 $e$ 以概率 $p_e$ 保留，进入 $H$ 后应赋权 $w_e/p_e$。因此对任意固定割，每条边贡献的期望仍为 $w_e$；只保留边却不重标权，会系统性缩小所有割。高强度边取较大 $p_e$，正是为了限制单条随机贡献的幅度。

困难不在单个固定割的无偏性，而在同一份 $H$ 要同时逼近指数多个割。证明需要割计数、边强度分层和集中不等式把失败事件合并，不能对 $2^n$ 个割直接套朴素 union bound。最终 $O(n\log n/{\epsilon }^2)$ 级边数依赖具体采样定理与常数，页面使用时应引用对应版本。

实现上先近似边强度，再独立采样并累加平行边权；零权边可删除，负权边则不在 cut sparsifier 的标准非负模型内。若后续算法关心拉普拉斯二次型而不只是割值，应使用 spectral sparsifier 的更强保证。

参考资料

• András Benczúr, David Karger, Approximating s–t Minimum Cuts in Õ(n²) Time, STOC, 1996.
• David Eppstein et al., Sparsification—A Technique for Speeding Up Dynamic Graph Algorithms, JACM, 1997.