Almost-Linear-Time 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 ∈ ℝ^E, and vertex demands d ∈ ℝ^V with ∑_v∈V d_v = 0. Our goal is to solve the following linear program for the minimum-cost flow problem

where the last constraint, B^⊤ f = d, succinctly captures the requirement that the flow f satisfies vertex demands d, where B ∈ℝ^E×V is the edge-vertex incidence matrix defined as B_((a,b),v) is 1 if v = a, −1 if v = b, and 0 otherwise.

In this extended abstract, we assume that all $u_e^{+},u_e^{-},c_e$ 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¹⁴ for maximum-flow that ran in O(mn²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^½, n^⅔})¹⁵, ^18,19,21 for maximum flow, and Õ(mn)¹⁷ 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³⁴ 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¹³ 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 $\sqrt{m}$ electrical flow (ℓ₂) problems. Since each of these ℓ₂ 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 ℓ₂ 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.

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.²⁰ 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.⁷

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.²⁶ We also obtain the current fastest algorithm to find the global min-cut in a directed graph.¹¹ 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.

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,²⁰ 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 B^⊤ f = d with bounded potential, that is, Φ(f) = O(m log m).

Given the current feasible solution f, the potential reduction interior point method asks to find a circulation Δ, that is, a flow that satisfies B^⊤ Δ = 0, such that Φ(f + Δ) ≤ Φ(f) − m^−o(1). Given Δ, it then sets f ← f + Δ and repeats. When Φ(f) ≤ −200m log mU, we can terminate because then c^⊤ f − F^⋆ ≤ (mU)⁻¹⁰, at which point standard techniques let us round to an exact optimal flow.¹³ Thus if we can reduce the potential by m^−o(1) per iteration, the method terminates in m^1+o(1) iterations.

Let us next describe how to find a circulation Δ that reduces the potential sufficiently. Given the current flow f, defining the gradient and lengths $g\left(f\right)\stackrel{\text{def}}{=}\nabla \Phi \left(f\right)$ and $\ell {\left(f\right)}_e\stackrel{\text{def}}{=}{(u_e^{+}-f_e)}^{-1-\alpha }+{(f_e-u_e^{-})}^{-1-\alpha }$, and we let $L\stackrel{\text{def}}{=}\text{diag}(\ell )$ be the matrix with these lengths on the diagonal and zeros elsewhere. We can then define the min-ratio cycle problem

Given any solution Δ to this problem with g(f)^⊤ Δ/∥LΔ∥₁≤−κ for some κ < 1/100, scaled so that ∥LΔ∥₁ = κ/50. Then a direct Taylor expansion shows that Φ(f + Δ) ≤ Φ(f) − κ²/500. Hence, it suffices to show that such a Δ exists with $k=\tilde{\Omega }\left(1\right)$, because then a data structure that returns an m^o(1)-approximate solution still has κ = m^−o(1), which suffices. Fortunately, the witness circulation Δ(f^⋆) = f^⋆ − f satisfies $g{\left(f\right)}^{\top }\Delta /\Vert L\Delta {\Vert }_1\le -\tilde{\Omega }\left(1\right)$.

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 f^⋆ − f, it still knows how it changes between iterations as it can track changes in f. We are able to leverage this guarantee to ensure our data structure succeeds for the updates coming from the IPM.

