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
Standard
Random k-out subgraph leaves only O(n/k) inter-component edges. / Holm, Jacob; King, Valerie; Thorup, Mikkel; Zamir, Or; Zwick, Uri.
Proceedings - 2019 IEEE 60th Annual Symposium on Foundations of Computer Science, FOCS 2019. IEEE, 2019. 8948658.Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - GEN
T1 - Random k-out subgraph leaves only O(n/k) inter-component edges
AU - Holm, Jacob
AU - King, Valerie
AU - Thorup, Mikkel
AU - Zamir, Or
AU - Zwick, Uri
PY - 2019
Y1 - 2019
N2 - 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.
AB - 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.
KW - communication complexity
KW - Connected components
KW - Random subgraph
U2 - 10.1109/FOCS.2019.00058
DO - 10.1109/FOCS.2019.00058
M3 - Article in proceedings
AN - SCOPUS:85078476801
BT - Proceedings - 2019 IEEE 60th Annual Symposium on Foundations of Computer Science, FOCS 2019
PB - IEEE
T2 - 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019
Y2 - 9 November 2019 through 12 November 2019
ER -
ID: 237757204