  Karger (SIAM Journal on Computing, 1999) developed the first fully-polynomial
approximation scheme to estimate the probability that a graph $G$ becomes
disconnected, given that its edges are removed independently with probability
$p$. This algorithm runs in $n^{5+o(1)} \epsilon^{-3}$ time to obtain an
estimate within relative error $\epsilon$.
  We improve this run-time through algorithmic and graph-theoretic advances.
First, there is a certain key sub-problem encountered by Karger, for which a
generic estimation procedure is employed, we show that this has a special
structure for which a much more efficient algorithm can be used. Second, we
show better bounds on the number of edge cuts which are likely to fail. Here,
Karger's analysis uses a variety of bounds for various graph parameters, we
show that these bounds cannot be simultaneously tight. We describe a new graph
parameter, which simultaneously influences all the bounds used by Karger, and
obtain much tighter estimates of the cut structure of $G$. These techniques
allow us to improve the runtime to $n^{3+o(1)} \epsilon^{-2}$, our results also
rigorously prove certain experimental observations of Karger & Tai (Proc.
ACM-SIAM Symposium on Discrete Algorithms, 1997). Our rigorous proofs are
motivated by certain non-rigorous differential-equation approximations which,
however, provably track the worst-case trajectories of the relevant parameters.
  A key driver of Karger's approach (and other cut-related results) is a bound
on the number of small cuts: we improve these estimates when the min-cut size
is "small" and odd, augmenting, in part, a result of Bixby (Bulletin of the
AMS, 1974).
