Tight Bounds on Vertex Connectivity Under Vertex Sampling

Abstract : A fundamental result by Karger (SODA 1994) states that for any λ-edge-connected graph with n nodes, independently sampling each edge with probability p = Ω(log n/λ) results in a graph that has edge connectivity Ω(λp), with high probability. This paper proves the analogous result for vertex connectivity, when sampling vertices. We show that for any k-vertex-connected graph G with n nodes, if each node is independently sampled with probability p = Ω(log n/k), then the subgraph induced by the sampled nodes has vertex connectivity Ω(kp^2), with high probability. This bound improves upon the recent results of Censor-Hillel et al. (SODA 2014), and is existentially optimal.
Type de document :
Communication dans un congrès
26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2015), Jan 2015, San Diego, CA, United States. pp.2006-1018, 2015, 〈10.1137/1.9781611973730.133〉
Liste complète des métadonnées

Littérature citée [16 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01250519
Contributeur : George Giakkoupis <>
Soumis le : lundi 4 janvier 2016 - 23:06:17
Dernière modification le : vendredi 16 novembre 2018 - 01:39:42

Fichier

soda15_kvc.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Keren Censor-Hillel, Mohsen Ghaffari, George Giakkoupis, Bernhard Haeupler, Fabian Kuhn. Tight Bounds on Vertex Connectivity Under Vertex Sampling. 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2015), Jan 2015, San Diego, CA, United States. pp.2006-1018, 2015, 〈10.1137/1.9781611973730.133〉. 〈hal-01250519〉

Partager

Métriques

Consultations de la notice

322

Téléchargements de fichiers

92