Abstract
We show a closer algorithmic connection between constructing cut-approximating hierarchical tree decompositions and computing approximate maximum flows in undirected graphs. Our approach is based on invoking known algorithms for these problems recursively, while reducing problem sizes using ultra-sparsifiers. This leads to the first O(m polylog(n)) time algorithms for both problems.