Approximate Undirected Maximum Flows in O(m polylog(n)) Time

Understand

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.