Approximating s-t minimum cuts in Õ ( n 2 ) time
András A. Benczúr, David R. Karger · 1996
We improve on random sampling techniques for approximately solving problems that involve cuts in graphs. We give a 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 Õ(mn)-time maximum flow algorithm of Goldberg and Tarjan to find an s–t minimum cut in Õ(n²) time. This corresponds to a(1+)-times minimum s–t cut in the original graph. In a similar way, we can approximate a sparsest cut in Õ(n²) time.