Algorithmic Theory of Networks Seminar: George Giakkoupis
- Date: 03/06/2015
George Giakkoupis, INRIA
Bio: George Giakkoupis is a Permanent Researcher at INRIA Rennes, in France. He received his PhD from the University of Toronto in 2008, and was a Postdoctoral Fellow at Université Paris 7 and the University of Calgary. His expertise is in the design and analysis of algorithms, in particular, randomized and distributed algorithms. He has worked on epidemic protocols, search in social networks, peer-to-peer networks, and shared-memory distributed computing.
University of Calgary
Vertex Connectivity under Vertex Sampling
A fundamental result by Karger (1994) states that for any k-edge connected graph with n nodes, independently sampling each edge with probability p = Omega(logn / k) results in a graph that has edge connectivity Omega(kp), with high probability. We prove the analogous result for vertex connectivity when independently sampling vertices. We show that for any k-vertex-connected graph with n nodes, if each node is independently sampled with probability p = Omega(sqrt{logn / k}), then the subgraph induced by the sampled nodes has vertex connectivity Omega(kp^2), with high probability. This bound is existentially optimal.
This is a joint work with Keren Censor-Hillel, Mohsen Ghaffari, Bernhard Haeupler and Fabian Kuhn, and appeared at SODA'15.