  We give the first O(m polylog(n)) time algorithms for approximating maximum
flows in undirected graphs and constructing polylog(n) -quality
cut-approximating hierarchical tree decompositions. Our algorithm invokes
existing algorithms for these two problems recursively while gradually
incorporating size reductions. These size reductions are in turn obtained via
ultra-sparsifiers, which are key tools in solvers for symmetric diagonally
dominant (SDD) linear systems.
