Title: Graph Sparsification by Edge-Connectivity and Random Spanning Trees

Abstract:
A "sparsifier" of a graph is a weighted subgraph for which
every cut has approximately the same value as the original graph, up
to a factor of (1 +/- eps). Sparsifiers were first studied by Benczur
& Karger (1996), with improvements by Spielman & Teng (2004), and
others. They have wide-ranging applications, including fast network
flow algorithms, fast linear system solvers, etc. It is known that
sparsifiers with O(n/eps^2) edges exist, and they can be computed in
time poly(n,eps).

We describe two new approaches to constructing sparsifiers. 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. The second approach samples uniformly random
spanning trees. Both of our approaches produce sparsifiers with
O(n log^2(n) / eps^2) edges. Our proofs are based on extensions of the
Karger-Stein contraction algorithm which allow it to compute minimum
"Steiner" cuts.