Finally, let us contrast our approach with previous approaches: previous analyses of IPMs solved ℓ₂ problems, that is, problems of the form given in Equation (2) but with the ℓ₁ norm replaced by a ℓ₂ norm (see Figure 1), which can be solved using a linear system. Karmarkar²⁰ shows that repeatedly solving ℓ₂ subproblems, the IPM converges in Õ(m) iterations. Later analyses of path-following IPMs³¹ showed that a sequence of $\tilde{O}{\left(\sqrt{m}\right)\ell }_2$ subproblems suffices to give a high-accuracy solution. Surprisingly, we are able to argue that a solving sequence of Õ(m)ℓ₁ minimizing subproblems of the form in Equation (2) suffice to give a high-accuracy solution to Equation (1). In other words, changing the ℓ₂ norm to an ℓ₁ norm does not increase the number of iterations in a potential reduction IPM. The use of an ℓ₁-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 ℓ₂ subproblems.

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^{\top }\Delta =0}{g}^{\top }\Delta /{\Vert L\Delta \Vert }_1$ to m^o(1) multiplicative accuracy. Because our IPM ensures stability for lengths and gradients, and is even robust to approximations of lengths and gradients, we can show that over the course of the algorithm, we only need to update the entries of the gradients g and lengths ℓ at most m^1+o(1) total times.

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 $st{r}_e^{T,\ell }\stackrel{\text{def}}{=}\frac{{\sum }_{f\in T[u,v]}\ell (f)}{\ell (e)}$ 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 $\frac{1}{2}$, 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, $\Delta *\in {ℝ}_{\ge 0}^E$. 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(e⊕T[v, u])∈ℝ^E the vector that sends one unit of flow along the cycle e⊕T[v, u] in the direction that aligns with the orientation of e. A classic fact from graph theory now states that $\Delta *={\sum }_{e:{\Delta }_e^{*}>0}{\Delta }_e^{*}\cdot p(e\oplus T[v,u])$ (note that the tree paths used by adjacent off-tree edges cancel out, see Figure 2). In particular, this implies that $g^{\top }\Delta *={\sum }_{e:{\Delta }_e^{*}>0}{\Delta }_e^{*}\cdot g^{\top }p(e\oplus T[v,u])$.

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 $\frac{1}{2}$, the circulation Δ^⋆ is not stretched by too much. Formally, we have that ${\sum }_{e:{\Delta }_e^{*}>0}{\Delta }_e^{*}\cdot {\Vert p(e\oplus T[v,u])\Vert }_1\le \gamma {\Vert L\Delta *\Vert }_1$ for γ = Õ(1). Combining these insights, we can derive that

$\begin{array}{c}\frac{g^{\top }\Delta *}{{\Vert L\Delta *\Vert }_1}\ge \frac{1}{\gamma }\cdot \frac{{\sum }_{e:{\Delta }_e^{*}>0}{\Delta }_e^{*}\cdot g^{\top }p(e\oplus T[v,u])}{{\sum }_{e:{\Delta }_e^{*}>0}{\Delta }_e^{*}\cdot {g^{\top }\Vert Lp(e\oplus T[v,u])\Vert }_1}\\ \ge \frac{1}{\gamma }\underset{e:{\Delta }_e^{*}>0}{\min }\frac{g^{\top }p(e\oplus T[v,u])}{{\Vert Lp(e\oplus T[v,u])\Vert }_1}\end{array}$

where the last inequality follows from the fact that ${\min }_{i\in \left[n\right]}\frac{x_i}{y_i}\le \frac{{\sum }_{i\in \left[n\right]}{x}_i}{{\sum }_{i\in \left[n\right]}{y}_i}$ (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₁, T₂, …, 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 f′ along such a fundamental tree cycle, we cannot reuse the set of trees T₁, T₂, …, T_s because the next solution to Equation (2) has to be found with respect to gradients g(f′) and lengths ℓ(f′) depending on f′ (instead of g = g(f) and ℓ = ℓ(f)). But g(f′) and ℓ(f′) depend on the randomness used in trees T₁, T₂, …, T_s. Thus, naively, we have to recompute all trees, spending again Ω(m) time. But this leads to run-time Ω(m²) for our overall algorithm which is far from our goal.

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 achieve an almost linear time algorithm overall, we want our data structure to have an amortized m^o(1) update time. Motivated by the simple construction above, our data structure will ultimately maintain a set of s = m^o(1) spanning trees T₁, …, T_s of the graph G. Each cycle Δ that is returned is represented by m^o(1) off-tree edges and paths connecting them on some T_i.

To obtain an efficient algorithm to maintain these trees T_i, we turn to a recursive approach. Each level of the recursion will partially construct a tree, by choosing a spanning forest of the vertices, and contracting the connected components of the forest. We obtain a tree by repeating forest selection-and-contraction until only a single vertex is left. Then, we compose the forest edges obtained at different levels, yielding a spanning tree of the original graph. At each level of the construction, our forest is probabilistic and only succeeds with constant probability at preserving the hidden witness circulation well enough. To preserve the witness with high probability, we construct O(log n) different forests at each level and recurse on them separately.

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 Õ(m/k) connected components for some size reduction parameter k. The associated core graph is the graph G/F_i which denotes G after contracting the vertices in the same components of F_i. We can define a map that lifts circulations $\hat{\Delta }$ in the core graph G/F_i, to circulations Δ in the graph G by routing flow along the contracted paths in F_i. The lengths in the core graph $\hat{\ell }$ (again let $\hat{L}=\text{diag}\left(\hat{\ell }\right))$) are chosen to upper bound the length of circulations when mapped back into G such that ${\Vert \hat{L}\hat{\Delta }\Vert }_1\ge {\Vert L\Delta \Vert }_1$. Crucially, we must ensure these new lengths $\hat{\ell }$ do not stretch the witness circulation Δ^⋆ when mapped into G/F_i by too much, so we can recover it from G/F_i. To achieve this goal, we choose F_i to be a low-stretch forest, that is, a forest with properties similar to those of a low-stretch tree. In Section 2.3, we summarize the central aspects of our core graph construction.

