Deterministic O(m polylog m) maximum flow, or an m^(1+o(1)) implementation that beats push-relabel

Almost-linear time. Chen, Kyng, Liu, Peng, Probst Gutenberg and Sachdeva (arXiv March 2022; FOCS 2022) solve exact max flow and min-cost flow on directed graphs with polynomially bounded integer data in $m^{1+o(1)}$ time. The method is an interior-point method whose steps are approximate undirected minimum-ratio cycles, found with a dynamic data structure with amortised $m^{o(1)}$ update time. Van den Brand, Chen, Kyng, Liu, Peng, Probst Gutenberg, Sachdeva and Sidford (arXiv September 2023; FOCS 2023) made it deterministic. The framework extends to convex edge-separable objectives, including entropy-regularised optimal transport and matrix scaling. The factor hides a large subpolynomial overhead, and no implementation competitive with push-relabel or Dinic codes is reported in the sources reviewed.

A practical near-linear max-flow would speed up everything reducible to flows: bipartite matching, image segmentation, scheduling, network reliability and transportation, as well as min-cost flow and optimal-transport solvers. Today the asymptotically fastest algorithms are not used in practice, so the benefit would come from an implementable variant, not from the theoretical bound alone.

(a) A proof of a deterministic $O(m\,\mathrm{polylog}\,m)$ max-flow algorithm, or (b) an open-source implementation of a worst-case $m^{1+o(1)}$ algorithm whose wall-clock time on the standard benchmark suites at is at least competitive with the best push-relabel code, with a reproducible report. (a) is theoretical resolution; (b) is the practical target.