Random sampling in cut, flow, and network design problems

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 graphs 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. ...