Vertex Connectivity Under Sampling

A fundamental graph-theoretic question is: If we independently sample each node (or edge) of a graph G with some probability p, or equivalently, delete each node (or edge) with probability 1-p, how does the connectivity of the resulting graph compare to that of G? In 1994 Karger answered this question for the case of edge connectivity. I will present the analogous result for vertex connectivity.

This is a joint work with Keren Censor-Hillel, Mohsen Ghaffari, Bernhard Haeupler and Fabian Kuhn, and appeared in SODA'15.