# Tight Bounds on Vertex Connectivity Under Sampling

3 ASAP - As Scalable As Possible: foundations of large scale dynamic distributed systems
Inria Rennes – Bretagne Atlantique , IRISA_D1 - SYSTÈMES LARGE ÉCHELLE
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〉
Domaine :

Littérature citée [19 références]

https://hal.inria.fr/hal-01635743
Contributeur : George Giakkoupis <>
Soumis le : mercredi 15 novembre 2017 - 16:02:43
Dernière modification le : mercredi 21 février 2018 - 01:57:01
Document(s) archivé(s) le : vendredi 16 février 2018 - 15:28:30

### Fichier

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

### 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〉

### Métriques

Consultations de la notice

## 79

Téléchargements de fichiers