Skip to Main content Skip to Navigation
Journal articles

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.
Document type :
Journal articles
Complete list of metadata

Cited literature [16 references]  Display  Hide  Download

https://hal.inria.fr/hal-01635743
Contributor : George Giakkoupis <>
Submitted on : Wednesday, November 15, 2017 - 4:02:43 PM
Last modification on : Saturday, July 11, 2020 - 3:18:28 AM
Long-term archiving on: : Friday, February 16, 2018 - 3:28:30 PM

File

talg2017kvc.pdf
Files produced by the author(s)

Identifiers

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⟩

Share

Metrics

Record views

266

Files downloads

247