Source-linked AI summary
Electrical Flows, Laplacian Systems, and Faster Approximation of Maximum Flow in Undirected Graphs
Paul Christiano, Jonathan A. Kelner, Aleksander Madry, Daniel A. Spielman, Shang-Hua Teng
TL;DR
The paper addresses the longstanding complexity barrier for approximate maximum-flow and minimum-cut computation in undirected graphs. It reduces capacity-constrained flow computation to a sequence of electrical-flow problems solved through Laplacian systems, with iterative resistance updates. The resulting algorithms break the O(n3/2) barrier and are reported as the fastest known for these problems.
Problem
Despite extensive study, O(n3/2) remained the fastest known bound for approximate maximum flow in undirected unit-capacity graphs with m = O(n) edges.
Method
The method computes electrical flows in resistor networks, increases resistances on heavily used edges, and uses Laplacian-system solvers for approximate computation.
Results
The algorithms break the O(n3/2) complexity barrier and are reported as the fastest known algorithms for approximate maximum flows and minimum cuts.
Takeaways & Limitations
The approach introduces techniques that may apply to other problems and immediately improves algorithms that use approximate undirected maximum flow as a subroutine.
Takeaways & Limitations
The paper presents extension to directed graphs and a nearly-linear-time approximate maximum-flow algorithm as future possibilities, not achieved results.
Abstract
from arXiv · showhide
We introduce a new approach to computing an approximately maximum s-t flow in a capacitated, undirected graph. This flow is computed by solving a sequence of electrical flow problems. Each electrical flow is given by the solution of a system of linear equations in a Laplacian matrix, and thus may be approximately computed in nearly-linear time. Using this approach, we develop the fastest known algorithm for computing approximately maximum s-t flows. For a graph having n vertices and m edges, our algorithm computes a (1-ε)-approximately maximum s-t flow in time \tilde{O}(mn^{1/3} ε^{-11/3}). A dual version of our approach computes a (1+ε)-approximately minimum s-t cut in time \tilde{O}(m+n^{4/3}\eps^{-8/3}), which is the fastest known algorithm for this problem as well. Previously, the best dependence on m and n was achieved by the algorithm of Goldberg and Rao (J. ACM 1998), which can be used to compute approximately maximum s-t flows in time \tilde{O}(m\sqrt{n}ε^{-1}), and approximately minimum s-t cuts in time \tilde{O}(m+n^{3/2}ε^{-3}).
1 Introduction
The paper introduces an electrical-flow approach that breaks the O(n3/2) barrier for approximate maximum-flow and minimum-cut computation in undirected capacitated graphs. Its algorithms use Laplacian-system solvers, averaging electrical flows for flow and extracting cuts from vertex potentials.
- Motivation: O(n3/2) remained the fastest known bound for approximately maximum flow in undirected unit-capacity graphs with m = O(n) edges.This bound had not improved despite 35 years of work.
- Approach: The approach reduces capacity-constrained maximum-flow computation to electrical flows in resistor networks.Each approximate electrical-flow problem can be solved in eO(m) time using Laplacian linear-system algorithms.
- Approach: Increasing an edge’s resistance in proportion to its current penalizes edges whose electrical flow violates capacity constraints.The process repeatedly recomputes electrical flows with updated resistances.
- Results: Averaging the computed electrical flows yields a (1 − ϵ)-approximately maximum s-t flow, while vertex potentials yield a (1 + ϵ)-approximately minimum s-t cut.The two outputs arise from the same iterative electrical-flow framework.
- Results: Graph smoothing and sampling techniques improve the approximate maximum-flow running time, and sparsifiers enable the corresponding cut algorithm.The paper also reports improved downstream algorithms that use approximate maximum flow as a subroutine.
- Outlook: The authors hope to extend the approach to directed graphs and eventually obtain a nearly-linear-time approximate maximum-flow algorithm.These are stated as future possibilities rather than achieved results.
2 Maximum Flows, Electrical Flows, and Laplacian Systems
The paper defines maximum flows and electrical flows, then connects electrical-flow computation to Laplacian linear systems and effective resistance and conductance.
- Maximum Flows and Minimum Cuts: A feasible s-t flow routes at most each edge's capacity, and the maximum-flow problem seeks the feasible flow with greatest value.Flow value is the net flow out of the source, equivalently the amount sent from s to t.
- Maximum Flows and Minimum Cuts: The minimum s-t cut has capacity equal to the maximum-flow value, so cut capacities upper-bound feasible flow values.This equivalence concerns objective values; obtaining a maximum flow from a minimum cut is not known to be more efficient than recomputing it.
- Electrical Flows: Electrical flow minimizes energy among all s-t flows of a fixed value, but it need not satisfy edge-capacity constraints.The approach increases resistances on heavily used edges, penalizing capacity violations.
- Electrical Flows and Laplacian Systems: Electrical flows can be computed by solving linear equations involving the incidence matrix and the graph's weighted Laplacian.The Laplacian uses conductances c_e = 1/r_e, while flow conservation is expressed through the incidence matrix.
- Effective Resistance and Conductance: For unit electrical flow, effective s-t resistance equals the flow's energy, while effective conductance is its reciprocal.The resistance also equals the potential difference between s and t for unit current.
- Approximate Electrical Flows: The electrical-flow approximation theorem computes vertex potentials and an s-t flow of prescribed value in time eO(m log R/δ) when the resistance ratio is at most R.The computed flow has energy at most (1 + δ) times that of the exact electrical flow.
3 A Simple eO
The section develops a multiplicative-weights algorithm that repeatedly calls an approximate flow oracle, then implements the oracle using electrical flows. The resulting framework yields approximate maximum-flow algorithms with stated running-time guarantees.
- Multiplicative Weights Method: The simpler algorithm uses multiplicative weights to convert a crude flow oracle into a good approximation for maximum flow.The oracle is called repeatedly as a black box, with edge weights updated between calls.
- Flow Oracle: An (ϵ, ρ)-oracle accepts a target flow value and edge weights, approximately satisfies capacity constraints, and may return “fail” when the target exceeds the maximum flow.For feasible target values, the oracle allows factor-ρ individual congestion while controlling weighted average congestion by 1 + ϵ.
- Multiplicative Weights Method: The routine increases an edge’s weight according to its congestion, emphasizing repeatedly violated capacity constraints in later oracle calls.The final flow is obtained by averaging the flows returned across iterations.
- Convergence and Complexity: Theorem 3.2 converts an (ϵ, ρ)-flow oracle with running time T(m, 1/ϵ, U) into a (1 −O(ϵ))-approximate maximum-flow algorithm.The number of iterations grows linearly with the oracle width ρ.
- Electrical-Flow Oracle: The oracle is implemented by approximating an electrical flow with resistances chosen from edge capacities and weights.Electrical-flow energy bounds control both weighted average congestion and maximum congestion.
- Electrical-Flow Oracle: The resulting implementation runs in eO(m log 1/ϵ) time for the oracle and yields the maximum-flow running-time bound stated in Theorem 3.3.The analysis bounds the ratio of the largest to smallest resistance before applying the electrical-flow procedure.
4 An eO
The improved algorithm modifies an electrical-flow oracle by permanently removing severely congested edges, then analyzes the resulting forbidden-edge set to establish correctness and improved running time.
- 4.1 The Improved Algorithm: Figure 3 demonstrates a tight obstruction: with m = Θ(k^2), an electrical flow can create oracle width Θ(m^1/2) on a direct edge.The example uses k parallel length-k paths plus one direct s-t edge; the maximum flow is k + 1.
- 4.1 The Improved Algorithm: The obstruction is fragile because removing the overloaded direct edge greatly improves electrical-flow behavior while only slightly reducing maximum-flow value.This motivates permanently removing edges that repeatedly exhibit excessive congestion.
- 4.1 The Improved Algorithm: The modified oracle removes edges whose electrical-flow congestion exceeds a threshold and permanently excludes them from future oracle calls.It repeats electrical-flow computation until every remaining edge meets the congestion bound or a failure condition occurs.
- 4.1 The Improved Algorithm: The algorithm tracks forbidden edges through a set H and returns either a flow with H or “fail” when the target value is too large.The oracle takes the graph, target flow, edge weights, and forbidden-edge set as input.
- 4.2 Analysis of the New Algorithm: The resulting theorem guarantees a feasible s-t flow of value (1 − O(ϵ))F whenever F ≤ F*.The proof bounds oracle calls through the number of iterations and forbidden edges, and uses the maintained flow and energy conditions to establish correctness.
- 4.2 Analysis of the New Algorithm: Binary search converts the target-value procedure into a (1 − ϵ)-approximation algorithm for maximum flow.The paper states this as its main theorem after establishing the improved procedure.
- 4.2 Analysis of the New Algorithm: The analysis uses effective resistance as a potential function: removing an edge that carries substantial electrical energy causes a substantial resistance change.The potential never decreases, supporting bounds on the number and total capacity of forbidden edges.
- 4.5 Approximating the Value of the Maximum s-t Flow: The approach also supports approximate minimum cuts and improves algorithms that use approximate undirected maximum flow as a subroutine.The paper notes a connection to sparsest cut through combination with Sherman’s work.
5 A Dual Algorithm for Finding an Approximately Minimum s-t Cut in Time eO
The dual algorithm repeatedly computes electrical flows, updates edge resistances from congestion, and uses the final electrical potentials to extract an approximately minimum s-t cut. Its analysis connects resistance growth and potential-based cut extraction to a near-linear-time approximation guarantee.
- Algorithm: The algorithm repeatedly computes an electrical flow, increases edge resistances according to flow, and partitions vertices by a potential cutoff to obtain a cut.It avoids the oracle abstraction, explicit forbidden edges, and averaging flows from different iterations.
- Guarantee: Theorem 5.1 and Theorem 5.8 establish a (1 + ϵ)-approximate minimum s-t cut algorithm with the section’s stated running time.The algorithm is presented in Figure 6 and can also be applied to a sparsifier.
- Potential cut extraction: A uniformly random potential cutoff yields a cut whose expected capacity is bounded by the potential differences across edges.Therefore, some cutoff produces a cut no larger than the stated potential-based bound.
- Potential cut extraction: The analysis relates effective resistance and total resistance to the capacity of the best potential cut, including approximate electrical potentials.The argument uses effective resistance bounds and Cauchy-Schwarz inequalities to control the extracted cut.
- Guarantee: If F ≥ F ∗, the algorithm returns a cut of capacity at most F/(1 −7ϵ), where F ∗ is the minimum s-t cut capacity.Combining the resistance and potential-cut lemmas gives this approximation guarantee.
A Computing Electrical Flows
Electrical-flow computation is reduced to solving a Laplacian linear system for vertex potentials. Approximate potentials are converted into a feasible s-t flow while controlling the resulting energy error.
- Laplacian formulation: The optimal vertex potentials of an electrical flow solve a linear system involving the graph’s Laplacian matrix.The resistance scaling places the Laplacian’s off-diagonal entries between −1 and −1/R.
- Approximate computation: The Koutis, Miller, and Peng algorithm provides an approximate solution to the electrical-flow computation in the stated time bound.This is the linear-algebraic subroutine used to obtain approximate potentials.
- Feasibility correction: An approximate potential vector induces a flow that may violate conservation at nonterminal vertices.The induced flow can have small amounts entering or leaving vertices other than s and t.
- Feasibility correction: The induced flow is corrected into an s-t flow by adding a flow that satisfies the residual vertex demands.A spanning tree can perform this correction while keeping the per-edge adjustment bounded by nη.
- Error control: The approximation parameters are chosen so the corrected flow’s energy remains within the required multiplicative error of the true electrical flow.The analysis imposes a condition on η and sets it using δ, n, m, and R.
- Error control: The electrical-flow energy satisfies Er(f) = F 2Reff(r), linking flow value, energy, and effective resistance.This identity is used to express the approximation guarantee in resistance terms.