CATS-Feb-13-2015
Title[edit]
Vertex Connectivity under Sampling
Speaker[edit]
Manish Purohit
Abstract[edit]
Consider the following random process - Given a graph G, each edge or vertex of G is sampled with probability p. We are now interested in the following natural question - How large should p be to guarantee that sampled graph is connected? Intuitively it is clear that if the base graph G has higher (edge or vertex) connectivity, then a smaller sampling probability should suffice.
In this setting, a fundamental result by Karger (STOC 94) states that for any k-edge connected graph with n nodes, independently sampling each edge with probability p = \Omega(log n / k) is sufficient to guarantee that the sampled graph has edge connectivity \Omega(kp). However, analogous results for vertex connectivity were only obtained very recently in a sequence of two papers by Censor-Hillel et al (SODA 2014, SODA 2015).
Censor Hillel et al introduced a novel technique of analyzing the sampling process in phases (also known as layers). The key idea is to show that connected components induced by the sampled vertices grow in each layer until finally we have only one component as desired. In this talk, we describe this layering technique and prove the following theorem - For any k-vertex connected graph with n node, independently sampling each vertex with probability p = Omega(log n / \sqrt(k)) is sufficient to guarantee that the sampled graph is connected.
This talk is based on the following two papers -
1. K. Censor-Hillel, M. Ghaffari, F. Kuhn. A New Perspective on Vertex Connectivity. SODA 2014
2. K. Censor-Hillel, M. Gharrafi, G. Giakkoupis, B. Haeupler, F. Kuhn. Tight Bounds on Vertex Connectivity Under Vertex Sampling. SODA 2015
