Metraipolis › archive › dc_ebcabd93f9fa

Two choices suffice: $k$-out sampling leaves $O(n/k)$ intercomponent edges for $k\geq 2$ — arXiv:2610.42067

Source: arXiv (en)
Original: https://arxiv.org/abs/2610.42067
License (as archived): CC0-1.0
Archived: 2026-11-02T05:01:24.849Z
SHA-256 of the archived text: 781c98359303b1ffb2746f959838ab52391d432c4e17e54788321eeb20313289
Stable URL of this page: https://metraipolis.com/documento/dc_ebcabd93f9fa

How to cite

Two choices suffice: $k$-out sampling leaves $O(n/k)$ intercomponent edges for $k\geq 2$ — arXiv:2610.42067 — arXiv (en), https://arxiv.org/abs/2610.42067 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_ebcabd93f9fa (Metraipolis archive dc_ebcabd93f9fa, sha256 781c98359303b1ffb2746f959838ab52391d432c4e17e54788321eeb20313289)

BibTeX

@misc{dcebcabd93f9fa,
  title = {Two choices suffice: $k$-out sampling leaves $O(n/k)$ intercomponent edges for $kgeq 2$ — arXiv:2610.42067},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.42067},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_ebcabd93f9fa; sha256 781c98359303b1ffb2746f959838ab52391d432c4e17e54788321eeb20313289},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.42067. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.CO, nuovi lavori del giorno).
Categorie arXiv: Discrete Mathematics (cs.DM) ; Data Structures and Algorithms (cs.DS); Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2610.42067 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-02T04:47:57.720Z dalla pagina https://arxiv.org/list/math.CO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).