Random contractions and sampling for hypergraph and hedge connectivity

Conference Paper

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.

Full Text

Duke Authors

Cited Authors

  • Ghaffari, M; Karger, DR; Panigrahi, D

Published Date

  • January 1, 2017

Published In

  • Proceedings of the Annual Acm Siam Symposium on Discrete Algorithms

Volume / Issue

  • 0 /

Start / End Page

  • 1101 - 1114

International Standard Book Number 13 (ISBN-13)

  • 9781611974782

Digital Object Identifier (DOI)

  • 10.1137/1.9781611974782.71

Citation Source

  • Scopus