Hypergraph Unreliability in Quasi-Polynomial Time

The hypergraph unreliability problem asks for the probability that a hypergraph gets disconnected when every hyperedge fails independently with a given probability. For graphs, the unreliability problem has been studied over many decades, and multiple fully polynomial-time approximation schemes are known starting with the work of Karger (STOC 1995). In contrast, prior to this work, no non-trivial result was known for hypergraphs (of arbitrary rank).

In this paper, we give quasi-polynomial time approximation schemes for the hypergraph unreliability problem. For any fixed ε ∈ (0, 1), we first give a (1 + ε)-approximation algorithm that runs in m O(log n) time on an m-hyperedge, n-vertex hypergraph. Then, we improve the running time to m • n O(log 2 n) with an additional exponentially small additive term in the approximation.