{"ID":2851133,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.20456","arxiv_id":"2510.20456","title":"Parallel $(1+ε)$-Approximate Multi-Commodity Mincost Flow in Almost Optimal Depth and Work","abstract":"We present a parallel algorithm for computing $(1+ε)$-approximate mincost flow on an undirected graph with $m$ edges, where capacities and costs are assigned to both edges and vertices. Our algorithm achieves $\\hat{O}(m)$ work and $\\hat{O}(1)$ depth when $ε\u003e 1/\\mathrm{polylog}(m)$, making both the work and depth almost optimal, up to a subpolynomial factor. Previous algorithms with $\\hat{O}(m)$ work required $Ω(m)$ depth, even for special cases of mincost flow with only edge capacities or max flow with vertex capacities. Our result generalizes prior almost-optimal parallel $(1+ε)$-approximation algorithms for these special cases, including shortest paths [Li, STOC'20] [Andoni, Stein, Zhong, STOC'20] [Rozhen, Haeupler, Marinsson, Grunau, Zuzic, STOC'23] and max flow with only edge capacities [Agarwal, Khanna, Li, Patil, Wang, White, Zhong, SODA'24]. Our key technical contribution is the first construction of length-constrained flow shortcuts with $(1+ε)$ length slack, $\\hat{O}(1)$ congestion slack, and $\\hat{O}(1)$ step bound. This provides a strict generalization of the influential concept of $(\\hat{O}(1),ε)$-hopsets [Cohen, JACM'00], allowing for additional control over congestion. Previous length-constrained flow shortcuts [Haeupler, Hershkowitz, Li, Roeyskoe, Saranurak, STOC'24] incur a large constant in the length slack, which would lead to a large approximation factor. To enable our flow algorithms to work under vertex capacities, we also develop a close-to-linear time algorithm for computing length-constrained vertex expander decomposition. Building on Cohen's idea of path-count flows [Cohen, SICOMP'95], we further extend our algorithm to solve $(1+ε)$-approximate $k$-commodity mincost flow problems with almost-optimal $\\hat{O}(mk)$ work and $\\hat{O}(1)$ depth, independent of the number of commodities $k$.","short_abstract":"We present a parallel algorithm for computing $(1+ε)$-approximate mincost flow on an undirected graph with $m$ edges, where capacities and costs are assigned to both edges and vertices. Our algorithm achieves $\\hat{O}(m)$ work and $\\hat{O}(1)$ depth when $ε\u003e 1/\\mathrm{polylog}(m)$, making both the work and depth almost...","url_abs":"https://arxiv.org/abs/2510.20456","url_pdf":"https://arxiv.org/pdf/2510.20456v1","authors":"[\"Bernhard Haeupler\",\"Yonggang Jiang\",\"Yaowei Long\",\"Thatchaphol Saranurak\",\"Shengzhe Wang\"]","published":"2025-10-23T11:46:51Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}