While each core graph G/F_i now has only Õ(m/k) vertices, it still has m edges which are too large for our recursion. To overcome this issue we build a spanner on S(G, F_i) on G/F_i to reduce the number of edges to Õ(m/k), which guarantees that for every edge e = (u, v) that we remove from G/F_i to obtain S(G, F_i), there is a u-to-v path in S(G, F_i) of length m^o(1). Ideally, we would now recurse on each spanner S(G, F_i), again approximating it with a collection of smaller core graphs and spanners. However, we face an obstacle: removing edges could destroy the witness circulation so that possibly no good circulation exists in any S(G, F_i). To solve this problem, we compute an explicit embedding ${\Pi }_{{G/F}_i\to S(G,F_i)}$ that maps each edge e=(u, v)∈G/F_i to a short u-to-v path in S(G, F_i). We can then show the following dichotomy: Let $\hat{\Delta }*$ denote the witness circulation when mapped into the core graph G/F_i. Then, either one of the edges ${e\in E}_{{G/F}_i}{E}_{S(G,F_i)}$ has a spanner cycle consisting of e combined with ${\Pi }_{{G/F}_i\to S(G,F_i)}\left(e\right)$ which is almost as good as $\hat{\Delta }*$, or re-routing $\hat{\Delta }*$ into S(G, F_i) roughly preserves its quality. Figure 3 illustrates this dichotomy. Thus, either we find a good cycle using the spanner, or we can recursively find a solution S(G, F_i) onthat almost matches $\hat{\Delta }*$ in quality. To construct our dynamic spanner with its efficient updates and strong stability guarantees under changes in the input graph, we design a new approach that diverges from other recent works on dynamic spanners.

Our recursion uses d levels, where we choose the size reduction factor k such that k^d ≈ m and the bottom level graphs have m^o(1) edges. Note that since we build B trees on G and recurse on the spanners of G/F₁, G/F₂, …, G/F_B, our recursive hierarchy has a branching factor of B = O(log n) at each level of recursion. Thus, choosing $d\le \sqrt{\log n}$, we get B^d = m^o(1) leaf nodes in our recursive hierarchy. Now, consider the forests ${F_i}_1,{F_i}_2,\mathrm{\dots },{F_i}_d$ on the path from the top of our recursive hierarchy to a leaf node. We can patch these forests together to form a tree associated with the leaf node. For each of these trees, we maintain a link-cut tree data structure. Using this data structure, whenever we find a good cycle, we can route flow along it and detect edges where the flow has changed significantly. The cycles are either given by an off-tree edge or a collection of m^o(1) off-tree edges coming from a spanner cycle. We call the entire construction a branching tree chain. In Section 2.4, we elaborate on the overall composition of the data structure.

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ⁱ updates at level i. Meanwhile, we can rebuild these constructions in time m^1+o(1)/kⁱ⁻¹, 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)^⋆ = f^⋆ − f and depends on the updates we make to f, making our sequence of subproblems adaptive. While we cannot show that our data structure succeeds against an adaptive adversary, we give a data structure that works against a restricted adaptive adversary. We show that the witness circulation f^⋆ − f lets us express the IPM as such a restricted adversary.

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.

2.4. Maintaining a branching tree chain

Our branching chain is constructed as follows:

1. Sample and maintain B = O(log n) k-LSDs F₁, F₂, …, F_B, and their associated core graphs G/F_i. Across O(m/k) updates at the top level, the forests F_i are decremental, that is, only undergo edge deletions (from root insertions), and will have Õ(m/k) connected components.

2. Maintain spanners S(G, F_i) of the core graphs G/F_i, and embeddings ${\Pi }_{E(G/F_i)\to S(G/F_i)}$, say with length increase γ_ℓ = m^o(1).

3. Recursively process the graphs S(G, F_i), that is, maintain LSDs and core graphs on those, and spanners on the contracted graphs, etc., for d total levels, with k^d = m.

