Congestion-Approximators from the Bottom Up
Jason Li, Satish Rao, Di Wang · Society for Industrial and Applied Mathematics eBooks · 2025
We develop a novel algorithm to construct a congestion-approximator with polylogarithmic quality on a capacitated, undirected graph in nearly-linear time. Our approach is the first bottom-up hierarchical construction, in contrast to previous top-down approaches including that of Racke, Shah, and Taubig (SODA 2014), the only other construction achieving polylogarithmic quality that is implementable in nearly-linear time (Peng, SODA 2016). Similar to Racke, Shah, and Taubig, our construction at each hierarchical level requires calls to an approximate max-flow/min-cut subroutine. However, the main advantage to our bottom- up approach is that these max-flow calls can be implemented directly without recursion. More precisely, the previously computed levels of the hierarchy can be converted into a pseudo-congestion-approximator, which then translates to a max-flow algorithm that is sufficient for the particular max-flow calls used in the construction of the next hierarchical level. As a result, we obtain the first non-recursive algorithms for congestion-approximator and approximate max-flow that run in nearly-linear time, a conceptual improvement to the aforementioned algorithms that recursively alternate between the two problems.