给定一个包含 $n$ 个顶点的简单无向图，$k$-out 采样让每个顶点独立地以均匀概率（可重复）选择 $k$ 条相邻边，形成一个生成子图。我们证明，对所有整数 $k\ge2$，不同采样连通分量之间的原始边的期望数量为 $O\left(\frac{n}{k}\right)$。该结果完整地解决了 Holm、King、Thorup、Zamir 与 Zwick 的猜想，将此前需要 $\Theta(\log n)$ 次采样的要求降至每个顶点仅两次本地选择的最优阈值。对于 $k=1$ 时结论不再成立，而 $O(n/k)$ 的依赖在常数因子上是紧的。由于采样过程允许重复选择，结论同样适用于不放回的情形。一个直接的推论是，仅通过每个顶点的两次独立局部选择即可在期望意义上将任意简单图压缩为仅含 $O(n)$ 条边的商图，这对许多基于收缩的算法在实例规模上的削减至关重要。证明核心使用了切换论证：首先将跨分量边与桥的数量建立关联，然后引入一个按度数加权的分量势函数，并通过再次的切换论证对其期望进行上界估计。
点评