Source-linked AI summary
An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations
Jonathan A. Kelner, Yin Tat Lee, Lorenzo Orecchia, Aaron Sidford
TL;DR
Approximate flow algorithms need to construct routings efficiently, while prior sparsifiers could preserve cut values without routing sparsified flows back into the original graph. The paper combines non-Euclidean gradient descent, flow sparsifiers, and fast oblivious routing to obtain faster single- and multicommodity flow algorithms, including O(m^{1+o(1)}ε^{-2}) time for approximate maximum s-t flow.
Problem
Prior cut sparsifiers preserved cut and flow values approximately but did not provide a direct way to route sparsified flows in the original graph.
Method
The framework reduces approximate flow problems to efficient low-competitive-ratio oblivious routings, using non-Euclidean gradient descent and flow sparsifiers with low-congestion embeddings back into the original graph.
Results
O(m^{1+o(1)}ε^{-2}) time gives an ε-approximate maximum s-t flow, while maximum concurrent flow takes O(m^{1+o(1)}ε^{-2}k^2) time.
Takeaways & Limitations
The framework supplies modular tools for constructing fast flow algorithms, including the first almost-linear-time O(m^{o(1)})-competitive oblivious routing scheme.
Takeaways & Limitations
The concurrent-flow approach achieves O(m^{1+o(1)}k^2/ε^2), because the authors could not obtain the needed regularization for an O(m^{1+o(1)}k/ε^2) algorithm.
Abstract
from arXiv · showhide
In this paper, we introduce a new framework for approximately solving flow problems in capacitated, undirected graphs and apply it to provide asymptotically faster algorithms for the maximum $s$-$t$ flow and maximum concurrent multicommodity flow problems. For graphs with $n$ vertices and $m$ edges, it allows us to find an $ε$-approximate maximum $s$-$t$ flow in time $O(m^{1+o(1)}ε^{-2})$, improving on the previous best bound of $\tilde{O}(mn^{1/3} poly(1/ε))$. Applying the same framework in the multicommodity setting solves a maximum concurrent multicommodity flow problem with $k$ commodities in $O(m^{1+o(1)}ε^{-2}k^2)$ time, improving on the existing bound of $\tilde{O}(m^{4/3} poly(k,ε^{-1})$. Our algorithms utilize several new technical tools that we believe may be of independent interest: - We give a non-Euclidean generalization of gradient descent and provide bounds on its performance. Using this, we show how to reduce approximate maximum flow and maximum concurrent flow to the efficient construction of oblivious routings with a low competitive ratio. - We define and provide an efficient construction of a new type of flow sparsifier. In addition to providing the standard properties of a cut sparsifier our construction allows for flows in the sparse graph to be routed (very efficiently) in the original graph with low congestion. - We give the first almost-linear-time construction of an $O(m^{o(1)})$-competitive oblivious routing scheme. No previous such algorithm ran in time better than $\tilde{Ω}(mn)$. We also note that independently Jonah Sherman produced an almost linear time algorithm for maximum flow and we thank him for coordinating submissions.
1. Introduction
The paper targets approximate single- and multicommodity flow problems, whose broad importance contrasts with limitations in prior sparsification, electrical-flow, and oblivious-routing approaches. It introduces a framework combining new algorithmic components to obtain faster flow algorithms.
- Motivation: Maximum flow and concurrent multicommodity flow are extensively studied core problems with theoretical, practical, and algorithmic applications.
- Paper contributions: O(m^{1+o(1)}ε^{-2}) time yields an ε-approximate maximum s-t flow, improving on the previous bound of eO(mn^{1/3}poly(1/ε)).The same framework solves maximum concurrent multicommodity flow in O(m^{1+o(1)}ε^{-2}k^2) time, improving on eO(m^{4/3}poly(k, ε^{-1})).
- Paper contributions: The paper combines non-Euclidean gradient descent, flow sparsifiers, and efficiently implemented oblivious routing as modular tools for faster flow algorithms.The authors present these components as potentially useful beyond the immediate flow problems.
- Prior limitations: Standard cut sparsifiers preserve cut weights and flow values approximately but do not explain how to route sparsified flows in the original graph.Oversampled edge weights in the sparsifier provide no direct guidance for routing those edges in the original graph.
- Prior limitations: Earlier electrical-flow algorithms incur superlinear time through an intrinsic Θ(√m) factor from approximating an ℓ∞ congestion objective with ℓ2 electrical flows.
- Prior limitations: Oblivious routing maps demand vectors to flows independently, but previous constructions were substantially superlinear and offered only logarithmic approximation.The paper’s framework uses oblivious routing as a route toward approximate maximum-flow algorithms.
The iterative scheme: Non-Euclidean gradient descent.
The paper replaces Euclidean gradient steps with updates defined by an arbitrary norm, using the ℓ∞ geometry to address the mismatch between electrical-flow methods and congestion objectives. This reduces iteration bounds at the cost of nonlinear minimization.
- Method: The flow formulation writes feasible flows as a fixed demand-satisfying flow plus a circulation and smooths the objective with a soft-max function.
- Motivation: The ℓ2–ℓ∞ mismatch creates an O(√m) iteration factor because spheres and cubes have substantially different sizes.
- Method: Non-Euclidean gradient descent chooses directions by optimizing a local linearization over the unit ball of an arbitrary norm rather than an Euclidean sphere.
- Method: Using the ℓ∞ norm can yield a much smaller iteration bound, although each step requires solving a nonlinear minimization problem.
- Method: A linear oblivious routing scheme with a good competitive ratio supplies the projection matrix needed for the iterative algorithm, whose iterations multiply by the scheme and its transpose.
Constructing a projection matrix.
The projection-matrix construction is supported by recursively building efficient oblivious routings through graph simplifications accompanied by low-congestion embeddings. This framework also extends to concurrent multicommodity flow, with a stated quadratic dependence on the number of commodities.
- Novelty: The non-Euclidean gradient-descent idea is presented in general terms because the authors did not find a clean prior statement or similar application.
- Constructing the routing scheme: Existing oblivious routing schemes are too slow for the iterative framework, motivating a recursive construction over successively simpler graphs.
- Constructing the routing scheme: Low-congestion embeddings in both directions let an oblivious routing on a simpler graph induce one on the original graph while transferring flows efficiently.
- Recursive reductions: The construction recursively composes vertex elimination and flow sparsification, reducing routing to simpler graphs without a large competitive-ratio increase.
- Flow sparsification: Flow sparsifiers reduce arbitrary graphs to graphs with eO(|V|) edges and provide efficient embeddings back into the original graph using electrical flows.
- Result: Combining the recursive reductions yields an efficient oblivious routing scheme and a maximum-flow algorithm.
- Multicommodity extension: The same framework applies to maximum concurrent multicommodity flow with changed norms and regularization but without substantial structural modification.
2. Preliminaries
The preliminaries establish notation for vectors, matrices, graphs, cuts, flows, demands, congestion, and operator norms. The paper focuses its congestion analysis on the infinity norm and defines running time through matrix-vector applications.
- Graphs: Graphs are undirected capacitated graphs with n vertices, m edges, nonnegative capacities, edge weights, and resistances defined as reciprocal weights.
- Fundamental Matrices: The incidence matrix B represents oriented edges, while U, W, and R are diagonal capacity, weight, and resistance matrices.
- Cuts and Subgraphs: A cut is induced by a vertex subset, whose volume sums vertex degrees; conductance describes the graph’s cut structure.
- Flows and Demands: Flow congestion is the infinity norm of capacity-scaled edge flows, and total congestion extends this notation to collections of flows.
- Flows and Demands: Demand vectors sum to zero across vertices, and a flow meets demands when its incidence-matrix divergence equals the demand vector.
- Norms and Running Time: The analysis uses operator norms and defines running time T(A) as the maximum time to apply a matrix A or its transpose to a vector.
3. Solving Max-Flow Using a Circulation Projection
The paper formulates minimum-congestion max flow as optimization over circulations and applies gradient descent under general norms, using a smooth infinity-norm surrogate and a circulation projection.
- General-Norm Gradient Descent: Gradient descent is generalized beyond Euclidean geometry using a dual norm and a fastest-increasing direction for selecting update steps.
- General-Norm Gradient Descent: The convergence analysis depends on convexity, differentiability, and a Lipschitz-continuous gradient with constant L.
- Maximum Flow Formulation: Maximum flow is written as maximizing the routed demand value subject to flow conservation and an infinity-norm capacity constraint.
- Circulation Projection: A circulation projection replaces unsuitable orthogonal projection by mapping vectors into circulation space while fixing existing circulations.
- Soft Maximum: The smooth function smaxt substitutes for the nonsmooth infinity norm, enabling differentiable optimization with a Lipschitz gradient.
- Approximate Maximum Flow Algorithm: The resulting algorithm initializes a feasible flow, performs k projected updates using P, and outputs a rescaled flow; Theorem 4 guarantees a (1 − ε)-approximate maximum flow.
4. Oblivious Routing
The paper constructs fast linear oblivious routings and connects them to circulation projections, enabling recursive graph simplification and almost-linear-time flow algorithms.
- Oblivious Routing: An oblivious routing is a fixed linear operator that maps every demand vector to a flow satisfying that demand.
- Oblivious Routing: Its competitive ratio compares worst-case congestion under the fixed routing with the minimum congestion achievable by an optimized multicommodity flow.
- Oblivious Routing: The competitive ratio equals the infinity operator norm of a capacity-scaled routing matrix.
- From Routing to Projection: An oblivious routing A yields a circulation projection I − AB^T whose scaled infinity norm is bounded by 1 + ρ(A).
- Embeddings: Embeddings preserve demands while transferring flows between graphs, and low-congestion embeddings support routing construction on simpler graphs.
- Recursive Construction: The flow sparsifier reduces a graph to at most eO(|V|) edges and supports routing flows from the sparse graph back in the original graph with low congestion.
- Recursive Construction: The recursive construction produces an oblivious routing algorithm efficiently, leading to an algorithm for approximate maximum flow under polynomial capacity ratio.
5. Flow Sparsifiers
Flow sparsifiers combine cut approximation with efficient low-congestion embeddings back into the original graph, enabling sparse-graph flow solutions to transfer to dense graphs.
- Definition and purpose: Flow sparsifiers add an efficiently computable low-congestion embedding from a cut-sparsified graph G′ back into the original graph G.This embedding transfers flows solved in G′ back to G.
- Definition and purpose: A flow sparsifier supports cut approximation, bounded embedding congestion, and nearly linear construction and embedding-application time.Its output capacity ratio may increase by at most a polynomial factor in the number of vertices.
- Definition and purpose: Flow problems can be solved on a sparse graph G′ and mapped back to G with congestion loss of at most the embedding factor α.This addresses the gap between preserving cut and flow values and constructing an actual flow in the original graph.
- Construction and analysis: For any constant ε in (0, 1), the paper constructs an (O~(n), ε, O~(1))-flow sparsifier.The construction is used to reduce dense-graph oblivious-routing problems to sparse graphs.
- Construction and analysis: The construction starts from spectral sparsification, partitions the graph into near-expanders, sparsifies induced subgraphs, and uses electrical-flow routing for low-congestion embeddings.Iterations remove a constant fraction of edges, supporting efficient recursive sparsification.
6. Removing Vertices in Oblivious Routing Construction
The oblivious-routing construction reduces graph size through partial tree embeddings, almost-j-trees, and degree elimination while controlling congestion and preserving efficient computation.
- Node reduction: Node reduction transforms a graph into t smaller graphs and reconstructs an oblivious routing on the original graph from routings on those graphs.The reduction is computed in O~(t · |E|) time.
- Node reduction: The reduction proceeds through partial tree embeddings, almost j-trees, and removal of degree-1 and degree-2 vertices.Almost j-trees contain a spanning tree whose non-tree edge endpoints involve at most j vertices.
- Partial tree embeddings: Partial tree embeddings retain selected non-tree structure while routing other edges over a spanning tree.This avoids the computational cost of embedding the entire graph into a collection of trees.
- Partial tree embeddings: A probabilistic combination of partial tree embeddings yields an oblivious routing whose competitive ratio is bounded by O~(max_i ρ(A_i) log n).The resulting routing time is the sum of the embedding and component-routing times.
- Vertex elimination: Removing degree-1 and degree-2 vertices reduces an almost j-tree to O(j) vertices while increasing congestion by only O(1).The elimination can be performed in O(m) time.
7. Nonlinear Projection and Maximum Concurrent Flow
The paper generalizes gradient descent to non-Euclidean norms and uses nonlinear projection to obtain approximate maximum concurrent flows from oblivious-routing projections.
- Nonlinear projection: The nonlinear projection problem seeks a vector near a point y within a linear subspace under an arbitrary norm.The framework assumes convex regularized objectives and a projection matrix onto the subspace.
- Nonlinear projection: NonlinearProjection outputs a vector whose norm is at most (1 + ε) times the minimum distance to the subspace.Its analysis uses an outer loop that rescales parameters and repeated gradient updates.
- Maximum concurrent flow: For k demand pairs, the method applies a multi-commodity projection to flows and uses smoothed objectives with gradient and # computations.Each iteration costs O(mk), while the regularized norm introduces the stated dependence on k and ε.
- Maximum concurrent flow: The output flows are obtained by a direct formula after solving the projected optimization problem.The paper states that the resulting flows provide an (1 − ε)-approximate maximum concurrent flow.
Appendix A. Some Facts about Norm and Functions with Lipschitz Gradient
The appendix collects basic facts about norms, dual norms, convex functions, and Lipschitz gradients used in the paper.
- Appendix A: The appendix presents foundational norm and convex-function lemmas, including properties of functions with Lipschitz gradients.It refers readers to standard references for a broader treatment.
A.1. Norms.
This section develops norm-related claims and supporting inequalities used in the paper’s analysis. It includes a Cauchy–Schwarz fact and arguments relating a norm to its transformed form.
- Norm identities: The section establishes the zero-case behavior of the transformed vector x#.When x = 0, Claim 50 implies x# = 0; the nonzero case is handled separately.
- Parameter choice: A derivative condition appears in the selection of the parameter c.Setting the derivative with respect to c to zero yields the displayed condition.
- Norm identities: The proof compares the dual norm of x with the norm of x# in both directions.One direction is stated directly, while the other uses a vector y maximizing the relevant expression.
- Supporting inequalities: The section invokes the Cauchy–Schwarz inequality as a supporting fact.
- Supporting inequalities: The dual-norm definition is used over vectors x satisfying ||x|| = 1.
A.2. Functions with Lipschitz Gradient.
This section characterizes convex functions with Lipschitz-continuous gradients through equivalent conditions and Hessian bounds. It also connects these properties to a computable Lipschitz parameter.
- Equivalent conditions: Lemma 54 states equivalence conditions for a continuously differentiable convex function.
- Hessian characterization: The section uses the first condition to derive an intermediate inequality in the proof.
- Equivalent conditions: The argument constructs φ_x(y) = f(y) − … to analyze the second condition for arbitrary x and y.
- Equivalent conditions: Adding the inequality with x and y interchanged provides a further bound.
- Hessian characterization: Lemma 55 relates Hessian bounds to the Lipschitz parameter L.It states that the relevant twice-differentiable function is convex and has a Lipschitz-continuous gradient with parameter L.
- Equivalent conditions: The proof applies the mean value theorem with a parameter satisfying 0 ≤ θ_t ≤ t.