A randomized fully polynomial time approximation scheme for the all-terminal network reliability problem

The classic all-terminal network reliability problem posits a graph, each o f whose edges fails independently with some given probability. The goal is to determine the probability that the network becomes disconnected due to e dge failures. This problem has obvious applications in the design of commun ication networks. Since the problem is #P-complete and thus believed hard t o solve exactly, a great deal of research has been devoted to estimating th e failure probability. In this paper, we give a fully polynomial randomized approximation scheme that, given any n-vertex graph with specified failure probabilities, computes in time polynomial in n and 1/epsilon an estimate for the failure probability that is accurate to within a relative error of 1 +/- epsilon with high probability. We also give a deterministic polynomia l approximation scheme for the case of small failure probabilities. Some ex tensions to evaluating probabilities of k-connectivity, strong connectivity in directed Eulerian graphs and r-way disconnection, and to evaluating the Tutte polynomial are also described.