An Improved Quality Hierarchical Congestion Approximator in Near-Linear Time

A congestion approximator for a graph is a compact data structure that approximately predicts the edge congestion required to route any set of flow demands in a network. A congestion approximator is hierarchical if it consists of a laminar family of cuts in the graph. There is a tradeoff between the running time for computing a congestion approximator and its approximation quality. Currently, for an n-node graph there exists a polynomial time algorithm that achieves a O(log1.5n log log n) approximation and a near-linear time algorithm that achieves w.h.p. a O(log⁴ n) approximation. In this paper we give the first near-linear time algorithm, that achieves w.h.p. a O(log² n log log n) approximation, using an hierarchical congestion approximator with O(n log n) cuts. Based on a reduction from oblivious routing, we also present a lower bound of Ω(log n) for the approximation quality of hierarchical congestion approximators. Our algorithm can also be implemented in the parallel setting achieving the same approximation quality, polylogarithmic span and near-linear work. This improves upon the best prior parallel algorithm, which has a O(log⁹n) approximation. Crucial for achieving a near linear running time is a new partitioning routine that, unlike previous such routines, manages to avoid recursing on large subgraphs. To achieve the improved approximation quality, we introduce the new concept of border routability of a cut and give an improved sparsest cut oracle for general vertex weights.