PaperlayerView exact revision on arXiv

Source-linked AI summary

Navigating Central Path with Electrical Flows: from Flows to Matchings, and Back

Aleksander Madry

arXiv:1307.2205v3cs.DS

TL;DR

Exact directed unit-capacity maximum flow and minimum cut remain difficult despite extensive prior work and barriers in interior-point convergence. The paper uses central-path improvement guided by electrical flows and obtains a faster algorithm, with implications for bipartite matching.

  • Problem

    Directed maximum s-t flow and minimum s-t cut have resisted progress, while interior-point methods face a worst-case iteration barrier of Ω(m^1/2).

  • Method

    The algorithm iteratively improves a maintained near-perfect b-matching solution toward the central path using electrical flows as guidance.

  • Results

    10^7-time computation of integral maximum s-t flow and minimum s-t cut is established for directed unit-capacity graphs.

  • Takeaways & Limitations

    The result advances exact directed flow and cut algorithms and, through reductions, supports progress on maximum-cardinality bipartite matching.

  • Takeaways & Limitations

    The approach’s ℓ2-norm-based dependence on the congestion vector is best possible within this approach.

Abstract

from arXiv · show

We present an $\tilde{O}(m^{10/7})=\tilde{O}(m^{1.43})$-time algorithm for the maximum s-t flow and the minimum s-t cut problems in directed graphs with unit capacities. This is the first improvement over the sparse-graph case of the long-standing $O(m \min(\sqrt{m},n^{2/3}))$ time bound due to Even and Tarjan [EvenT75]. By well-known reductions, this also establishes an $\tilde{O}(m^{10/7})$-time algorithm for the maximum-cardinality bipartite matching problem. That, in turn, gives an improvement over the celebrated celebrated $O(m \sqrt{n})$ time bound of Hopcroft and Karp [HK73] whenever the input graph is sufficiently sparse.

1 Introduction

The paper develops a faster algorithm for exact unit-capacity directed maximum flow and minimum cut, overcoming long-standing running-time barriers and improving bipartite matching in sparse graphs. Its approach combines primal-dual interior-point methods with electrical flows and reductions between flow and matching.

  • 1.1 Our Contribution: Theorem 1.1 gives an integral maximum s-t flow and minimum s-t cut algorithm for directed unit-capacity graphs in eO(m^10/7) time.This improves the long-standing O(m min{√m, n^2/3}) bound and breaks the Ω(n^3/2) barrier for sparse directed graphs.
  • 1.1 Our Contribution: Theorem 1.2 solves maximum-cardinality bipartite matching in eO(m^10/7) time, improving the sparse-graph regime of the O(m√n) Hopcroft–Karp and Karzanov algorithms.The result follows through a well-known reduction between flow and bipartite matching.
  • 1.2 Our Approach: The core algorithm is a primal-dual method for near-perfect bipartite b-matching that follows a central path using electrical-flow computations.Its convergence analysis ties progress to the structure of the guiding electrical flows.
  • 1.2 Our Approach: The paper addresses the Ω(m^1/2) iteration barrier for interior-point methods by developing a convergence guarantee based on electrical-flow structure.The authors describe this as the first time the barrier was broken for a natural optimization problem.
  • 1.2 Our Approach: Perturbing arcs and preconditioning solutions improve electrical-flow alignment with the primal solution, enabling larger progress steps while limiting effects on final solution quality.These techniques are the technical core of the faster convergence analysis.

2 Preliminaries

This section defines flows, cuts, graph representations, and electrical flows, then describes their potential-based characterization and nearly-linear-time approximation.

  • A directed graph has vertices, arcs, and nonnegative integer capacities; m denotes the number of arcs and n the number of vertices.
  • A σ-flow assigns arc values satisfying vertex flow-conservation constraints determined by a demand vector whose entries sum to zero.Feasibility additionally requires nonnegative flows within arc capacities.
  • An s-t flow has demand vector F·χ_s,t, where F is its value; the maximum s-t flow is a feasible flow of greatest value.
  • The minimum s-t cut minimizes the capacity of a vertex cut separating s from t and is dual to maximum s-t flow.Its capacity equals the maximum flow value, and a corresponding cut can be obtained from a maximum flow.
  • Electrical σ-flows uniquely minimize resistance-weighted energy among σ-flows and can equivalently be induced by vertex potentials.The graph may be viewed as undirected with oriented edges, while directed graphs project to undirected graphs with parallel oppositely oriented edges when necessary.
  • Electrical-flow computation reduces to Laplacian-system solving, and approximate vertex potentials can be computed in eO(m log m log ε^-1) time.The approximation is measured in the Laplacian norm relative to the exact electrical-flow potentials.

