Home/Magazine Archive/December 2023 (Vol. 66, No. 12)/Almost-Linear-Time Algorithms for Maximum Flow and.../Full Text

Research Highlights
## Almost-Linear-Time Algorithms for Maximum Flow and Minimum-Cost Flow

We present an algorithm that computes exact maximum flows and minimum-cost flows on directed graphs with *m* edges and polynomially bounded integral demands, costs, and capacities in *m*^{1+o(1)} time. Our algorithm builds the flow through a sequence of *m*^{1+o(1)} approximate undirected minimum-ratio cycles, each of which is computed and processed in amortized *m*^{o(1)} time using a new dynamic graph data structure.

Our framework extends to algorithms running in *m*^{1+o(1)} time for computing flows that minimize general edge-separable convex functions to high accuracy. This gives almost-linear time algorithms for several problems including entropy-regularized optimal transport, matrix scaling, *p*-norm flows, and *p*-norm isotonic regression on arbitrary directed acyclic graphs.

The maximum flow problem and its generalization, the minimum-cost flow problem, are classic combinatorial graph problems that find numerous applications in engineering and scientific computing. These problems have been studied extensively over the last seven decades, starting from the work of Dantzig and Ford-Fulkerson. Several important algorithmic problems can be reduced to minimum-cost flows, for example, max-weight bipartite matching, min-cut, and Gomory-Hu trees. The origin of numerous significant algorithmic developments such as the simplex method, graph sparsification, and link-cut trees can be traced back to seeking faster algorithms for maximum flow and minimum-cost flow.

**1.1. Problem formulation**

Formally, we are given a directed graph *G* = (*V*, *E*) with |*V*| = *n* vertices and |*E*| = *m* edges, upper/lower edge capacities *u*^{+}, *u*^{−} ∈ ℝ^{E}, edge costs ** c** ∈ ℝ

where the last constraint, *B*^{┬} ** f** =

In this extended abstract, we assume that all and *d*_{v} are integral and polynomially bounded in *n* since this paper focuses on weakly-polynomial algorithms for the maximum flow and minimum-cost flow problems.

**1.2. Previous work**

There has been extensive work on maximum flow and minimum-cost flow. Here, we briefly discuss some highlights from this work to help place our work in context.

Starting with the first pseudo-polynomial time algorithm by Dantzig^{14} for maximum-flow that ran in *O*(*mn*^{2}*U*) time where *U* denotes the maximum absolute capacity, approaches to designing faster flow algorithms were primarily combinatorial, working with various adaptations of augmenting paths, cycle canceling, blocking flows, and capacity/cost scaling. A long line of work led to a running time of *Õ*(*m* min {*m*^{1/2}, *n*^{2/3}})^{15,18,19,21} for maximum flow, and *Õ*(*mn*)^{17} for minimum-cost flow. These bounds stood for decades.

In a breakthrough work on solving Laplacian linear systems and computing electrical flows, Spielman and Teng^{34} introduced a novel set of ideas and tools for solving flow problems using combinatorial techniques in conjunction with continuous optimization methods. To deploy these methods, flow algorithms researchers have used graph-algorithmic techniques to solve increasingly difficult subproblems that drive powerful continuous methods.

In the context of maximum flow and minimum-cost flow, Daitch and Spielman^{13} demonstrated the power of this paradigm by using a path-following interior point method (IPM) to reduce the minimum-cost flow problem to solving a sequence of roughly electrical flow (*ℓ*_{2}) problems. Since each of these *ℓ*_{2} problems could then be solved in nearly-linear time using the fast Laplacian solver by Spielman-Teng, they achieved an *Õ*(*m*^{1.5}) time algorithm for minimum-cost flow, the first progress in two decades. They showed that a key advantage of IPMs is that they reduce flow problems on directed graphs to flow problems on undirected graphs, which are easier to work with.

