Improved bounds and algorithms for graph cuts and network reliability. Issue 1 (17th August 2017)

• Record Type: Journal Article
• Authors: Harris, David G.; Srinivasan, Aravind
• Is Part Of: Random structures & algorithms. Volume 52:Issue 1(2018)
• Page Start: 74
• Page End: 135
• Publication Date: 2017-08-17
• Subjects: contraction algorithm -- graph cuts -- graph reliability; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20724
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: 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 ) ϵ − 3 time 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 to n 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).