# An Improved Quality Hierarchical Congestion Approximator in Near-Linear Time

arXiv: https://arxiv.org/abs/2511.03716 · HTML: https://mlsanity.com/paper/2511.03716/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Nov 2025.

## Built on by (most cited first, 1 of 1)

- [An Approximation Algorithm for Graph Label Selection](https://mlsanity.com/paper/2605.18623/) (2026)

## Abstract (arXiv)

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 single-commodity 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(log1.5n log log n). Among near-linear time algorithms, the best previous result achieves approximation quality O(log4 n). We improve upon the latter result by giving the first near-linear time algorithm for computing an HCA with approximation quality O(log2 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(log9n) approximation quality. We also present a lower bound of Omega(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.