Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms

1999/11/01 by Tom Leighton, Satish Rao · 833 citations
Computer Science · Mathematics · #Algorithm #Algorithms and Data Compression #Citation #Complexity and Algorithms in Graphs #Computer science #Library science #Mathematics #Numerical Methods and Algorithms #Operations research

paper · pdf · doi:10.1145/331524.331526

published in Journal of the ACM 46(6), 787-832 (Association for Computing Machinery)

openalex publication_date 1999/11/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/14

Abstract

In this paper, we establish max-flow min-cut theorems for several important classes of multicommodity flow problems. In particular, we show that for any n-node multicommodity flow problem with uniform demands, the max-flow for the problem is within an O(log n) factor of the upper bound implied by the min-cut. The result (which is existentially optimal) establishes an important analogue of the famous 1-commodity max-flow min-cut theorem for problems with multiple commodities. The result also has substantial applications to the field of approximation algorithms. For example, we use the flow result to design the first polynomial-time (polylog n-times-optimal) approximation algorithms for well-known NP-hard optimization problems such as graph partitioning, min-cut linear arrangement, crossing number, VLSI layout, and minimum feedback arc set. Applications of the flow results to path routing problems, network reconfiguration, communication in distributed networks, scientific computing and rapidly mixing Markov chains are also described in the paper.

Cited by

• Property A and duality in linear programming
• On the cover time of dense graphs
• A Subexponential Algorithm for ARRIVAL
• Estimating the Cheeger constant using machine learning
• On Convexity of Optimal Multi-Commodity Freeway Network Control
• A Tight Max-Flow Min-Cut Duality Theorem for Non-Linear Multicommodity Flows
• Deterministic Padded Decompositions and Negative-Weight Shortest Paths
• Improved Tree Sparsifiers in Near-Linear Time
• Disjoint Paths in Expanders in Deterministic Almost-Linear Time via Hypergraph Perfect Matching
• Faster Negative-Weight Shortest Paths and Directed Low-Diameter Decompositions
• Convergence to Equilibrium in Local Interaction Games and Ising Models
• Trust Region Bayesian Optimization of Annealing Schedules on a Quantum Annealer
• Efficient Approximation for Triangulation of Minimum Treewidth
• Crossing numbers of dense graphs on surfaces
• RNE: computing shortest paths using road network embedding
• Deterministic Graph Cuts in Subquadratic Time: Sparse, Balanced, and k-Vertex
• ExplaGraphs: An Explanation Graph Generation Task for Structured Commonsense Reasoning
• Finding Colorings in One-Sided Expanders
• Structure of Graphs with Locally Restricted Crossings
• Testing Markov Chains without Hitting
• Efficient Hierarchical Clustering for Classification and Anomaly Detection
• Short Schedules for Fast Flow Rerouting
• ℓ₂-norm Flow Diffusion in Near-Linear Time
• Towards Better Approximation of Graph Crossing Number
• O(log n)-Approximation Algorithms for Bipartiteness Ratio
• Decremental All-Pairs Shortest Paths in Deterministic Near-Linear Time
• Correlation Clustering for General Graphs
• Clustering on the Edge: Learning Structure in Graphs
• Towards an O(√[3]log n)-Approximation Algorithm for \sc Balanced Separator
• Provable Guarantees for Self-Supervised Deep Learning with Spectral Contrastive Loss
• Reweighted Spectral Partitioning Works: A Simple Algorithm for Vertex Separators in Special Graph Classes
• Hierarchical Forecast Reconciliation on Networks: A Network Flow Optimization Formulation
• Limits of Approximation Algorithms: PCPs and Unique Games (DIMACS Tutorial Lecture Notes)
• Expanders via Random Spanning Trees
• Vertex Sparsification for Edge Connectivity in Polynomial Time
• Simpler and Faster Directed Low-Diameter Decompositions
• Towards Tight Bounds for Spectral Sparsification of Hypergraphs
• Fast Balanced Partitioning is Hard, Even on Grids and Trees
• Fully Polynomial-Time Parameterized Computations for Graphs and Matrices of Low Treewidth
• Improved Approximation Algorithms for Minimum Weight Vertex Separators
• Approximation Algorithms for Treewidth
• Throughput Optimal On-Line Algorithms for Advanced Resource Reservation in Ultra High-Speed Networks
• Improved approximation algorithms for minimum-weight vertex separators
• Nested graph dissection and approximation algorithms
• Relations between average case complexity and approximation complexity
• Inapproximability of Treewidth and Related Problems
• Expander graphs and their applications
• Expander Decomposition with Almost Optimal Overhead
• Nearly Maximum Flows in Nearly Linear Time
• Many sparse cuts via higher eigenvalues
• A fixed-parameter algorithm for the directed feedback vertex set problem
• A new rounding procedure for the assignment problem with applications to dense graph arrangement problems
• Expander flows, geometric embeddings and graph partitioning
• Graph expansion and the unique games conjecture
• On the Unique Games Conjecture (Invited Survey)
• A Parameterized Approximation Scheme for Min k-Cut
• Improved Region-Growing and Combinatorial Algorithms for k-Route Cut Problems
• Balanced graph partitioning
• Dynamic Mobility-Aware Interference Avoidance for Aerial Base Stations in Cognitive Radio Networks
• Vermilion: A Traffic-Aware Reconfigurable Optical Interconnect with Formal Throughput Guarantees
• The Bidimensionality Theory and Its Algorithmic Applications
• A Separator Theorem for String Graphs and its Applications
• Engineering planar separator algorithms
• Spectral Graph Theory and its Applications
• Predicting direct protein interactions from affinity purification mass spectrometry data. [europepmc]
• Cutting Materials in Half: A Graph Theory Approach for Generating Crystal Surfaces and Its Prediction of 2D Zeolites. [europepmc]
• New algorithms for maximum disjoint paths based on tree-likeness. [europepmc]
• Kemeny Constant-Based Optimization of Network Clustering Using Graph Neural Networks. [europepmc]

Related

• A Tight Max-Flow Min-Cut Duality Theorem for Non-Linear Multicommodity Flows
• A New Algorithm for Multicommodity Flow
• An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations
• An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations
• Faster Approximate Multicommodity Flow Using Quadratically Coupled Flows