HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
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 Connect in order to contact the contributor
Submitted on : Wednesday, November 15, 2017 - 4:02:43 PM
Last modification on : Monday, April 4, 2022 - 9:28:19 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

123

Files downloads

137