Deterministic almost-linear time for general matching and network flow
Version 1 / Nov 19, 2026 / CC BY 4.0
Abstract
We give deterministic almost-linear-time algorithms for maximum-cardinality matching in general graphs and integral minimum-cost flow. With , both run in time for polynomially bounded integer flow data. Their circulation oracle charges every traversal of a returned walk. A clipped logarithmic potential handles flow thresholds under improving updates and maintains strong components under arc insertions. For subgraphs with degree bounds, two matching computations encode a factor of every feasible size. The underlying exchange argument also gives integral cardinality slices for capacitated factors and is compatible with sharp local rounding.
Provenance statement
References
- A. Abboud, R. Kyng, J. Li, D. Panigrahi, M. Probst Gutenberg, T. Saranurak, Weixuan Yuan and Wuwei Yuan. Deterministic almost-linear-time Gomory--Hu trees (https://arxiv.org/abs/2507.20354). arXiv:2507.20354, 2025.arXiv
- S. Alstrup, J. Holm, K. de Lichtenberg and M. Thorup. Maintaining information in fully dynamic trees with top trees (https://arxiv.org/abs/cs/0310065). ACM Transactions on Algorithms 1 (2005), 243--264.link
- V. E. Beneš. Optimal rearrangeable multistage connecting networks (https://doi.org/10.1002/j.1538-7305.1964.tb04103.x). Bell System Technical Journal 43 (1964), 1641--1656.DOI
- J. van den Brand, L. Chen, R. Kyng, Y. P. Liu, R. Peng, M. Probst Gutenberg, S. Sachdeva and A. Sidford. A deterministic almost-linear time algorithm for minimum-cost flow (https://arxiv.org/abs/2309.16629). FOCS (2023), 503--514 (https://doi.org/10.1109/FOCS57990.2023.00037).DOI
- L. Chen, R. Kyng, Y. P. Liu, R. Peng, M. Probst Gutenberg and S. Sachdeva. Maximum flow and minimum-cost flow in almost-linear time (https://arxiv.org/abs/2203.00671). FOCS (2022), 612--623 (https://doi.org/10.1109/FOCS54457.2022.00064).DOI
- L. Chen, R. Kyng, Y. P. Liu, S. Meierhans and M. Probst Gutenberg. https://arxiv.org/abs/2311.18295 Almost-linear time algorithms for incremental graphs: cycle detection, SCCs, - shortest path, and minimum-cost flow . STOC (2024), 1165--1173 (https://doi.org/10.1145/3618260.3649745).DOI
- E. Cohen. Approximate max-flow on small depth networks (https://doi.org/10.1137/S0097539792236717). SIAM Journal on Computing 24 (1995), 579--597.DOI
- J. E. Graver. On the foundations of linear and integer linear programming I (https://doi.org/10.1007/BF01681344). Mathematical Programming 9 (1975), 207--226.DOI
- J. Holm, K. de Lichtenberg and M. Thorup. Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity (https://doi.org/10.1145/502090.502095). Journal of the ACM 48 (2001), 723--760.DOI
- R. Kyng, S. Meierhans, M. Probst Gutenberg and A. Sulser. A simpler and faster min-cost flow solver via min-ratio cycles from distance oracles (https://arxiv.org/abs/2609.23852). arXiv:2609.23852, 2026.arXiv
Show all 15 referencesShow fewer references
- A. N. Letchford, G. Reinelt and D. O. Theis. https://doi.org/10.1137/060664793 Odd minimum cut sets and -matchings revisited . SIAM Journal on Discrete Mathematics 22 (2008), 1480--1487.DOI
- Yilin Liu and GPT-6 Astra Pro. Graph algorithms for matching and flow (https://github.com/icekylinx/algorithm-frontier/tree/77140c264e7cc9e7d2853a7cc86c76f4a7ad7d28). Algorithm Frontier , source snapshot 77140c2 (2026).link
- G. B. Mertzios, A. Nichterlein and R. Niedermeier. The power of linear-time data reduction for maximum matching (https://doi.org/10.1007/s00453-020-00736-0). Algorithmica 82 (2020), 3521--3565.DOI
- OpenAI. Almost-linear-time maximum-cardinality matching in general graphs (https://github.com/openai/math/tree/main/preprints/Almost-Linear-Time-Maximum-Cardinality-Matching-in-Sparse-General-Graphs-September-24-2026). OpenAI Math Release, 2026.link
- W. T. Tutte. A short proof of the factor theorem for finite graphs (https://doi.org/10.4153/CJM-1954-033-3). Canadian Journal of Mathematics 6 (1954), 347--352.DOI