We present two new approaches to constructing graph sparsifiers -- weighted subgraphs for which every cut has the same value as the original graph, up to a factor of (1+/-epsilon). The first approach independently samples each edge uv with probability inversely proportional to the edge-connectivity between u and v. The fact that this approach produces a sparsifier resolves an open question of Benczur and Karger. Concurrent work of Hariharan and Panigrahi (2010) also resolves this question. The second approach samples uniformly random spanning trees. Both of our approaches produce sparsifiers with O(n log^2(n) / epsilon^2) edges. Our proofs are based on extensions of Karger's contraction algorithm which allow it to compute minimum "Steiner cuts".
Copyright. All Rights Reserved.