A Randomized Fully Polynomial Time Approximation Scheme for the All Terminal Network Reliability Problem
06 December 1999
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 disconnected due to edge failures. This problem has obvious applications in the design of communication networks. Since it is #P-complete, a great deal of research has been devoted to estimating the failure probability. In this paper, we give a fully polynomial time approximation scheme that, given any graph with specified failures probabilities, computes in time polynomial in n and 1/epsilon and estimate for the failure probability that is accurate to within a relative error of 1 +- epsilon with high probability. Some extensions are also described.