Implementing a fully polynomial time approximation scheme for all terminal network reliability

The classic all-terminal network reliability problem posits a graph, each of whose edges fails independently with some given probability. The goal is to determine the probability that the network becomes discon-nected due to edge failures. This problem has obvious applications in the design of communication networks. Since the problem is]P-complete and thus believed hard to solve exactly, a great deal of research has been de-voted to estimating the failure probability. In this paper, we give a fully polynomial randomized approximation scheme that, given any n-vertex graph with specied failure probabilities, computes in time polynomial in n and 1= an estimate for the failure probability that is accurate to within a relative error of 1 with high probability. We also give a deterministic polynomial approximation scheme for the case of small failure probabili-ties. Some extensions 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