Improved bounds and algorithms for graph cuts and network reliability

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 inn 5 + o ( 1 )ϵ − 3time to obtain an estimate within relative error ϵ . 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 ton 3 + o ( 1 )ϵ − 2; our results also rigorously prove certain experimental observations of Karger and 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).