We present a fully polynomial randomized approximation scheme (FPRAS) for all‑terminal unreliability in explicitly represented undirected hypergraphs of arbitrary rank. The algorithm allows a distinct rational failure probability for each hyperedge and estimates the probability that independent hyperedge failures disconnect the hypergraph.
The key idea is to turn the representative‑survival bound of Cen, Li, and Panigrahi into an importance sampler. During contraction we randomly select one representative pair, protect it, correct the path likelihood, and finally divide by the number of surviving pairs. The resulting unbiased estimator has a relative second moment bounded by $\binom n2$, even when unreliability is exponentially small.
A minimum‑cut normalization makes the estimator implementable with polynomially bounded precision. After normalization the residual likelihood becomes a survival probability in an auxiliary absorbing process, which can be discretized rationally using a fixed random‑bit budget. Logarithmic rate rounding and an exact weighted minimum cut extend the construction to unequal rational failure probabilities.
The worst‑case running time and random‑bit usage are polynomial in the input length, the inverse relative error, and $\log(1/\delta)$ for confidence $1-\delta$.
Review: This work lifts hypergraph unreliability approximation from quasi‑polynomial to true polynomial time, offering a practical randomized tool for reliability analysis in complex systems.