Network Flow & Matchings

A foundational framework for modeling optimization problems on networks, where resources flow from sources to sinks through capacity-constrained edges. The elegant duality between maximum flows and minimum cuts, and the connection to matching problems, makes this one of the most versatile algorithmic paradigms.

Intermediate to Advanced

• Basic max-flow algorithms: Intermediate
• Min-cut applications: Intermediate
• Bipartite matching: Intermediate
• General matching (blossom algorithm): Advanced
• Min-cost flow: Advanced

The skill that solves everything: Flow problems aren’t just about water in pipes—they’re about modeling resource constraints and optimization. Once you see the world through the lens of flows, you discover network structure everywhere:

• Supply chain logistics (moving goods from warehouses to customers)
• Image segmentation (computer vision problems as graph cuts)
• Airline crew scheduling (assigning pilots to flights)
• Baseball elimination (proving teams can’t make playoffs)

War Story - Baseball Elimination: In 1996, Wayne Winston used network flow algorithms to prove mathematically when baseball teams were eliminated from playoff contention—sometimes weeks before it was obvious. The insight: model each game as capacity flowing through a network. When the max-flow can’t distribute enough wins to a team, they’re mathematically eliminated. This transformed sports analytics and demonstrated how abstract graph theory solves real scheduling problems.

War Story - Image Segmentation Revolution: The graph-cut approach to image segmentation (Boykov-Jolly, 2001) formulated computer vision as a min-cut problem. Pixels are nodes, similarity is capacity, and the cut separates foreground from background. This algorithm became the foundation for Photoshop’s “Magic Wand” tool and modern medical image analysis. A single flow algorithm changed how millions edit photos daily.

1. Ford-Fulkerson Method - Augmenting paths framework for max-flow
2. Edmonds-Karp Algorithm - BFS-based augmenting paths, O(VE²)
3. Max-Flow Min-Cut Theorem - Fundamental duality
4. Bipartite Matching - Reduction to max-flow

5. Dinic’s Algorithm - Blocking flows approach, O(V²E)
6. Push-Relabel/Preflow-Push - Different paradigm from augmenting paths
7. Edmonds’ Blossom Algorithm - General graph matching
8. Min-Cost Max-Flow - Combining flow with edge costs
9. Gomory-Hu Trees - Computing all-pairs min-cuts efficiently

• Required:

  • Graph theory fundamentals (paths, cuts, connectivity)
  • BFS/DFS traversal algorithms
  • Basic optimization intuition

• Helpful:

  • Linear programming (for understanding duality)
  • Proof techniques for correctness arguments
  • Understanding of greedy algorithms

Setup: A city has multiple evacuation routes from the danger zone to safety shelters. Each road has a maximum capacity (vehicles per hour). What’s the maximum evacuation rate?

Naive approach: Try different route combinations manually. Gets intractable with many roads.

Flow insight: Model as a network:

• Source = danger zone
• Sink = safety
• Edges = roads with capacities
• Find maximum flow from source to sink

The revelation: The evacuation rate is limited not by individual roads, but by the minimum cut separating danger from safety. The max-flow min-cut theorem tells us these are equal!

Generalization: Any problem about “maximum throughput with bottlenecks” is likely a flow problem.

Setup: You’re organizing a coding competition with n teams and m mentors. Each team lists mentors they’re compatible with. Can you assign each team exactly one mentor (with no mentor taking more than one team)?

Naive approach: Try different assignments by hand. Backtrack when stuck.

Flow insight: Create a bipartite graph:

• Left nodes = teams
• Right nodes = mentors
• Edges = compatibility
• Add super-source → all teams (capacity 1)
• Add all mentors → super-sink (capacity 1)
• Run max-flow

The insight: A maximum flow of n means a perfect matching exists! The integrality of flows gives integer solutions automatically.

Setup: You have a network where you want to send 5 units of flow from S to T. You find a path that can take 3 units and greedily push flow. Now what?

The problem: Your greedy choice might block better solutions!

The solution: Ford-Fulkerson allows backward edges in the residual graph. You can “undo” previous flow choices by pushing flow backwards. This is counterintuitive but essential.

The insight: Sometimes solving optimization problems requires reversibility—the ability to undo suboptimal choices. This appears throughout algorithm design.

Matching in real life: The matching problem isn’t just about graphs—it’s about pairing people to opportunities:

• Medical residents to hospitals (NRMP, affects 40,000+ doctors annually)
• Students to schools (school choice algorithms in NYC, Boston)
• Kidney donors to recipients (saves thousands of lives)

The algorithmic insight: stability matters. The Gale-Shapley algorithm guarantees no resident-hospital pair would both prefer each other over their assignments. This prevents the system from unraveling.

Bottleneck identification: Max-flow teaches us to think about system bottlenecks. In project management, operations, or personal productivity, identifying the “minimum cut” that limits throughput guides where to invest resources. Don’t optimize non-bottleneck components!

Statement: The maximum flow value from s to t equals the minimum capacity of any s-t cut.

Why it matters: This duality is profound:

• Gives a certificate of optimality (found a cut with capacity = flow value? You’re done!)
• Connects local improvements (augmenting paths) to global structure (cuts)
• Generalizes to many other optimization problems via LP duality

Statement: A bipartite graph has a perfect matching iff every subset S of left vertices has |N(S)| ≥ |S| neighbors.

