An Improved Quality Hierarchical Congestion Approximator in Near-Linear Time

A single-commodity congestion approximator for a graph is a compact data structure that approximately predicts the edge congestion required to route any set of singlecommodity flow demands in a network. A hierarchical congestion approximator (HCA) consists of a laminar family of cuts in the graph and has numerous applications in approximating cut and flow problems in graphs, designing efficient routing schemes, and managing distributed networks.

There is a tradeoff between the running time for computing an HCA and its approximation quality. The best polynomial-time construction in an n-node graph gives an HCA with approximation quality O(log 1.5 n log log n). Among near-linear time algorithms, the best previous result achieves approximation quality O(log 4 n). We improve upon the latter result by giving the first near-linear time algorithm for computing an HCA with approximation quality O(log 2 n log log n). Additionally, our algorithm can be implemented in the parallel setting with polylogarithmic span and near-linear work, achieving the same approximation quality. This improves upon the best previous such algorithm, which has an O(log 9 n) approximation quality. We also present a lower bound of Ω(log n) for the approximation guarantee of hierarchical congestion approximators.

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 provide an improved sparsest cut oracle for general vertex weights.