Two choices suffice: k-out sampling leaves O(n/k) intercomponent edges for k≥ 2
Abstract
Given a simple undirected graph on n vertices, random k-out sampling forms a spanning subgraph by having each vertex independently choose k incident edges uniformly with replacement. We prove that, for every integer k≥2, the expected number of original edges joining distinct sampled components is O(n/k). This resolves the conjecture of Holm, King, Thorup, Zamir, and Zwick in its full range, improving their logarithmic sampling requirement to the optimal threshold of two choices per vertex. The bound fails for k=1, and the dependence O(n/k) is tight up to constant factors. Our result holds with replacement and consequently also without replacement. In particular, this implies that contracting just two independent local choices per vertex suffices to reduce an arbitrary simple graph to a quotient with O(n) edges in expectation, which is crucial in reducing the instance size for many contraction-based algorithms. Our proof uses switching arguments to relate intercomponent edges to bridges and a degree-weighted component potential, whose expectation we also bound with a switching argument.
Related
- Triangles and quadrilaterals suffice
- Few small primes suffice to cover unit groups
- Three Standard Deviations Suffice While One Does Not
- Two moments suffice for Bessel approximation: conditioned differences, contingency tables, and probabilistic divide-and-conquer
- Three Machines Suffice for Local Hardening of Electromechanical Oscillations
BibTeX
@misc{chen2026choices,
title = {{Two choices suffice: $k$-out sampling leaves $O(n/k)$ intercomponent edges for $k\geq 2$}},
author = {Yanyu Chen and Yu Chen},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.42067},
eprint = {2610.42067},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.42067},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Two choices suffice: k-out sampling leaves O(n/k) intercomponent edges for k≥ 2
AU - Yanyu Chen
AU - Yu Chen
PY - 2026
DA - 2026/10/30
PB - arXiv
DO - 10.48550/arxiv.2610.42067
UR - https://arxiv.org/abs/2610.42067
AB - Given a simple undirected graph on n vertices, random k-out sampling forms a spanning subgraph by having each vertex independently choose k incident edges uniformly with replacement. We prove that, for every integer k≥2, the expected number of original edges joining distinct sampled components is O(n/k). This resolves the conjecture of Holm, King, Thorup, Zamir, and Zwick in its full range, improving their logarithmic sampling requirement to the optimal threshold of two choices per vertex. The bound fails for k=1, and the dependence O(n/k) is tight up to constant factors. Our result holds with replacement and consequently also without replacement. In particular, this implies that contracting just two independent local choices per vertex suffices to reduce an arbitrary simple graph to a quotient with O(n) edges in expectation, which is crucial in reducing the instance size for many contraction-based algorithms. Our proof uses switching arguments to relate intercomponent edges to bridges and a degree-weighted component potential, whose expectation we also bound with a switching argument.
ER -