Tutte seminar - Nick Harvey

Graph Sparsifiers

Abstract:

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.