Approximating s-t minimum cuts in Õ(n2) time
We improve on random sampling techniques for approximately solving problems that involve cuts in graphs. We give a lineartime construction that transforms any graph on n vertices into anO(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(mn)-time maximum flow algorithm of Goldberg and Tarjan to find an s–tminimum cut in ~ O(n2) 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 ~ O(n2) time.