DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2026.147

Strongly Polynomial Parallel Maximum Flow Revisited

Authors: Adam Karczmarz and Paweł Pilarski

Published in: LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026)

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 [Dadush et al., 2026] runs in Õ(mn) work and Õ(m) depth. This improves upon the previously described tradeoffs between work and depth for strongly polynomial parallel maximum flow algorithms: earlier Õ(n³)-work algorithms have Õ(n²) depth [Goldberg and Tarjan, 1988; Shiloach and Vishkin, 1982], while the known Õ(m)-depth approach uses Õ(mn³) work [Orlin, 1993].

Cite as

Adam Karczmarz and Paweł Pilarski. Strongly Polynomial Parallel Maximum Flow Revisited. In 34th Annual European Symposium on Algorithms (ESA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 388, pp. 147:1-147:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{karczmarz_et_al:LIPIcs.ESA.2026.147,
  author =	{Karczmarz, Adam and Pilarski, Pawe{\l}},
  title =	{{Strongly Polynomial Parallel Maximum Flow Revisited}},
  booktitle =	{34th Annual European Symposium on Algorithms (ESA 2026)},
  pages =	{147:1--147:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-445-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{388},
  editor =	{Bille, Philip and Pettie, Seth and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.147},
  URN =		{urn:nbn:de:0030-drops-272835},
  doi =		{10.4230/LIPIcs.ESA.2026.147},
  annote =	{Keywords: maximum flow, parallel algorithm, work-depth tradeoff, strongly polynomial}
}

Search Results

Documents authored by Pilarski, Paweł

Strongly Polynomial Parallel Maximum Flow Revisited

Abstract

Cite as

Thanks for your feedback!

Could not send message