Random sampling in graph optimization problems
David R. Karger · 1995
The representative random sample is a central concept of statistics. It is often possible to gather a great deal of information about a large population by examining a small sample randomly drawn from it. This approach has obvious advantages in reducing the investigator's work, both in gathering and in analyzing the data. We apply the concept of a representative sample to combinatorial optimization. Our general technique is to generate small random representative subproblems and solve them in lieu of the original ones, producing approximately correct answers which may then be refined to correct ones at little additional cost. Our focus is optimization problems on undirected graphs. Highlights of our results include: (1) The first (randomized) linear time minimum spanning tree algorithm; (2) A (randomized) minimum cut algorithm with running time roughly $O(n\sp2)$ as compared to previous roughly $O(n\sp3)$ time bounds, as well as the first algorithm for finding all approximately minimal cuts and multiway cuts; (3) An efficient parallelization of the minimum cut algorithm, providing the first parallel $({\cal RNC})$ algorithm for minimum cuts, together with a derandomization proving that minimum cuts can be found deterministically in parallel $({\cal NC})$; (4) Tight bounds on the all terminal reliability (probability of remaining connected) of a network suffering random edge failures. (5) Linear time sequential and linear processor parallel algorithms for finding approximately minimum cuts; (6) Faster algorithms for approximating and exactly finding s-t minimum cuts and maximum flows; (7) For the ${\cal NP}$-complete problem of designing minimum cost networks satisfying specified connectivity requirements (a generalization of the minimum spanning tree problem), significantly improved polynomial-time approximation bounds (from $O(\log n)$ to 1 + o(1) for many such problems); (8) For coloring 3-colorable graphs, improvements in the polynomial time approximation bounds from O($n\sp{3/8})$ to O($n\sp{1/4}),$ and even better bounds for sparse graphs; (9) An analysis of random sampling in matroids.