|
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.
|