Improved bounds and algorithms for graph cuts and network reliability
Lists
Only you see this
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 O(n5+o(1)∊−3) time to obtain an estimate within relative error ∊. We improve this runtime in two key ways, one algorithmic and one graph-theoretic. From an algorithmic point of view, there is a certain key sub-problem encountered by Karger, for which a generic estimation procedure is employed. We show that this sub-problem has a special structure for which a much more efficient algorithm can be used. From a graph-theoretic point of view, we show better bounds on the number of edge cuts which are likely to fail. Karger's analysis depends on 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 use it to obtain much tighter estimates of the behavior of the cuts of G. These techniques allow us to improve the runtime to n3+o(1)∊−2, which is essentially best-possible for the meta-approach proposed by Karger; our results also rigorously prove certain experimental observations of Karger & Tai (Proc. ACM-SIAM Symposium on Discrete Algorithms, 1997). A key driver of Karger's approach (and other cut-related results) is his earlier bound on the number of small cuts: we also show how to improve this when the min-cut size is “small” and odd, augmenting, in part, a result of Bixby (Bull. AMS, 1974).
BibTeX
@inproceedings{harris2014improved,
author = {David G. Harris and Aravind Srinivasan},
title = {{Improved bounds and algorithms for graph cuts and network reliability}},
booktitle = {Random Struct. Algorithms},
year = {2014},
doi = {10.1137/1.9781611973402.19},
}Loading related content...