Skip to main content

Random contractions and sampling for hypergraph and hedge connectivity

Publication ,  Conference
Ghaffari, M; Karger, DR; Panigrahi, D
Published in: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
January 1, 2017

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 st 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.

Duke Scholars

Published In

Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

DOI

Publication Date

January 1, 2017

Volume

0

Start / End Page

1101 / 1114
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Ghaffari, M., Karger, D. R., & Panigrahi, D. (2017). Random contractions and sampling for hypergraph and hedge connectivity. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (Vol. 0, pp. 1101–1114). https://doi.org/10.1137/1.9781611974782.71
Ghaffari, M., D. R. Karger, and D. Panigrahi. “Random contractions and sampling for hypergraph and hedge connectivity.” In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 0:1101–14, 2017. https://doi.org/10.1137/1.9781611974782.71.
Ghaffari M, Karger DR, Panigrahi D. Random contractions and sampling for hypergraph and hedge connectivity. In: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. 2017. p. 1101–14.
Ghaffari, M., et al. “Random contractions and sampling for hypergraph and hedge connectivity.” Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, vol. 0, 2017, pp. 1101–14. Scopus, doi:10.1137/1.9781611974782.71.
Ghaffari M, Karger DR, Panigrahi D. Random contractions and sampling for hypergraph and hedge connectivity. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. 2017. p. 1101–1114.

Published In

Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

DOI

Publication Date

January 1, 2017

Volume

0

Start / End Page

1101 / 1114