While other continuous optimization methods have been used in the context of maximum flow, even leading to nearly-linear time (1 + ε) -approximate undirected maximum flow and multicommodity flow algorithms,^{12,23,30,32,33} to date all approaches for exact maximum flow and minimum-cost flow rely on the framework suggested by Daitch and Spielman of using a path-following IPM to reduce to a small but polynomial number of convex optimization problems. Notable achievements include an *m*^{4/3+o(1)}*U*^{1/3} time algorithm for bipartite matching and unit-capacity maximum flow.^{4,22,27,28,29} Further, for general capacities, minimum-cost flow algorithms were given with runtimes *Õ*(*m* + *n*^{1.5})^{8,9,10} and *Õ*(*m*^{3/2−1/58}).^{5,6,16,35} In both of these results, the development of efficient data structures to solve the sequence of *ℓ*_{2} sub-problems in amortized time sub-linear in *m* has played a key role in obtaining these runtimes. Yet, despite this progress, the best running time bounds remain far from linear.

**1.3. Our result**

We give the first almost-linear time algorithm for minimum-cost flow, achieving the optimal running time up to subpolynomial factors.

THEOREM 1.1. *There is an algorithm that, on a graph G* = (*V*, *E*) *with m edges, vertex demands, upper/lower edge capacities, and edge costs, all integral with capacities and costs bounded by a polynomial in n, computes an exact minimum-cost flow in m*^{1+o(1)} *time with high probability.*

Our algorithm can be extended to work with capacities and costs that are not polynomially bounded at the cost of an additional logarithmic dependency in both the maximum absolute capacity and the maximum absolute cost.

We make two key contributions to achieve our result. First, we develop a novel potential-reduction IPM, similar to Karmarkar's original work.^{20} Our IPM is *worse* in some ways than existing path-following IPMs because it needs more updates to converge to a good solution. However, our new IPM reduces the minimum-cost flow problem to a sequence of update subproblems that have a more combinatorial structure than those studied before. This enables our second key contribution, a data structure that solves our sequence of update subproblems extremely quickly.

In addition to the use of highly combinatorial updates, our new IPM has three crucial properties. The IPM is (a) *robust* to approximation error in subproblems, (b) *stable* in terms of the subproblems it defines, and (c) *stable* in terms of a good solution to the subproblems. These features allow us to solve the sequence of update subproblems much faster by developing a powerful data structure, yielding a much faster algorithm overall. Thus, instead of making graph algorithms more suitable for continuous optimization, we made continuous optimization more suitable for graph algorithms.

We call the update subproblem that our IPM yields *min-ratio cycle*: This problem is specified by a graph where every edge has a "gradient" and a "length." The problem asks us to find a cycle that minimizes the sum of (signed, directed) edge gradients relative to its (undirected) length.

Our data structure for solving the sequence of min-ratio cycle problems is our second key contribution. As a first observation, we show that if we sample a random "low-stretch" spanning tree of the graph, then with constant probability, some *fundamental tree cycle* approximately solves the min-ratio cycle problem. Recall a fundamental tree cycle is a cycle defined by a single non-tree edge and the unique tree path between its endpoints. Unfortunately, this simple approach fails after a single flow update, as the IPM requires us to change the gradients and lengths after each update.

To maintain a set of trees that repeatedly allow us to identify good update cycles, we develop a hierarchical construction based on a recursive approach. This requires us to repeatedly construct and contract a random forest (which partially defines our tree), and then recurse on the resulting smaller graph, which we call a *core graph.* Furthermore, to enable recursion, we need to reduce the edge count in the core graph. We achieve this using a new *spanner* construction, which identifies a sparse subgraph of the core graph on which to recurse *and* detects if the removed edges damage the min-ratio cycle. Maintaining the core graphs and spanners in our recursive construction requires us to develop an array of novel dynamic graph techniques, which may be of independent interest.

**1.4. Applications**

Our result in Theorem 1.1 has a wide range of applications. By standard reductions, it gives the first *m*^{1+o(1)} time algorithms for bipartite matching, worker assignment, negative-lengths single-source shortest paths, and several other problems. For the negative-lengths shortest path problem, Bernstein, Nanongkai, and Wulff-Nilsen obtained the first *m* · poly(log *m*) time algorithm in an independent and concurrent work.^{7}

Using recent reductions from various connectivity problems to maximum flow, we also obtain the first *m*^{1+o(1)} time algorithms to compute vertex connectivity and Gomory-Hu trees in undirected, unweighted graphs,^{1,25} and (1 + ε)-approximate Gomory-Hu trees in undirected weighted graphs.^{26} We also obtain the current fastest algorithm to find the global min-cut in a directed graph.^{11} Finally, we obtain the first almost-linear-time algorithm to compute the approximate sparsest cuts in directed graphs.

