Tight Bounds on Vertex Connectivity Under Sampling

Abstract : A fundamental result by Karger [10] 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 either vertices or edges are sampled. 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. If edges are sampled with probability $p = Ω(log(n)/k)$ then the sampled subgraph has vertex connectivity $Ω(kp$), with high probability. Both bounds are existentially optimal.
Type de document :
Article dans une revue
ACM Transactions on Algorithms, Association for Computing Machinery, 2017, 13 (2), pp.19:1 - 19:26. 〈10.1145/3086465〉
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-01635743
Contributeur : George Giakkoupis <>
Soumis le : mercredi 15 novembre 2017 - 16:02:43
Dernière modification le : mercredi 16 mai 2018 - 11:24:13
Document(s) archivé(s) le : vendredi 16 février 2018 - 15:28:30

Fichier

talg2017kvc.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 Sampling. ACM Transactions on Algorithms, Association for Computing Machinery, 2017, 13 (2), pp.19:1 - 19:26. 〈10.1145/3086465〉. 〈hal-01635743〉

Partager

Métriques

Consultations de la notice

153

Téléchargements de fichiers

41