Random k-out subgraph leaves only O(n/k) inter-component edges
Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Each vertex of an arbitrary simple graph on n vertices chooses k random incident edges. What is the expected number of edges in the original graph that connect different connected components of the sampled subgraph? We prove that the answer is O(n/k), when k ≥ c log n, for some large enough c. We conjecture that the same holds for smaller values of k, possibly for any k ≥ 2. Such a result is best possible for any k ≥ 2. As an application, we use this sampling result to obtain a one-way communication protocol with private randomness for finding a spanning forest of a graph in which each vertex sends only O (√n log n) bits to a referee.
Originalsprog | Engelsk |
---|---|
Titel | Proceedings - 2019 IEEE 60th Annual Symposium on Foundations of Computer Science, FOCS 2019 |
Antal sider | 14 |
Forlag | IEEE |
Publikationsdato | 2019 |
Artikelnummer | 8948658 |
ISBN (Elektronisk) | 9781728149523 |
DOI | |
Status | Udgivet - 2019 |
Begivenhed | 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019 - Baltimore, USA Varighed: 9 nov. 2019 → 12 nov. 2019 |
Konference
Konference | 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019 |
---|---|
Land | USA |
By | Baltimore |
Periode | 09/11/2019 → 12/11/2019 |
Sponsor | IEEE Computer Society Technical Committee on Mathematical Foundations of Computing |
Links
- https://arxiv.org/pdf/1909.11147.pdf
Indsendt manuskript
ID: 237757204