Can any graph be approximated by a sparse graph? Surprisingly, the answer is
"yes", under several notions of approximation.
In 1996, Benczur and Karger proved that, for any graph on n vertices, there is
an efficient algorithm to decrease its number of edges to only O(n log n /
epsilon2) while preserving all cuts of the graph to within a factor 1+epsilon.
In 2008, Batson, Spielman and Srivastava strengthened this result, showing that
there is an efficient algorithm to decrease its number of edges to only O( n /
epsilon2 ) while preserving all cuts and all eigenvalues to within a factor
I find these results to be very interesting because (1) the statements
themselves are surprising, (2) the proofs are glorious, and (3) there are
numerous applications. For example, these results are now heavily used in
algorithms for cut and flow problems, and they play a key role in the recent
nearly-linear-time algorithms for solving symmetric, diagonally dominant linear