Why students care: Provides a simple necessary and sufficient condition for matchings to exist. Shows the power of combinatorial characterizations.

Statement: If capacities are integers, max-flow algorithms find integer flows.

Why it matters: This is not obvious! Many LP relaxations don’t have this property. It explains why flow reductions give integral solutions to matching problems.

• Kleinberg & Tardos §7 - Exceptional motivation, the baseball elimination story, clear proofs
• Skiena §6.5 - War stories including bipartite matching applications
• Erickson Chapter 10-11 - Network flows and applications with excellent exercises
• CLRS Ch 26 - Comprehensive reference with push-relabel algorithms
• Schrijver’s “Combinatorial Optimization” - Advanced, encyclopedic treatment

• Stanford CS261 (Moses Charikar) - Emphasizes LP connections and duality
• MIT 6.854J - Advanced flow algorithms and recent results
• CMU 15-850 - Includes spectral approaches to flow problems

• Boykov-Jolly (2001) - “Interactive Graph Cuts for Optimal Boundary & Region Segmentation of Objects in N-D Images”
• Edmonds (1965) - “Paths, Trees, and Flowers” (blossom algorithm, beautiful combinatorics)
• Orlin (2013) - “Max flows in O(nm)” time, recent breakthrough

• Linear Programming: Max-flow is a special LP; duality theory generalizes min-cut theorem
• Matching Theory: Bipartite matching via flow; general matching needs blossom algorithm
• Graph Connectivity: Min-cuts characterize connectivity; Gomory-Hu trees structure all cuts
• Approximation Algorithms: Multicommodity flow relaxations for cut problems
• Online Algorithms: Online bipartite matching (Karp-Vazirani-Vazirani algorithm)
• Spectral Methods: Electrical flow analogy connects to Laplacian solvers

1. Baseball Elimination Analyzer

   • Scrape current MLB standings
   • Build flow network for each team
   • Compute elimination dates
   • Visualize the flow/cut proving elimination
   • Compare to actual playoff timeline

2. Image Segmentation Tool

   • Implement graph-cut segmentation
   • User marks foreground/background seeds
   • Build pixel similarity graph
   • Compute min-cut for segmentation
   • Compare to ML-based approaches

3. Matching Market Simulator

   • Implement Gale-Shapley stable matching
   • Simulate medical residency matching
   • Analyze strategic behavior (manipulation)
   • Compare stability vs. efficiency tradeoffs
   • Visualize preference lists and outcomes

4. Flow Algorithm Race

   • Implement Ford-Fulkerson, Edmonds-Karp, Dinic, Push-Relabel
   • Benchmark on random graphs, grid graphs, bipartite graphs
   • Analyze when each performs best
   • Visualize augmenting paths vs. blocking flows
   • Explore gap between theory (worst-case) and practice

5. Supply Chain Optimizer

   • Model multi-stage supply chain as flow network
   • Warehouses, distribution centers, stores
   • Add costs for min-cost flow
   • Handle demand constraints
   • Visualize flow distribution

3-5 lectures depending on depth

• 2 lectures: Ford-Fulkerson, max-flow min-cut, bipartite matching
• 3 lectures: + Dinic or Push-Relabel, applications (baseball, image segmentation)
• 4 lectures: + Min-cost flow, general matching
• 5 lectures: + Advanced topics (Gomory-Hu trees, recent algorithms)

1. “Flow must follow one path from source to sink”

   • False! Flow can split and recombine. It’s about net flow conservation at nodes.

2. “Augmenting paths must increase flow”

   • False! They increase the flow value, but might decrease flow on some edges (via backward edges in residual graph).

3. “Bipartite matching needs special algorithms”

   • False! It’s just max-flow on a constructed network. But specialized algorithms can be faster.

4. “Min-cut is NP-hard like most cut problems”

   • False! Min s-t cut is polynomial via max-flow. But min k-cut for k > 2 gets harder.

5. “Flow algorithms only work on directed graphs”

   • Partially false. You can model undirected edges as bidirectional, though some subtleties arise.

Traditional (banking model):

“Here’s the definition of a flow network. Here’s the Ford-Fulkerson algorithm. Here’s the max-flow min-cut theorem. Prove it.”

Problem-posing approach:

“You need to evacuate a city as fast as possible. Roads have capacity limits. How do you find the bottleneck that limits evacuation? What if you could ‘undo’ earlier routing decisions? Let’s explore this together and discover why the bottleneck (min-cut) equals the maximum evacuation rate (max-flow)…”

The difference: Students discover why flow networks matter and why algorithms need features like residual graphs. The math formalizes intuitions they’ve already developed.

Curriculum placement:

• Week 6-8 for graduate courses (after graph fundamentals, before approximation)
• Mid-semester for advanced undergraduate

Prerequisites check: Students need solid graph theory (BFS/DFS, connectivity) and proof maturity. Bipartite matching is a good “easy win” to build confidence before general flows.

Why mid-sequence: Flows integrate multiple earlier concepts (graphs, optimization, duality) and set up approximation algorithms and LP formulations that come later.

Relationship to other topics:

• After: Graph traversal, shortest paths (provides graph foundation)
• Before: Approximation algorithms (uses flow relaxations), linear programming (flows are special LPs)

Ready for students? ✓ Yes - comprehensive motivation from sports to image processing, clear progression from intuition to algorithms to theory.