|
Abstract : |
We explore random sampling as a tool for solving undirected graph problems. We show that the sparse graph, or skeleton, which arises when we randomly sample a graph's edges will accurately approximate the value of all cuts in the original graph. This makes sampling effective for problems involving cuts in graphs. We apply these tools in fast randomized (Monte Carlo and Las Vegas) algorithms for approximating and exactly finding cuts and flows in an unweighted, undirected graph. We also give weighted-graph versions of these algorithms which use a form of scaling to achieve a sublinear dependence on the maximum edge weight. Our methods also reduce the work done by some parallel cut algorithms. Our sampling theorems also yield faster algorithms for several other cut based problems, including approximating the best balanced cut of a graph, finding a k-connected orientation of a 2k-connected graph, and finding integral multicommodity flows in graphs with a great deal of excess capacity. Our sampling theorems apply even when the sampling probabilities are different for different edges. Using this fact, we show how to use randomized rounding in (1 + o(1))-approximation algorithm for the NP-complete minimum k-connected subgraph problem when k AE log n; the best previous approximation factor was 2. Our techniques generalize to many other survivable network design problems., |
