A Fast and Simple Unbiased Estimator for Network (Un)reliability
Author:
- David R. KargerDKDavid R. Karger
- 15 December 2016
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 44 (02725428) , 635-644
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 networksKeywords
This publication has 15 references indexed in Scilit:
- Improved bounds and algorithms for graph cuts and network reliability2013
- Minimum cuts in near-linear timeJournal of the ACM, 2000
- A Randomized Fully Polynomial Time Approximation Scheme for the All-Terminal Network Reliability ProblemSIAM Journal on Computing, 1999
- A new approach to the minimum cut problemJournal of the ACM, 1996
- A very simple algorithm for estimating the number of k‐colorings of a low‐degree graphRandom Structures & Algorithms, 1995
- A linear-time algorithm for finding a sparsek-connected spanning subgraph of ak-connected graphAlgorithmica, 1992
- Computing Edge-Connectivity in Multigraphs and Capacitated GraphsSIAM Journal on Discrete Mathematics, 1992
- Probabilistic recurrence relations1991
- The Complexity of Counting Cuts and of Computing the Probability that a Graph is ConnectedSIAM Journal on Computing, 1983
- The Complexity of Enumeration and Reliability ProblemsSIAM Journal on Computing, 1979