Random contractions and sampling for hypergraph and hedge connectivity
We initiate the study of hedge connectivity of undirected graphs, motivated by dependent edge failures in real-world networks. In this model, edges are partitioned into groups called hedges that fail together. The hedge connectivity of a graph is the minimum number of hedges whose removal disconnect...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Association for Computing Machinery
2018
|
| Online Access: | http://hdl.handle.net/1721.1/116309 https://orcid.org/0000-0003-4213-9898 https://orcid.org/0000-0002-0024-5847 |
| _version_ | 1826192598083043328 |
|---|---|
| author | Panigrahi, Debmalya Ghaffari, Mohsen Karger, David R |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Panigrahi, Debmalya Ghaffari, Mohsen Karger, David R |
| author_sort | Panigrahi, Debmalya |
| collection | MIT |
| description | We initiate the study of hedge connectivity of undirected graphs, motivated by dependent edge failures in real-world networks. In this model, edges are partitioned into groups called hedges that fail together. The hedge connectivity of a graph is the minimum number of hedges whose removal disconnects the graph. We give a polynomial-time approximation scheme and a quasi-polynomial exact algorithm for hedge connectivity. This provides strong evidence that the hedge connectivity problem is tractable, which contrasts with prior work that established the intractability of the corresponding s−t min-cut problem. Our techniques also yield new combinatorial and algorithmic results in hypergraph connectivity. Next, we study the behavior of hedge graphs under uniform random sampling of hedges. We show that unlike graphs, all cuts in the sample do not converge to their expected value in hedge graphs. Nevertheless, the min-cut of the sample does indeed concentrate around the expected value of the original min-cut. This leads to a sharp threshold on hedge survival probabilities for graph disconnection. To the best of our knowledge, this is the first network reliability analysis under dependent edge failures. |
| first_indexed | 2024-09-23T09:22:36Z |
| format | Article |
| id | mit-1721.1/116309 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T09:22:36Z |
| publishDate | 2018 |
| publisher | Association for Computing Machinery |
| record_format | dspace |
| spelling | mit-1721.1/1163092022-09-30T14:21:32Z Random contractions and sampling for hypergraph and hedge connectivity Panigrahi, Debmalya Ghaffari, Mohsen Karger, David R Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Ghaffari, Mohsen Karger, David R We initiate the study of hedge connectivity of undirected graphs, motivated by dependent edge failures in real-world networks. In this model, edges are partitioned into groups called hedges that fail together. The hedge connectivity of a graph is the minimum number of hedges whose removal disconnects the graph. We give a polynomial-time approximation scheme and a quasi-polynomial exact algorithm for hedge connectivity. This provides strong evidence that the hedge connectivity problem is tractable, which contrasts with prior work that established the intractability of the corresponding s−t min-cut problem. Our techniques also yield new combinatorial and algorithmic results in hypergraph connectivity. Next, we study the behavior of hedge graphs under uniform random sampling of hedges. We show that unlike graphs, all cuts in the sample do not converge to their expected value in hedge graphs. Nevertheless, the min-cut of the sample does indeed concentrate around the expected value of the original min-cut. This leads to a sharp threshold on hedge survival probabilities for graph disconnection. To the best of our knowledge, this is the first network reliability analysis under dependent edge failures. 2018-06-14T14:49:34Z 2018-06-14T14:49:34Z 2017-01 Article http://purl.org/eprint/type/ConferencePaper http://hdl.handle.net/1721.1/116309 Ghaffari, Mohsen, David R. Karger, and Debmalya Panigrahi. "Random contractions and sampling for hypergraph and hedge connectivity." SODA '17 Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 16-19 January, 2017, Barcelona, Spain, ACM, 2017, pp. 1101-1114. https://orcid.org/0000-0003-4213-9898 https://orcid.org/0000-0002-0024-5847 en_US http://dl.acm.org/citation.cfm?id=3039757 SODA '17 Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Association for Computing Machinery Other univ. web domain |
| spellingShingle | Panigrahi, Debmalya Ghaffari, Mohsen Karger, David R Random contractions and sampling for hypergraph and hedge connectivity |
| title | Random contractions and sampling for hypergraph and hedge connectivity |
| title_full | Random contractions and sampling for hypergraph and hedge connectivity |
| title_fullStr | Random contractions and sampling for hypergraph and hedge connectivity |
| title_full_unstemmed | Random contractions and sampling for hypergraph and hedge connectivity |
| title_short | Random contractions and sampling for hypergraph and hedge connectivity |
| title_sort | random contractions and sampling for hypergraph and hedge connectivity |
| url | http://hdl.handle.net/1721.1/116309 https://orcid.org/0000-0003-4213-9898 https://orcid.org/0000-0002-0024-5847 |
| work_keys_str_mv | AT panigrahidebmalya randomcontractionsandsamplingforhypergraphandhedgeconnectivity AT ghaffarimohsen randomcontractionsandsamplingforhypergraphandhedgeconnectivity AT kargerdavidr randomcontractionsandsamplingforhypergraphandhedgeconnectivity |