|Affiliation:||University of Waterloo|
|Room:||Mathematics & Computer Building (MC) 5158|
Can a dense graph be approximated by a sparse graph? Surprisingly, yes. A "sparsifier" of a graph is a weighted subgraph that approximates the weight of every cut, up to a factor (1+eps). Benczur and Karger showed that, for any graph on n nodes, sparsifiers with only O(n log n / eps^2) edges exist, and furthermore they can be constructed efficiently.
Sparsifiers have numerous applications, including fast algorithms for network flow and cut problems. Related constructions play a key role in Spielman and Teng's remarkable algorithm for solving diagonally dominant linear systems in nearly linear time.
We give a new approach to constructing sparsifiers, which simplifies and clarifies the original work of Benczur and Karger. Our algorithm independently samples every 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 resulting sparsifiers have O(n log^2 n / eps^2) edges. Our proofs are based on extensions of Karger's contraction algorithm for computing minimum cuts in a graph.
Joint work with Isaac Fung.
200 University Avenue West
Waterloo, ON N2L 3G1