  We improve on random sampling techniques for approximately solving problems
that involve cuts and flows in graphs. We give a near-linear-time construction
that transforms any graph on n vertices into an O(n\log n)-edge graph on the
same vertices whose cuts have approximately the same value as the original
graph's. In this new graph, for example, we can run the O(m^{3/2})-time maximum
flow algorithm of Goldberg and Rao to find an s--t minimum cut in O(n^{3/2})
time. This corresponds to a (1+epsilon)-times minimum s--t cut in the original
graph. In a similar way, we can approximate a sparsest cut to within O(log n)
in O(n^2) time using a previous O(mn)-time algorithm. A related approach leads
to a randomized divide and conquer algorithm producing an approximately maximum
flow in O(m sqrt{n}) time.
