arXiv preprint ·
Two choices suffice: $k$-out sampling leaves $O(n/k)$ intercomponent edges for $k\geq 2$
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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\geq2$, 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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Discrete Mathematics
Degree Realization with Maximum Matching
The Value of Steiner Hubs in Two-Hop Distance Labeling
The C-3PO Framework: Algorithms for $\#\mathrm{BIS}$-Hard Problems on Graphs with Low Threshold Rank or High Girth
Metric Testing: A Characterization of One-Sided Testability
Monotone Local Search with Sample-Dependent Running Times
Get the few papers worth your time in Discrete Mathematics every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.