# Strongly Polynomial Parallel Maximum Flow Revisited

Preprint · Adam Karczmarz, Paweł Pilarski

- Archive id: arxiv:2608.12171
- Published: 2026-08-12
- arXiv: https://arxiv.org/abs/2608.12171
- Source URL: https://arxiv.org/abs/2608.12171
- PDF: https://arxiv.org/pdf/2608.12171
- Provenance: arxiv

## Abstract

We study the maximum flow problem in directed networks with real capacities in the parallel setting. For a network with $n$ vertices and $m$ arcs, we show that a randomized parallel implementation of a variant of the strongly polynomial max-flow algorithm of Dadush, Orlin, Sidford, and Végh \[SODA 2026\] runs in $\\tilde{O}(mn)$ work and $\\tilde{O}(m)$ depth. This improves upon the previously described tradeoffs between work and depth for strongly polynomial parallel maximum flow algorithms: earlier $\\tilde{O}(n^3)$-work algorithms have $\\tilde{O}(n^2)$ depth \[Shiloach and Vishkin, J. Algorithms 1982; Goldberg and Tarjan, J. ACM 1988\], while the known $\\tilde{O}(m)$-depth approach uses $\\tilde{O}(mn^3)$ work \[Orlin, Oper. Res. 1993\].

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.