3 From Flows to Matchings, and Back

The paper establishes reductions between maximum s-t flow and perfect bipartite b-matching, then develops an electrical-flow-guided primal-dual algorithm and fast rounding to obtain the desired exact solutions.

  • Flows and matchings: A simple combinatorial reduction converts maximum s-t flow into perfect bipartite b-matching, complementing the known reduction in the opposite direction.The reduction also applies to fractional instances, enabling flow rounding through matching rounding.
  • Flows and matchings: Theorem 3.1 reduces a flow instance with m arcs to balanced b-matching instances with Θ(m) vertices and 4m edges, across O(log |u|_1) capacity scales.The resulting running time is eO((m + T(Θ(m), 4m, 4|u|_1)) log |u|_1).
  • Electrical-flow algorithm: The near-perfect b-matching algorithm uses path-following interior-point ideas and electrical flows to iteratively move solutions toward near-optimality.Its convergence analysis relates progress to the structure of the guiding electrical flows.
  • Electrical-flow algorithm: Shaping, perturbing, and preconditioning the guiding electrical flows improves convergence to eO(m^10/7) time.Perturbation targets arcs that distort electrical-flow structure, while auxiliary arcs precondition the solution.
  • Rounding: Fractional b-matchings can be rounded in eO(m) time to integral b-matchings of size floor(k), and fractional flows can be rounded to integral flows of value floor(F).These procedures complete the passage from near-perfect fractional solutions to exact integral flow and matching solutions.
  • Rounding: Combining the matching algorithm, the flow reduction, and rounding yields the stated eO(m^10/7)-time algorithms for unit-capacity maximum flow and bipartite matching.The result also gives the corresponding minimum-cut algorithm through the maximum-flow setting.

4 From Maximum Flows to Perfect Matchings

This section constructs a balanced bipartite b-matching instance for a chosen integral flow value F, preserving feasibility in both directions and supporting the flow-to-matching reduction.

  • Reduction overview: The reduction solves maximum s-t flow by constructing O(log |u|_1) balanced perfect b-matching instances.The construction is an adaptation of a reduction from vertex-disjoint s-t paths to bipartite matching.
  • Reduction overview: For any integral F, a balanced b-matching instance can be built in eO(m) time so that a feasible flow of value F implies a perfect b-matching.The converse also holds: a perfect b-matching yields a feasible s-t flow of value F in eO(m) time.
  • Construction: Each original arc e becomes paired vertices p_e and q_e joined by an edge, both with demand u_e.Additional vertices and edges encode flow conservation at nonterminal vertices and connect the source and sink to arc gadgets.
  • Illustration: Figure 1 illustrates the correspondence between a directed s-t flow instance and its b-matching instance for F = 2.Arc labels represent capacities in the flow graph; vertex labels represent demands in the matching graph.
  • Construction: The resulting instance is balanced because edges incident to p_e or q_e have thickness u_e, while the remaining vertex-pair edges contribute only a bounded additional amount.The balance argument uses the thickness definition for b-matching edges.

