Dr. Karger, A randomized fully polynomial time approximation scheme for the all-terminal network reliability problem, SIAM REV, 43(3), 2001, pp. 499-522
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
fur 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.
This version of the paper corrects several errata that appeared in the prev
ious journal publication.