Subscribe to Events

Abstract: 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.

We give applications of this sampling lemma for models of distributed algorithms.

Based on joint work with Jacob Holm, Valeria King, Mikkel Thorup and Uri Zwick.