Additionally, our algorithm extends to computing flows that minimize general edge-separable convex objectives.

INFORMAL THEOREM 1.2. *Consider a graph G with demands d, and an edge-separable convex cost function* cost(

This generalization gives the first almost-linear-time algorithms for solving entropy-regularized optimal transport (equivalently, matrix scaling), *p*-norm flow problems, and *p*-norm isotonic regression for *p* ∈ [1,∞].

**2.1. Computing minimum-cost flows via undirected min-ratio cycles**

Recall the linear program for minimum-cost flow given in Equation (1). We assume that this LP has a unique optimal solution at *f*^{*} ∈ ℝ^{E} and let *F*^{*} = *c*^{┬} *f*^{*} (this can be achieved by a negligible perturbation using the famous Isolation Lemma).

For our algorithm, we use a potential-reduction interior point method,^{20} where in each iteration we measure progress by reducing the value of the potential function

for α = 1/(1000 log *mU*). The reader can think of the barrier *x*^{-α} as the more standard -log *x* for simplicity instead. We use it for technical reasons beyond the scope of this paper.

Using standard techniques, one can add *O*(*n*) additional, artificial edges of large capacity and cost to the graph *G* such that the optimal solution to the minimum-cost flow problem remains unchanged (and in particular is not supported on the artificial edges) and such that one can easily find a *feasible* flow ** f** on the artificial edges such that

Given the current *feasible solution* ** f**, the potential reduction interior point method asks to find a circulation Δ, that is, a flow that satisfies

Let us next describe how to find a circulation Δ that reduces the potential sufficiently. Given the current flow ** f**, defining the gradient and lengths and , and we let be the matrix with these lengths on the diagonal and zeros elsewhere. We can then define the

Given any solution Δ to this problem with *g(f)*^{┬}Δ/||*L*Δ||_{1} ≤ −*k* for some *k* < 1/100, scaled so that ||** L**Δ||

We emphasize that it is essential for our data structure that the witness circulation *f*^{*} – ** f** yields a sufficiently good solution. This assumption ensures that good solutions to the min ratio cycle instances do not change arbitrarily between iterations. Further, even though the algorithm does not have access to the witness circulation

Finally, let us contrast our approach with previous approaches: previous analyses of IPMs solved *ℓ*_{2} problems, that is, problems of the form given in Equation (2) but with the *ℓ*_{1} norm replaced by a *ℓ*_{2} norm (see Figure 1), which can be solved using a linear system. Karmarkar^{20} shows that repeatedly solving *ℓ*_{2} subproblems, the IPM converges in *Õ*{*m*) iterations. Later analyses of path-following IPMs^{31} showed that a sequence of subproblems suffices to give a high-accuracy solution. Surprisingly, we are able to argue that a solving sequence of *Õ*{*m*)*ℓ*_{1} minimizing subproblems of the form in Equation (2) suffice to give a high-accuracy solution to Equation (1). In other words, changing the *ℓ*_{2} norm to an *ℓ*_{1} norm does not increase the number of iterations in a potential reduction IPM. The use of an *ℓ*_{1}-norm-based subproblem gives us a crucial advantage: Problems of this form must have optimal solutions in the form of simple cycles—and our new algorithm finds approximately optimal cycles vastly more efficiently than any known approaches for *ℓ*_{2} subproblems.

**Figure 1. The IPM takes steps to minimize the potential Φ( f) by updating f to f + Δ. Previous approaches suggest obtaining Δ by solving an ℓ_{2} subproblem (here finding Δ_{2} as the optimal step on an ellipsoid), but our approach obtains Δ by minimizing an ℓ_{1} problem (illustrated by finding Δ_{1} as the optimal step in a box). While the new strategy possibly makes less progress at a step, this allows us to find the step Δ more efficiently.**

**2.2. High-level overview of the data structure for dynamic min-ratio cycle**

As discussed in the previous section, our algorithm computes a minimum-cost flow by solving a sequence of *m*^{1+o(1)} min-ratio cycle problems min _{B┬Δ = 0} *g*^{┬}Δ/||** L**Δ||

**Warm-up: A simple, static ALGORITHM.** A simple approach to finding an *Õ*(1) -approximate min-ratio cycle is the following: given our graph *G*, we find a probabilistic low stretch spanning tree *T*, that is, a tree such that for each edge *e* = (*u,v*) ∈ *G*, the stretch of *e*, defined as where *T*[*u*, *v*] is the unique path from *u* to *v* along the tree *T*, is *Õ*(1) in expectation. Such a tree can be found in *Õ*(*m*) time.^{2,3} This fact will allow us to argue that with probability at least , one of the tree cycles is an *Õ*(1) -approximate solution to Equation (2).

Let Δ^{*} be the optimal circulation that minimizes Equation (2), and assume w.l.o.g. that Δ^{*} is a cycle that routes one unit of flow along the cycle. We assume for convenience, that edges on Δ^{*} are oriented along the flow direction of Δ^{*}, that is, . Then, for each edge *e* = (*u*, *v*), the *fundamental tree cycle* of *e* in *T*, denoted *e*⊕*T*[*v*, *u*], is formed by edge *e* concatenated with the path in *T* from its endpoint *v* to *u.* To work again with vector notation, we denote by ** p**(

**Figure 2. Illustrating the decomposition Δ* = Σ _{e:Δ*e≥0} Δ*_{e}· p(e⊕T[v, u]) of a circulation into fundamental tree cycles.**

From the guarantees of the low-stretch tree distribution, we know that the circulation Δ^{*} is not stretched by too much in expectation. Thus, by Markov's inequality, with probability at least , the circulation Δ^{*} is not stretched by too much. Formally, we have that for γ = *Õ*(1). Combining these insights, we can derive that

where the last inequality follows from the fact that (recall also that *g*^{┬} Δ^{*} is negative). This tells us that for the edge *e* minimizing the expression on the right, the tree cycle *e*⊕*T*[*v*, *u*] is a γ-approximate solution to Equation (2), as desired. We can boost the probability of success of the above algorithm by sampling *Õ*(1) trees *T*_{1}, *T*_{2}, …, *T _{s}* independently at random and conclude that w.h.p. one of the fundamental tree cycles approximately solves Equation (2).

Unfortunately, after updating the flow ** f** to

**A dynamic approach.** Thus we consider the data structure problem of maintaining an *m*^{o(1)} approximate solution to Equation (2) over a sequence of at most *m*^{1+o{1)} changes to entries of ** g**,

To obtain an efficient algorithm to maintain these trees *T _{i}*, we turn to a recursive approach. Each level of the recursion will

In each level of our recursion, we first reduce the number of vertices using a forest contraction and then the number of edges by making the contracted graph sparse. To reduce the number of vertices, we produce a *core graph* (the result of contracting forest components) on a subset of the original vertex set, and we then compute a *spanner* of the core graph which reduces the number of edges. The edge-reduction step is important to ensure the overall recursion reduces the graph size in each step, which is essential to obtaining almost linear running time in our framework.

Both the *core graph* and *spanner* at each level need to be maintained dynamically, and we ensure they are very stable under changes in the graphs at shallower levels in the recursion. In both cases, our notion of stability relies on some subtle properties of the interaction between data structure and hidden witness circulation.

We maintain a recursive hierarchy of graphs. At the top level of our hierarchy, for the input graph *G*, we produce *B* = *O*(log *n*) core graphs. To obtain each such core graph, for each *i* ∈ [*B*], we sample a (random) forest *F _{i}* with

While each core graph *G/F _{i}* now has only

**Figure 3. Illustration of a dichotomy: either one of the edges e ∈ E_{G/Fi} \ E_{S(G,Fi)} has a spanner cycle consisting of e combined with Π_{G/Fi→S(G,Fi)}(e) which is almost as good as (f)^{*}, or re-routing (f)^{*} into S(G, F_{i}) roughly preserves its quality.**

Our recursion uses *d* levels, where we choose the size reduction factor *k* such that *k ^{d}* ≈

What have we achieved using this hierarchical construction compared to our simple, static algorithm? First, consider the setting of an *oblivious adversary*, where the gradient and length update sequences and the optimal circulation after each update are fixed in advance (i.e., the adversary is oblivious of the algorithm's random choices). In this setting, we can show that our spanner-of-core graph construction can survive through *m*^{1-o(1)}/*k*^{i} updates at level *i.* Meanwhile, we can rebuild these constructions in time *m*^{1+o(1)}/*k*^{i-1}, leading to an amortized cost per update of *km*^{o(1)} ≤ *m*^{o(1)} at each level. This gives the first dynamic data structure for our undirected min-ratio problem with *m*^{o(1)} query time against an oblivious adversary.

However, our real problem is harder: the witness circulation in each round is Δ(** f**)

**2.3. Building core graphs**

In this section, we describe our core graph construction, which maps our dynamic undirected min-ratio cycle problem on a graph *G* with at most *m* edges and vertices into a problem of the same type on a graph with only *Õ*{*m*/*k*) vertices and *m* edges, and handles *Õ*(*m*/*k*) updates to the edges before we need to rebuild it.

**Forest routings and stretches.** To understand how to define the stretch of an edge *e* with respect to a forest *F*, it is useful to define how to *route* an edge *e* in *F.* Given a spanning forest *F*, every path and cycle in *G* can be mapped to *G/F* naturally (where we allow *G/F* to contain self-loops). On the other hand, if every connected component in *F* is rooted, where root^{F}_{u} denotes the root corresponding to a vertex *u*∈*V*, we can map every path and cycle in *G/F* back to *G* as follows. Let *P* = *e*_{1}, …, *e _{k}* be any (not necessarily simple) path in

where we use *A*⊕*B* to denote the concatenation of paths *A* and *B*, and *F*[*a*, *b*] to denote the unique *ab*-path in the forest *F.* When *P* is a circuit (that is, a not necessarily simple cycle), *P ^{G}* is a circuit in

To make our core graph construction dynamic, the key operation we need to support is the dynamic addition of more root nodes, which results in forest edges being deleted to maintain the invariant each connected component has a root node. Whenever an edge is changing in *G*, we ensure that *G/F* approximates the changed edge well by forcing both its endpoints to become root nodes, which in turn makes the portal routing of the new edge trivial and this guarantees its stretch is 1.

For any edge *e ^{G}* = (

Now, for any flow ** f** in

**Collections of low stretch decompositions (LSD).** The first component of the data structure is constructing and maintaining forests of *F* that form a *Low Stretch Decomposition (LSD)* of *G.* Informally, a *k*-LSD is a rooted forest *F*⊆*G* that decomposes *G* into *O*(*m/k*) vertex disjoint components. Given some positive edge weights and reduction factor *k* > 0, we compute a *k*-LSD *F* and length upper bounds of *G/F* that satisfy two properties:

- for any edge
*e*∈^{G}*G*with image*e*in*G/F*, and - The weighted average of w.r.t.
is only*v**Õ*(1), that is, .

Item 1 guarantees that the solution to Equation (2) for *G/F* yields a *Õ*(*k*)-approximate one for *G.* However, this guarantee is not sufficient for our data structure, as our *B*-branching tree chain has *d* ≈ log_{k} *m* levels of recursion and the quality of the solution from the deepest level would only be *Õ*(*k*)^{d} ≈ *m*^{1+o(1)}-approximate.

Instead, we compute *k* different edge weight assignments *v*_{1}, …, *v*_{k} via multiplicative weight updates so that the LSDs *F*_{1}, …, *F _{k}* have

By Markov's inequality, for any fixed flow ** f** in holds for at least half the LSDs corresponding to

That is, it suffices to solve Equation (2) on *G/F*_{1}, …, *G/F _{B}* to find an

**2.4. Maintaining a branching tree chain**

Our branching chain is constructed as follows:

- Sample and maintain
*B*=*O*(log*n*)*k*-LSDs*F*_{1},*F*_{2}, …,*F*, and their associated core graphs_{B}*G/F*. Across_{i}*O*(*m/k*) updates at the top level, the forests*F*are_{i}*decremental*, that is, only undergo edge deletions (from root insertions), and will have*Õ*(*m*/*k*) connected components. - Maintain spanners
*S*(*G*,*F*) of the core graphs_{i}*G/F*, and embeddings Π_{i}_{E(G/Fi)→S(G/Fi)}, say with length increase*γ*_{ℓ}=*m*^{o(1)}. - Recursively process the graphs
*S*{*G*,*F*), that is, maintain LSDs and core graphs on those, and spanners on the contracted graphs, etc., for_{i}*d*total levels, with*k*=^{d}*m.* - Whenever a level
*i*accumulates*m/k*total updates, hence doubling the number of edges in the graphs at that level, we rebuild levels^{i}*i*,*i*+ 1, …,*d.*

Recall that on average, the LSDs stretch lengths by *Õ*(1), and the spanners *S*(*G*, *F _{i}*) stretch lengths by γ

We now discuss how to update the forests *G/F _{i}* and spanners

Overall, let every level have recourse γ_{r} = *m*^{o(1)} (independent of *k*) per tree. Then each update at the top level induces *O*(*B*γ_{r})^{d} (as we branch using *B* forests/core graphs at each level of the recursion) updates in the data structure overall. Intuitively, for the proper choice of *d* = ω(1), both the total recourse *O*(*B*γ_{r})^{d} and approximation factor *Õ(γ _{ℓ})^{d}* are

**2.5. Going beyond oblivious adversaries by using IPM guarantees**

The precise data structure in the previous section only works for *oblivious adversaries*, because we used that if we sampled *B* = *O*(log *n*) LSDs, then w.h.p. there is a tree whose average stretch is *Õ*(1) with respect to a *fixed flow* ** f.** However, since we are updating the flow along the circulations returned by our data structure, we influence future updates, so the optimal circulations our data structure needs to preserve, are not independent of the randomness used to generate the LSDs. To overcome this issue, we leverage the key fact that the flow

To simplify our discussion, we focus on the role of the witness in ensuring the functioning of a single layer of core graph construction, which already captures the main ideas. We can prove that for any flow holds where **Δ( f)=f* − f**. Then, the best solution to Equation (2) among the LSDs

In this case, let be the best solution obtained from graphs *G/F*_{1}, …, *G/F _{B}*. We have

The additive *Õ*(*m*) term is there for technical reasons that can be ignored for now. We define the *width* ** w**(

Observe that for any forest *F _{j}* in the LSD of

Equation (5) also holds with w.h.p. if the collection of LSDs is built after knowing ** f.** However, this does not necessarily hold after augmenting with Δ, an approximate solution to Equation (2).

Due to the stability of ** w**(

Using the fact that , have the following:

Thus, solving Equation (2) on the updated *G/F*_{1}, …, *G/F _{B}* yields a good enough solution for reducing IPM potential as long as the width of

If the solution on the updated graphs *G/F*_{1}, …, *G/F _{B}* does not have a good enough quality, we know by the above discussion that ||

The full construction is along these lines, but more complicated since we recursively maintain the solutions on the spanners of each core graph *G/F*_{1}, …, *G/F _{B}*. In the full version of the paper, we describe and analyze a multi-level rebuilding scheme that extends the above reasoning to our full data structure.

In this paper, we presented an almost-linear time algorithm for minimum-cost flow, maximum flow, and more generally, all convex single-commodity flows. Our work essentially settles the complexity of several fundamental and intensely studied problems in algorithms design. We hope that the ideas introduced in this work will spur further research in several directions, including simpler and faster algorithms for flow problems; hopefully resulting in a significant impact on algorithms in practice.

Li Chen was supported by NSF Grant CCF-2106444. Rasmus Kyng and Maximilian Probst Gutenberg have received funding from the grant "Algorithms and complexity for high-accuracy flows and convex optimization" (no. 200021 204787) of the Swiss National Science Foundation. Yang P. Liu was supported by NSF CAREER Award CCF-1844855 and NSF Grant CCF-1955039. Richard Peng was partially supported by NSF CAREER Award CCF-1846218 and NSERC Discovery Grant RGPIN-2022-03207. Sushant Sachdeva's research is supported by a Natural Sciences and Engineering Research Council of Canada (NSERC) Discovery Grant RGPIN-2018–06398 and an Ontario Early Researcher Award (ERA) ER21–16–284.

The authors thank the 2021 Hausdorff Research Institute for Mathematics Program Discrete Optimization. The authors are very grateful to Yin Tat Lee and Aaron Sidford for several useful discussions.

1. Abboud, A., Krauthgamer, R., Li, J., Panigrahi, D., Saranurak, T., Trabelsi, O. Breaking the cubic barrier for all-pairs max-flow: Gomory-hu tree in nearly quadratic time. In *63 ^{rd} IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022* (Denver CO, USA, October 31–November 3, 2022), IEEE, NY, 884–895.

2. Abraham, I., Neiman, O. Using petal-decompositions to build a low stretch spanning tree. *SIAM J. Comput. 48*, 2 (2019), 227–248.

3. Alon, N., Karp, R.M., Peleg, D., West, D. A graph-theoretic game and its application to the k-server problem. *SIAM J. Comput. 24*, 1 (1995), 78–100.

4. Axiotis, K., Mąadry, A., Vladu, A. Circulation control for faster minimum cost flow in unit-capacity graphs. In *2020 IEEE 61 ^{st} Annual Symposium on Foundations of Computer Science (FOCS)* (2020), IEEE, NY, 93–104.

5. Axiotis, K., Mąadry, A., Vladu, A. Faster sparse minimum cost flow by electrical flow localization. In *2021 IEEE 62 ^{nd} Annual Symposium on Foundations of Computer Science (FOCS)* (2022), IEEE, NY, 528–539.

6. Bernstein, A., Gutenberg, M.P., Saranurak, T. Deterministic decremental sssp and approximate min-cost flow in almost-linear time. In *2021 IEEE 62 ^{nd} Annual Symposium on Foundations of Computer Science (FOCS)* (2022), IEEE, NY, 1000–1008.

7. Bernstein, A., Nanongkai, D., Wulff-Nilsen, C. Negative-weight single-source shortest paths in near-linear time. In *2022 IEEE 63 ^{rd} Annual Symposium on Foundations of Computer Science (FOCS)* (2022), IEEE, NY, 600–611.

8. Brand, J.v.d., Lee, Y.T., Liu, Y.P., Saranurak, T., Sidford, A., Song, Z., et al. Minimum cost flows, mdps, and *ℓ*_{1}-regression in nearly linear time for dense instances. In *STOC* (2021), ACM, NY, 859–869.

9. Brand, J.v.d., Lee, Y.-T., Nanongkai, D., Peng, R., Saranurak, T., et al. Bipartite matching in nearly-linear time on moderately dense graphs. In *2020 IEEE 61 ^{st} Annual Symposium on Foundations of Computer Science (FOCS)* (2020), IEEE, NY, 919–930.

10. Brand, J.v.d., Lee, Y.T., Sidford, A., Song, Z. Solving tall dense linear programs in nearly linear time. In *Proccedings of the 52 ^{nd} Annual ACM SIGACT Symposium on Theory of Computing (STOC)* (2020), ACM, NY, 775–788.

11. Cen, R., Li, J., Nanongkai, D., Panigrahi, D., Saranurak, T., Quanrud, K. Minimum cuts in directed graphs via partial sparsification. In *2021 IEEE 62 ^{nd} Annual Symposium on Foundations of Computer Science (FOCS)* (2021), IEEE, Denver, CO, 1147–1158.

12. Christiano, P., Kelner, J.A., Mąadry, A., Spielman, D.A., Teng, S. Electrical flows, Laplacian systems, and faster approximation of maximum flow in undirected graphs. In *Proceedings of the 43 ^{rd} ACM Symposium on Theory of Computing (STOC)* (2011), ACM, NY, 273–282.

13. Daitch, S.I., Spielman, D.A. Faster approximate lossy generalized flow via interior point algorithms. In *Proceedings of the fortieth annual ACM symposium on Theory of computing* (2008), ACM, NY, 451–460.

14. Dantzig, G.B. Application of the simplex method to a transportation problem. In *Activity Analysis and Production and Allocation*, T.C. Koopmans (ed.), (1951), John Wiley and Sons, New York, 359–373.

15. Even, S., Tarjan, R.E. Network flow and testing graph connectivity. *SIAM J. Comput. 4*, 4 (1975), 507–518.

16. Gao, Y., Liu, Y.P., Peng, R. Fully dynamic electrical flows: Sparse maxflow faster than goldberg-rao. In *2021 IEEE 62 ^{nd} Annual Symposium on Foundations of Computer Science (FOCS)* (2022), IEEE, NY, 516–527.

17. Goldberg, A., Tarjan, R. Finding minimum-cost circulation by successive approximation. *Math. Oper. Res.* 15 (1990), 430–466.

18. Goldberg, A.V., Rao, S. Beyond the flow decomposition barrier. *J. ACM 45*, 5 (1998), 783–797. Announced at FOCS'97.

19. Hopcroft, J.E., Karp, R.M. An *n*^{5/2} algorithm for maximum matchings in bipartite graphs. *SIAM J. Comput. 2*, 4 (Dec 1973), 225–231.

20. Karmarkar, N. A new polynomial-time algorithm for linear programming. In *STOC* (1984), ACM, NY, 302–311.

21. Karzanov, A.V. On finding maximum flows in networks with special structure and some applications. *Matematicheskie Voprosy Upravleniya Proizvodstvom 5*, (1973), 81–94.

22. Kathuria, T., Liu, Y.P., Sidford, A. Unit capacity maxflow in almost *O*(*m*^{4/3}) time. In *61 ^{st} IEEE Annual Symposium on Foundations of Computer Science (FOCS)* (2020), IEEE, NY, 119–130.

23. Kelner, J.A., Lee, Y.T., Orecchia, L., Sidford, A. An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations. In *Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)* (2014), Society for Industrial and Applied Mathematics, Portland, OR, 217–226.

24. Kyng, R., Peng, R., Sachdeva, S., Wang, D. Flows in almost linear time via adaptive preconditioning. In *Proceedings of the 51 ^{st} Annual ACM SIGACT Symposium on Theory of Computing* (2019), ACM, NY, 902–913.

25. Li, J., Nanongkai, D., Panigrahi, D., Saranurak, T., Yingchareonthawornchai, S. Vertex connectivity in poly-logarithmic max-flows. In *Proceedings of the 53 ^{rd} Annual ACM SIGACT Symposium on Theory of Computing* (2021), ACM, NY, 317–329.

26. Li, J., Panigrahi, D. Approximate gomory–hu tree is faster than n–1 max-flows. In *Proceedings of the 53 ^{rd} Annual ACM SIGACT Symposium on Theory of Computing* (2021), ACM, NY, 1738–1748.

27. Liu, Y.P., Sidford, A. Faster energy maximization for faster maximum flow. In *Proceedings of the 52 ^{nd} Annual ACM SIGACT Symposium on Theory of Computing (STOC 2020)* (2020), ACM, NY, 803–814.

28. Mąadry, A. Navigating central path with electrical flows: From flows to matchings, and back. In *2013 IEEE 54 ^{th} Annual Symposium on Foundations of Computer Science* (2013), IEEE, NY, 253–262.

29. Mąadry, A. Computing maximum flow with augmenting electrical flows. In *57 ^{th} IEEE Annual Symposium on Foundations of Computer Science (FOCS)* (2016), IEEE Computer Society, NY, 593–602.

30. Peng, R. Approximate undirected maximum flows in o(mpolylog(n)) time. In *Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms* (2016), SIAM, Philadelphia, PA, 1862–1867.

31. Renegar, J. A polynomial-time algorithm, based on newton's method, for linear programming. *Math. Program. 40*, 1 (1988), 59–93.

32. Sherman, J. Nearly maximum flows in nearly linear time. In *54 ^{th} Annual IEEE Symposium on Foundations of Computer Science (FOCS)* (2013), IEEE Computer Society, NY, 263–269.

33. Sherman, J. Area-convexity, *ℓ*_{∞} regularization, and undirected multicommodity flow. In *Proceedings of the 49 ^{th} Annual ACM SIGACT Symposium on Theory of Computing* (2017), ACM, NY, 452–460.

34. Spielman, D.A., Teng, S. Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In *Proceedings of the 36 ^{th} Annual ACM Symposium on Theory of Computing (STOC)* (2004), ACM, NY, 81–90.

35. van den Brand, J., Gao, Y., Jambulapati, A., Lee, Y.T., Liu, Y.P., Peng, R., et al. Faster maxflow via improved dynamic spectral vertex sparsifiers. In *Proceedings of the 54 ^{th} Annual ACM SIGACT Symposium on Theory of Computing (STOC 2022)* (2022), ACM, NY, 543–556.

To view the accompanying Technical Perspective, visit doi.acm.org/10.1145/3623277

The original version of this paper titled "Maximum Flow and Minimum-Cost Flow in Almost-Linear Time" was published in *Proceedings of the 2022 IEEE 63 ^{rd} Annual Symposium on Foundations of Computer Science*, 612–623.

2023 Copyright held by owner(s)/author(s). Publication rights licensed to ACM.

Request permission to publish from permissions@acm.org

The Digital Library is published by the Association for Computing Machinery. Copyright © 2023 ACM, Inc.

No entries found