4. 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 + 1, …, d.

Recall that on average, the LSDs stretch lengths by Õ(1), and the spanners S(G, F_i) stretch lengths by γ_ℓ. Hence, the overall data structure stretches lengths by Õ(γ_ℓ)^d = m^o(1) (for appropriately chosen d).

We now discuss how to update the forests G/F_i and spanners S(G, F_i). Intuitively, every time an edge e = (u, v) is changed in G, we will delete Õ(1) additional edges from F_i. This ensures that no edge’s total stretch/routing-length increases significantly due to the deletion of e. As the forest F_i undergoes edge deletions, the graph G/F_i undergoes vertex splits, where a vertex has a subset of its edges moved to a newly created vertex. Thus, a key component of our data structure is to maintain spanners and embed-dings of graphs undergoing vertex splits (and edge insertions/ deletions). Importantly, the amortized recourse (number of changes) to the spanner S(G, F_i) is m^o(1) independent of k, even though the average degree of G/F_i is Ω(k). Hence, on average Ω(k) edges will move in G/F_i per vertex split.

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 m^o(1) as desired.

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 f^⋆ − f is a good witness for the min-ratio cycle problem at each iteration.

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 f, g(f)^⊤ Δ(f)/(100m+∥L(f)Δ(f)∥₁) ≤ −Ω̃(1) holds where Δ(f) = f^⋆ − f. Then, the best solution to Equation (2) among the LSDs G/F₁, …, G/F_B maintains an Õ(1)-approximation of the quality of the witness Δ(f) = f^⋆ − f as long as

In this case, let $\hat{\Delta }$ be the best solution obtained from graphs G/F₁, …, G/F_B. We have

The additive term is there for technical reasons that can be ignored for now. We define the width w(f) of Δ(f) as w(f) = 100 · 1+|L(f)Δ(f)|. The name comes from the fact that w(f)_e is always at least $|\ell {\left(f\right)}_e\left(f_e^{*}-f_e\right)|$ for any edge e. We show that the width is also slowly changing across IPM iterations, in that if the width changed by a lot, then the residual capacity of e must have changed significantly. This gives our data structure a way to predict which edges’ contribution to the length of the witness flow f^⋆ − f could have significantly increased.

Observe that for any forest F_j in the LSD of G, we have ${\Vert {\hat{L}}^{F_j}\Delta \left(f\right)\Vert }_1\le {\Vert {\widetilde{str}}^{F_j}\circ w\left(f\right)\Vert }_1$. Thus, we can strengthen Equation (4) and show that the IPM potential can be decreased by m^−o(1) if

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(f), we have w(f + Δ)_e ≈ w(f)_e for every edge e whose length does not change a lot. For other edges, we update their edge length and force the stretch to be 1, that is, ${\widetilde{str}}_e^{F_j}=1$ via the dynamic LSD maintenance, by shortcutting the routing of the edge e at its endpoints. To distinguish between the earlier stretch values and those after updating edges, let us denote the former by ${\widetilde{str}}_{\text{old}}^{F_j}$ and the latter by ${\widetilde{str}}_{\text{new}}^{F_j}$. This gives that for any j∈[B], the following holds:

Using the fact that ${\min }_{j\in \left[B\right]}{\Vert {\widetilde{str}}_{\text{old}}^{F_j}\circ w\left(f\right)\Vert }_1\lesssim \tilde{O}\left({\Vert w\left(f\right)\Vert }_1\right)$, we have the following:

Thus, solving Equation (2) on the updated G/F₁, …, G/F_B yields a good enough solution for reducing IPM potential as long as the width of w(f + Δ) has not decreased significantly, that is, ∥w(f)∥₁ ≤ Õ(1)∥w(f + Δ)∥₁.

If the solution on the updated graphs G/F₁, …, G/F_B does not have a good enough quality, we know by the above discussion that ∥w(f + Δ)∥₁ ≤ 0.5∥w(f)∥₁ must hold. Then, we re-compute the collection of LSDs of G and solve Equation (2) on the new collection of G/F₁, …, G/F_B again. Because each recomputation reduces the ℓ₁ norm of the width by a constant factor, and all the widths are bounded by exp(log^O(1) m) (which can be guaranteed by the IPM), there can be at most Õ(1) such recomputations. At the top level, this only increases our runtime by Õ(1) factors.

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₁, …, 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.