# Faster High Accuracy Multi-Commodity Flow from Single-Commodity Techniques

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Apr 2023.

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

- [Hierarchical Forecast Reconciliation on Networks: A Network Flow Optimization Formulation](https://mlsanity.com/paper/2505.03955/) (2025)

## Abstract (arXiv)

Since the development of efficient linear program solvers in the 80s, all major improvements for solving multi-commodity flows to high accuracy came from improvements to general linear program solvers. This differs from the single commodity problem (e.g.~maximum flow) where all recent improvements also rely on graph specific techniques such as graph decompositions or the Laplacian paradigm (see e.g.~[CMSV17,KLS20,BLL+21,CKL+22]). This phenomenon sparked research to understand why these graph techniques are unlikely to help for multi-commodity flow. [Kyng, Zhang'20] reduced solving multi-commodity Laplacians to general linear systems and [Ding, Kyng, Zhang'22] showed that general linear programs can be reduced to 2-commodity flow. However, the reductions create sparse graph instances, so improvement to multi-commodity flows on denser graphs might exist. We show that one can indeed speed up multi-commodity flow algorithms on non-sparse graphs using graph techniques from single-commodity flow algorithms. This is the first improvement to high accuracy multi-commodity flow algorithms that does not just stem from improvements to general linear program solvers. In particular, using graph data structures from recent min-cost flow algorithm by [BLL+21] based on the celebrated expander decomposition framework, we show that 2-commodity flow on an n-vertex m-edge graph can be solved in tildeO(√mnω-1/2) time for current bounds on fast matrix multiplication ω ≈ 2.373, improving upon the previous fastest algorithms with tildeO(mω) [CLS19] and tildeO(√mn2) [KV96] time complexity. For general k commodities, our algorithm runs in tildeO(k2.5√mnω-1/2) time.