KIT | KIT-Bibliothek | Impressum | Datenschutz

Parallel Minimum Cost Flow in Near-Linear Work and Square Root Depth for Dense Instances

van den Brand, Jan; Gholizadeh, Hossein 1; Jiang, Yonggang; de Vos, Tjin
1 Karlsruher Institut für Technologie (KIT)

Abstract:

For n-vertex m-edge graphs with integer polynomially-bounded costs and capacities, we provide a randomized parallel algorithm for the minimum cost flow problem with Õ(m + n1.5) work and Õ(√n) depth1. On moderately dense graphs (m > n1.5), our algorithm is the first one to achieve both near-linear work and sub-linear depth. Previous algorithms are either achieving almost optimal work but are highly sequential [CKL+22], or achieving sub-linear depth but use super-linear work [LS14, OS93]. Our result also leads to improvements for the special cases of max flow, bipartite maximum matching, shortest paths, and reachability. Notably, the previous algorithms achieving near-linear work for shortest paths and reachability all have depth no(1). √n [JLS19, FHL+25].
Our algorithm consists of a parallel implementation of [BLL+21]. One important building block is a parallel batch-dynamic expander decomposition, which we show how to obtain from the recent parallel expander decomposition of [CMGS25].


Verlagsausgabe §
DOI: 10.5445/IR/1000186211
Veröffentlicht am 28.10.2025
Cover der Publikation
Zugehörige Institution(en) am KIT Karlsruher Institut für Technologie (KIT)
Publikationstyp Proceedingsbeitrag
Publikationsdatum 16.07.2025
Sprache Englisch
Identifikator ISBN: 979-84-00-71258-6
KITopen-ID: 1000186211
Erschienen in Proceedings of the 37th ACM Symposium on Parallelism in Algorithms and Architectures
Veranstaltung 37th ACM Symposium on Parallelismin Algorithms and Architectures (2025), Portland, OR, USA, 28.07.2025 – 01.08.2025
Verlag Association for Computing Machinery (ACM)
Seiten 1–16
Nachgewiesen in Dimensions
Web of Science
Scopus
OpenAlex
KIT – Die Universität in der Helmholtz-Gemeinschaft
KITopen Landing Page