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

Leave a Reply

Your email address will not be published.

156,142 Spam Comments Blocked so far by Spam Free Wordpress

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>