![Algorithmic Spectral Graph Theory_hi-res logo](/sites/default/files/styles/workshop_banner_sm_1x/public/2023-01/Algorithmic%20Spectral%20Graph%20Theory_hi-res.jpg?h=bc58dfd7&itok=8NAdfoPF)
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.