Faster (and Still Pretty Simple) Unbiased Estimators for Network (Un)reliability

摘要

Consider the problem of estimating the (un)reliability of an n-vertex graph when edges fail with probability p. We show that the Recursive Contraction Algorithms for minimum cuts, essentially unchanged and running in n^2+o(1) time, yields an unbiased estimator of constant relative variance (and thus an FPRAS with the same time bound) whenever p^c <; n^-2. For larger p, we show that reliable graphs-where failures are rare so seemingly harder to find-effectively act like small graphs and can thus be analyzed quickly. Combining these ideas gives us an unbiased estimator for unreliability running in Õ(n^2.78) time, an improvement on the previous Õ(n³) time bound.