Premium
Improved bounds and algorithms for graph cuts and network reliability
Author(s) -
Harris David G.,
Srinivasan Aravind
Publication year - 2018
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20724
Subject(s) - graph , mathematical proof , algorithm , computer science , key (lock) , upper and lower bounds , mathematics , discrete mathematics , theoretical computer science , mathematical analysis , geometry , computer security
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).