5 Basic eO(m

The basic algorithm reduces balanced b-matching to a minimum-cost flow problem and uses central-path progress guided by electrical flows to obtain near-perfect matchings.

  • Setup: The algorithm assumes |b|_1 ≤ 2m and sparse input graphs, with m = O(n), without loss of generality after adding dummy graph copies.The dummy copies preserve the relevant asymptotic ratios while enforcing these convenient conditions.
  • Flow reduction: A b-matching instance is reduced to a minimum-cost σ-hat-flow problem on a related directed graph with an auxiliary vertex v* and length vector l-hat.The auxiliary vertex and incident arcs support and penalize initial and intermediate solutions.
  • Flow reduction: A near-optimal σ-hat-flow yields a fractional near-perfect b-matching or certifies that no perfect b-matching exists.Lemma 5.1 obtains this in eO(m-hat) time when the flow cost is within additive 1/2 of optimum.
  • Flow reduction: The extracted matching uses direct one-arc flow paths, while flow routed through v* accounts for the deficit from perfection.The cost bound limits the non-direct flow to at most 1/2 unit, yielding matching size at least |b|_1/2 - 1/2.
  • Central path: The iterative method maintains primal-dual solutions and pushes the current feasible solution along a central path toward a small duality gap.Arc importance measures ν_e are maintained at least 1 with controlled total sum.

The associated flow ˆf

The associated electrical flow guides primal and dual updates while controlling the improvement step through congestion relative to the current solution. Electrical-flow energy bounds yield step-size guarantees, but ℓ4-based analysis is needed to surpass the Ω(√m) iteration barrier.

  • Guided improvement step: The electrical flow simultaneously updates the primal flow and dual line embedding through a guided improvement step.The update preserves centering to first order, while second-order terms require controlling the step size.
  • Step-size guarantee: Theorem 5.5 computes a centered and feasible next solution whose progress measure decreases by a factor of at most 1 − δt, subject to the congestion bound.The measures remain unchanged, and the relative resistance and flow changes are bounded in infinity norm by 1.
  • Guided improvement step: The step size δt increases when the guiding electrical flow resembles the current primal solution more closely.Congestion measures how much the electrical flow differs from the current flow, and large congestion penalizes the resemblance measure.
  • Congestion and energy: Using only ℓ2-norm arguments cannot improve the Ω(√m) iteration bound, so surpassing it requires ℓ4-norm-based arguments.The paper identifies the Ω(√m) lower bound as best possible for the simpler approach.
  • Convergence: A sufficiently small step size yields an eO(√m)-iteration procedure whose final duality gap is at most 1/2, producing a near-perfect b-matching solution.The progress measure contracts geometrically over T := δ^-1 log(8√m) steps.
  • Congestion and energy: Electrical-flow energy minimization connects congestion to energy, enabling ℓ2-energy bounds to control the ℓ4 congestion norm.The electrical flow minimizes energy, and the congestion-energy relationship motivates choosing resistances to support larger steps.

6 An Improved Algorithm for Bipartite b-Matching Problem

The improved algorithm overcomes worst-case congestion barriers by carefully perturbing heavy arcs and preconditioning light arcs, improving electrical-flow behavior while preserving solution quality. These techniques yield the stated improved running-time bound and support recovery of near-perfect b-matchings.

  • Motivation: The previous worst-case step-size bound is tight when even one arc has Ω(bm^1/2) electrical-flow congestion, motivating explicit control of such arcs.A single highly congested arc can force the ℓ4 congestion norm to remain large and prevent larger improvement steps.
  • High-level approach: The algorithm massages its maintained solution to improve electrical-flow behavior while only slightly perturbing properties needed to recover a near-perfect b-matching.The two methods are designed to address different arc types while preserving the relevant primal-dual structure.
  • Perturbing heavy arcs: Perturbing heavy arcs increases their lengths and slack variables moderately instead of removing them, avoiding the drastic dual distortion caused by edge removal.The perturbation is restricted to arcs that are heavy in the primal solution.
  • Preconditioning light arcs: Preconditioning light arcs augments the graph with auxiliary arcs that improve connectivity and electrical conductance while minimally changing the original solution.The modification is applied at the beginning of each improvement phase to enforce the needed smoothness condition.
  • Correctness: The final solution preserves the required invariants, allowing recovery of a near-perfect b-matching or certification that no perfect b-matching exists.The analysis also bounds cumulative energy and arc-length increases so the invariants remain valid.
  • Convergence and running time: At most θ^-2 progress steps and eO(θ^-2 bm) stretch-boosts are needed, with each progress step reducing the potential by a factor of at least (1−δt).The resulting total time for progress steps and stretch-boosts is eO(bm^(1+2η)).

7 Electrical Flows and the Central Path

The improvement step advances a primal-dual solution along the central path using electrical flows, then restores centering and feasibility. The descent step reduces the duality-gap measure, while the centering step controls the resulting loss of centrality without undoing that progress.

  • Improvement step: Electrical flows implement a path-following improvement step that transforms a centered feasible solution into a better one.The construction is directly inspired by improvement steps in path-following methods.
  • Descent step: The descent step produces an intermediate feasible solution whose duality-gap measure decreases by a factor of at least (1−δt), but centering may deteriorate.Each of the descent and centering steps requires one electrical-flow computation and runs in eO(bm) time.
  • Descent step: Because second-order update terms disturb centering, the step size must be sufficiently small to control this deficiency.Ignoring quadratic terms would preserve centering, but those terms cannot generally be discarded.
  • Centering step: The centering step restores centrality without increasing the duality-gap measure, using another electrical flow to repair feasibility.The intermediate flow may not be feasible because some arc flows can be negative.
  • Guarantee: The repaired solution is centered and retains the descent guarantee, satisfying μ(f_t+1,s_t+1,ν_t+1) ≤ (1−δt)μ(f_t,s_t,ν_t).The analysis bounds the energy of the corrective electrical flow to establish the centrality guarantee.

8 Rounding Fractional Bipartite b-Matchings

The rounding procedure converts fractional bipartite b-matchings into integral ones while preserving nearly the full matching size. It handles perfect, non-perfect, and higher-demand cases through augmentation, splitting, and removal of integral edge copies.

  • eO(m) time suffices to round a fractional b-matching into an integral b-matching of size at least ⌊|x|1⌋.
  • Perfect fractional matchings: Fractional perfect matchings with unit demands become doubly-stochastic square matrices, enabling an integral perfect matching in eO(m) time.
  • Non-perfect matchings: Non-perfect unit-demand matchings are extended to perfect matchings by adding dummy vertices and fractionally assigning deficits to them.
  • Non-perfect matchings: Removing dummy-incident edges from the rounded perfect matching leaves a feasible integral matching with size at least ⌊|x|1⌋.
  • Higher demands: For demands above one, integral copies of edges with weight at least one are removed first, while vertices are split into unit-demand vertices for the remaining fractional matching.

A Proof of Lemma 2.1

The proof establishes an energy-based characterization by comparing feasible flows and vertex potentials. It shows that the proposed potential attains the minimum value determined by the energy of the optimal flow.

  • The proof targets the identity C∗ = 1/E∗, where E∗ denotes the energy of the distinguished flow f∗.
  • The constructed potential ˜φ attains the minimum, while the complementary calculation gives C∗ ≤ 1/E∗.
  • Together, the two inequalities yield C∗ = 1/E∗ and certify optimality of ˜φ.

B Proof of Corollary 3.4

The reduction transfers a fractional s-t flow to a fractional perfect b-matching, rounds it integrally, and maps the result back to an integral flow. A fractional flow value is handled by augmenting the graph with one unit-capacity arc.

  • An integral-valued feasible s-t flow yields a fractional perfect b-matching through the flow-to-matching reduction.
  • eO(m) time suffices to round that fractional perfect b-matching to an integral perfect b-matching.
  • The integral perfect b-matching is then used to recover an integral feasible s-t flow of the same value.
  • For non-integral flow value F, adding a unit-capacity arc from s to t raises the value to ⌈F⌉ before applying the integral procedure.

C.1 Correctness Analysis

The correctness analysis proves that the constructed bipartite b-matching instance exactly captures feasible s-t flows. It establishes both directions of the correspondence and notes that the construction also applies to fractional solutions.

  • The constructed bipartite instance has Θ(m) vertices, at most 4m edges, and total demand at most 4|u|1.
  • Flow to matching: A feasible s-t flow of value F is encoded as a perfect b-matching by assigning edge multiplicities according to flow and residual capacity.
  • Flow to matching: The encoding satisfies matching demands because flow feasibility, capacity bounds, conservation, and the flow value enforce every vertex degree.
  • Matching to flow: A perfect b-matching recovers a feasible s-t flow by setting each original arc flow equal to the multiplicity of its corresponding edge.
  • The correspondence preserves integrality or fractionality: integral flows map to integral matchings, and fractional flows map to fractional matchings, and conversely.

D.1 Proof of Lemma 5.4

The proof constructs an initial flow and measure assignment, then verifies primal-dual feasibility, bounded total measure, and centeredness with centrality 1.

  • The initial vector s0 is the all-ones vector, corresponding to assigning zero value to every vertex.
  • Unit flow and measure are assigned to arcs corresponding to the original edges, with additional assignments determined by vertex deficits rp and rq.
  • The resulting flow is verified to be a σ̂-flow, so the constructed solution is primal-dual feasible.
  • The total measure of all arcs is at most 3m̂.
  • Every arc has normalized measure 1, making the solution 0-centered with centrality μ̂(f0,s0,ν0)=1.

E.1 Proof of Lemma 6.3

The proof preserves the centrality value when modifying one arc and reduces the required bound to that arc's changed contribution, using bounded graph distances and slack embeddings.

  • The parameters satisfy (1−γ)α ≤ β ≤ (1+γ)α by Fact 5.3.
  • The transformed solution preserves centrality's reference value: μ̂(f′,s′,ν′)=μ̂(f,s,ν).
  • Because the two solutions differ only on arc e, bounding the transformed centrality reduces to analyzing arc e's contribution.
  • The remaining inequalities establish the desired bound on the changed contribution and hence the centrality estimate.
  • Every pair of vertices has directed paths in both directions using at most two arcs and length at most 4, which bounds differences in their slack embedding by 4.

E.3 Proof of Lemma 6.6

The proof bounds non-direct flow using stretched arc lengths and compares the resulting flow cost with the cost encoding a perfect b-matching.

  • All original arcs have length 1, and α-stretching only increases their lengths.
  • The non-direct flow between sp and tq is bounded by the stretched total length minus the direct-arc contribution.
  • The cost of the flow encoding a perfect b-matching can increase to at most a baseline term plus eO(m̂^(1/2−η)).
  • If the computed flow exceeded that cost, the proof would conclude that no perfect b-matching exists; otherwise, non-direct flow is at most eO(m̂^(1/2−η)).
  • Keeping only direct flow paths yields a fractional b-matching that remains near-perfect.

E.4 Proof of Lemma 6.8

The proof analyzes electrical flows under collapsed resistances, stretch-boost operations, and interior-point updates, controlling energy and centrality through flow decomposition and smoothness.

  • Electrical-flow reduction: Collapsing arcs not adjacent to P reduces the graph to P plus a single vertex w∗, with all remaining arcs incident to w∗.
  • Electrical-flow reduction: Rayleigh monotonicity compares the electrical flow under collapsed resistances with the original resistance configuration.
  • Electrical-flow reduction: The reduced graph's effective-resistance analysis uses parallel-arc resistance and lowerbounds the relevant energy contribution.
  • Energy bound: Decomposing the flow into paths and cycles bounds F by O(m̂), using the path-volume bound and the fact that cycles contribute to the duality gap.
  • Stretch-boost analysis: The proof bounds the energy change after stretch-boost using potential normalization, arc energy fractions, and smoothness across energy classes.
  • Stretch-boost analysis: For a 1-stretch, resistances on S∗ double while all other resistances remain unchanged.
  • Interior-point update: The interior-point step is analyzed by retaining vertex potentials and showing the resulting resistance-weighted sum remains controlled.

E.7 Proof of Lemma 6.12

The proof bounds how freezing changes auxiliary-arc measures and flows, then shows the algorithm tolerates approximate electrical-flow computations through perturbation and correction. These bounds support constant multiplicative flow changes and a total freezing-related measure increase of eO(m^8η).

  • Freezing effects: eO(m^8η) bounds the overall increase in measure caused by freezing across all progress steps.There are at most log θ̂^-2 contributing sets per progress step and at most θ̂^-2 = m̂^2η progress steps.
  • Auxiliary-arc flow changes: A constant bound holds for each auxiliary arc’s total multiplicative flow change during the θ̂-improvement phase.Non-freezing progress steps are bounded using Theorem 5.5, while freezing increases measure enough to prevent repeated freezing after a threshold.
  • Approximate electrical flows: The algorithm uses electrical flows for descent, centering, and checking θ̂-smoothness, with arc classification needed only approximately up to a constant factor.The relevant flows are determined by resistances from a centered, feasible primal-dual solution.
  • Approximate electrical flows: Polynomially bounded resistance ratios and bounded duality gap keep arc flows polynomially bounded in m̂.The argument rules out large flow values dominated by flow-cycles because such cycles would contribute to the duality gap.
  • Approximate electrical flows: Approximate electrical flows are acceptable when the running-time dependence on approximation error is logarithmic.Small feasibility perturbations can be corrected at the end of each θ̂-improvement step using the existing fixing procedure.
Loading 1307.2205v3…