A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability

We give a fully polynomial-time randomized approximation scheme (FPRAS) for the all-terminal network reliability problem, which is to determine the probability that in an undirected graph, assuming each edge fails independently, the remainder of the graph is still connected. Our main contribution is to confirm a conjecture by Gorodezky and Pak [ Random Structures Algorithms, 44 (2014), pp. 201--223] that the expected running time of the “cluster-popping” algorithm in bidirected graphs is bounded by a polynomial in the size of the input.