Improved bounds and algorithms for graph cuts and network reliability

David Harris and Aravind Srinivasan

Abstract: Karger 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. We improve this runtime in two key ways, one algorithmic and one graph-theoretic. From an algorithmicpoint of view, there is a certain key sub-problem encountered by Karger, for which a generic estimation procedureis 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.

Guest: David Harris
Host: Yvonne-Anne Pignolet