Abstract
The following is an unbiased estimator for the disconnectionprobability of an n-vertex graph with min-cut c whenevery edge fails independently with probability p: (i) contractevery edge independently with probability 1n2=c, (ii) compute(by brute force) the disconnection probability of the resulting tinygraph if each edge fails with probability n2=cp. We give a short,simple, self-contained proof that the estimator can be computedin linear time and has relative variance O(n2). Combining thesetwo facts with a standard sparsification argument yields anO(n3 log n)-time algorithm for estimating the (un)reliability ofa network. We also show how the technique can be used tocreate unbiased samples of disconnected networks

This publication has 15 references indexed in Scilit: