Title: A polynomial-time approximation algorithm for all-terminal network reliability,
Abstract: 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 a undirected graph, assuming each edge fails
independently, the remaining graph is still connected. Our main contribution is
to confirm a conjecture by Gorodezky and Pak (Random Struct. Algorithms, 2014),
that the expected running time of the "cluster-popping" algorithm in
bi-directed graphs is bounded by a polynomial in the size of the input.