A General Framework for Graph Sparsification
Feb 29, 2012

In this talk, I will present a general framework for constructing cut sparsifiers in undirected graphs, and use it to simplify, unify and improve upon previous sparsification results. As simple instantiations of this framework, we show thatsparsifiers can be constructed by sampling edges according to their strength (a result of Bencz\'ur and Karger), effective resistance (a result of Spielman and Srivastava), edge connectivity (this resolves the main open question posed by Bencz\'ur and Karger) and Nagamochi-Ibaraki indices (this yields an elementary sparsification algorithm). In addition, we develop techniques that give the first (strictly) linear-time sparsification algorithm for unweighted graphs. Our algorithm produces sparsifiers containing O(n log n) edges in expectation; the only known construction of sparsifiers with fewer edges is by a substantially slower algorithm running in O(n^3 m) time. A key component of our results that might be of independent interest is a natural generalization of a seminal cut counting theorem due to Karger.

This work was done in collaboration with Ramesh Hariharan. Some of these results were also obtained by Isaac Fung and Nick Harvey in independent concurrent work.