Approximating <i>s-t</i> minimum cuts in <i>Õ</i>(<i>n</i>²) time 论文

摘要

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.