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 mO(logn) time on an m-hyperedge, n-vertex hypergraph. Then, we improve the running time to m· nO(log2 n) with an additional exponentially small additive term in the approximation.
