DROPS

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2026.136

Back in the Saddle: Toward Parallel Approximate Minimum-Cost Flow

Authors: Rasmus Kyng and Aurelio L. Sulser

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract

We present the first polylog-depth, nearly-linear-work parallel algorithm that achieves a (1+ε)-bicriteria approximation guarantee for undirected minimum-cost flow on expanders. Fix an undirected graph G = (V,E) with unit capacities, unit lengths, and conductance ϕ. For any feasible demand vector d and any ε ∈ (0,1) we compute, in Õ(|E|/(εϕ)) work and Õ(1/(εϕ)) depth, a flow f that routes d exactly while satisfying ‖f‖_∞ ≤ 1+ε and ‖f‖_1 ≤ (1+ε)min_{Bg = d, ‖g‖_∞ ≤ 1}}‖g‖_1. This bicriteria guarantee simultaneously controls congestion and total cost, strengthens the previously studied notion of throughput error, and matches the best known ε-dependence for parallel maximum flow/transshipment on general graphs. Our main contribution is a new saddle-point optimization method for mixed 𝓁_∞-𝓁_1 optimization. Concretely, we (i) formulate a two-term regression capturing minimum-cost flow as a saddle-point problem that couples 𝓁_∞ and 𝓁_1 terms, (ii) construct a small-magnitude area-convex regularizer tailored to the resulting primal–dual domain (building on Sherman’s area-convexity framework [Sherman, 2017]), and (iii) implement efficient δ-approximate maximization/minimization oracles so that Sherman’s extragradient iteration yields low iteration-count convergence. Beyond the concrete expander result, our mixed 𝓁_∞-𝓁_1 optimization toolkit appears broadly applicable and suggests a promising route toward Õ(m/ε) work and Õ(1/ε) depth algorithms for approximate undirected minimum-cost flow on general graphs.

Cite as

Rasmus Kyng and Aurelio L. Sulser. Back in the Saddle: Toward Parallel Approximate Minimum-Cost Flow. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 136:1-136:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{kyng_et_al:LIPIcs.ICALP.2026.136,
  author =	{Kyng, Rasmus and Sulser, Aurelio L.},
  title =	{{Back in the Saddle: Toward Parallel Approximate Minimum-Cost Flow}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{136:1--136:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.136},
  URN =		{urn:nbn:de:0030-drops-265255},
  doi =		{10.4230/LIPIcs.ICALP.2026.136},
  annote =	{Keywords: Approximate Min-Cost-Flow, Parallel, Area-Convexity, Expanders}
}

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2025.132

Near-Optimal Algorithm for Directed Expander Decompositions

Authors: Aurelio L. Sulser and Maximilian Probst Gutenberg

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract

In this work, we present the first algorithm to compute expander decompositions in an m-edge directed graph with near-optimal time Õ(m). Further, our algorithm can maintain such a decomposition in a dynamic graph and again obtains near-optimal update times. Our result improves over previous algorithms [Bernstein et al., 2020; Hua et al., 2023] that only obtained algorithms optimal up to subpolynomial factors. In order to obtain our new algorithm, we present a new push-pull-relabel flow framework that generalizes the classic push-relabel flow algorithm [Goldberg and Tarjan, 1988] which was later dynamized for computing expander decompositions in undirected graphs [Henzinger et al., 2020; Saranurak and Wang, 2019]. We then show that the flow problems formulated in recent work [Hua et al., 2023] to decompose directed graphs can be solved much more efficiently in the push-pull-relabel flow framework. Recently, our algorithm has already been employed to obtain the currently fastest algorithm to compute min-cost flows [Van Den Brand et al., 2024]. We further believe that our algorithm can be used to speed-up and simplify recent breakthroughs in combinatorial graph algorithms towards fast maximum flow algorithms [Chuzhoy and Khanna, 2024; Chuzhoy and Khanna, 2024; Bernstein et al., 2024].

Cite as

Aurelio L. Sulser and Maximilian Probst Gutenberg. Near-Optimal Algorithm for Directed Expander Decompositions. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 132:1-132:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{sulser_et_al:LIPIcs.ICALP.2025.132,
  author =	{Sulser, Aurelio L. and Gutenberg, Maximilian Probst},
  title =	{{Near-Optimal Algorithm for Directed Expander Decompositions}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{132:1--132:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.132},
  URN =		{urn:nbn:de:0030-drops-235096},
  doi =		{10.4230/LIPIcs.ICALP.2025.132},
  annote =	{Keywords: Directed Expander Decomposition, Push-Pull-Relabel Algorithm}
}

Search Results

Documents authored by Sulser, Aurelio L.

Back in the Saddle: Toward Parallel Approximate Minimum-Cost Flow

Abstract

Cite as

Near-Optimal Algorithm for Directed Expander Decompositions

Abstract

Cite as

Thanks for your feedback!

Could not send message