2019/09/24 by Jacob Holm, Valerie King, Holm, Jacob +7 · 1 citation
Computer Science · #Complexity and Algorithms in Graphs #Algorithms and Data Compression #Advanced Graph Theory Research
paper · pdf · doi:10.48550/arxiv.1909.11147
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≥ clog 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.