Maximum Flow

Ford-Fulkerson, Edmonds-Karp, Bipartite Matching, Max-Flow Min-Cut

Flow Networks

Key Concepts:

  • Flow Network: Directed graph with source s, sink t, and edge capacities c(u,v)
  • Flow Properties:
    • Capacity constraint: 0 ≤ f(u,v) ≤ c(u,v)
    • Flow conservation: Flow in = Flow out (except s and t)
  • Max Flow: Maximum flow from s to t
  • Cut: Partition of vertices into S and T where s∈S, t∈T
  • Min-Cut: Cut with minimum capacity
Max-Flow Min-Cut Theorem: Maximum flow value = Minimum cut capacity

Ford-Fulkerson Method

Key Concepts:

  • Method (not specific algorithm): Framework using augmenting paths
  • Augmenting Path: Path from s to t in residual graph with available capacity
  • Residual Graph: Shows remaining capacity after current flow
  • Residual Capacity: c_f(u,v) = c(u,v) - f(u,v) + f(v,u)
  • Time Complexity: O(E·|f*|) where |f*| is max flow (depends on path-finding method)

Video Recommendations:

🎥 MIT OCW - Max Flow (47 min) 🎥 William Fiset - Ford-Fulkerson (10 min) 🎥 Reducible - Max Flow (16 min - great visualization)

Algorithm:

  1. Initialize: f(u,v) = 0 for all edges
  2. While there exists augmenting path p in residual graph G_f:
    • Find bottleneck capacity c_f(p) = min capacity along p
    • Augment flow along p by c_f(p)
    • Update residual graph
  3. Return total flow

Important Note:

Ford-Fulkerson might not terminate with irrational capacities! Use Edmonds-Karp (BFS for paths) for polynomial time: O(VE²).

Edmonds-Karp Algorithm

Key Points:

  • Specific implementation: Ford-Fulkerson with BFS for finding augmenting paths
  • Time Complexity: O(VE²) - polynomial!
  • Why BFS?: Finds shortest augmenting path (fewest edges), guarantees termination

Maximum Bipartite Matching

Key Concepts:

  • Bipartite Graph: Vertices split into two sets, edges only between sets
  • Matching: Set of edges with no shared vertices
  • Maximum Matching: Matching with maximum number of edges
  • Reduction to Max Flow:
    • Add source s connected to all left vertices (capacity 1)
    • Add sink t connected from all right vertices (capacity 1)
    • All bipartite edges have capacity 1
    • Max flow = Maximum matching size

Video Recommendations:

🎥 William Fiset - Bipartite Graph Matching (12 min)

Example Application:

Job assignment: n workers, m jobs, edges show which workers can do which jobs. Max matching = maximum number of jobs that can be assigned.

Max Flow Quick Reference

Concept Definition Complexity
Ford-Fulkerson Method using augmenting paths O(E·|f*|)
Edmonds-Karp Ford-Fulkerson with BFS O(VE²)
Max-Flow Min-Cut Max flow value = Min cut capacity -
Bipartite Matching Reduce to max flow problem O(VE²)

Interactive Max Flow Practice - Find Augmenting Paths!

Practice Ford-Fulkerson by selecting edges to form augmenting paths and computing the maximum flow.

Exercise 1: Ford-Fulkerson - Find the Maximum Flow

Instructions: Find augmenting paths from source S to sink T. Click edges in order to form a path, then submit to augment flow.

Flow Network (Capacities)
10 5 15 10 10 S A B T (0/10) (0/5) (0/15) (0/10) (0/10)
Current Path: Click edges to build a path from S to T
Current Total Flow: 0
Augmenting Paths Found: 0
Path History: None yet

Maximum Flow Solution:

Maximum Flow Value: 15

Augmenting Paths (one possible sequence):
  1. Path 1: S → A → T
    • Bottleneck capacity: min(10, 10) = 10
    • Flow after: S→A(10/10), A→T(10/10)
    • Total flow: 10
  2. Path 2: S → B → T
    • Bottleneck capacity: min(5, 10) = 5
    • Flow after: S→B(5/5), B→T(5/10)
    • Total flow: 15

Final Flow Configuration:

  • S → A: 10/10 (saturated)
  • S → B: 5/5 (saturated)
  • A → B: 0/15 (unused)
  • A → T: 10/10 (saturated)
  • B → T: 5/10 (partially used)

Why is this maximum?

The minimum cut is {S, A, B} | {T} with capacity = 10 (A→T) + 5 (B→T) = 15. By the Max-Flow Min-Cut theorem, this proves our flow of 15 is maximum.

Note: S is saturated (all outgoing capacity used), so no more flow can leave the source!

Exercise 2: Find the Minimum Cut

Instructions: After finding the maximum flow above, identify which edges form the minimum cut.

Q1: What is the capacity of the minimum cut?

A) 10
B) 15
C) 20
D) 25
Correct! The minimum cut has capacity 15, which equals the maximum flow (Max-Flow Min-Cut Theorem). The cut separates {S, A, B} from {T}, cutting edges A→T (capacity 10) and B→T (capacity 5).

Q2: Which edges cross the minimum cut?

A) S→A and S→B
B) A→T and B→T
C) S→A and A→T
D) A→B only
Correct! The minimum cut edges are A→T and B→T. These are the only edges going from the source side {S, A, B} to the sink side {T}. Their total capacity is 10 + 5 = 15.

Q3: In the residual graph at maximum flow, is there a path from S to T?

A) Yes, there is always a path
B) No, there is no path
C) Only if we use backward edges
D) Depends on the graph
Correct! At maximum flow, there is NO augmenting path from S to T in the residual graph. If there were, we could increase the flow further. This is how Ford-Fulkerson knows to stop!

Key Insights:

  • Augmenting Path: Any path from S to T in the residual graph with available capacity
  • Bottleneck: Minimum capacity edge along the path - this limits how much flow we can push
  • Residual Graph: Shows remaining capacity. After pushing flow f on edge (u,v), subtract f from forward edge, add f to backward edge
  • Termination: Algorithm stops when no augmenting path exists in residual graph
  • Max-Flow Min-Cut: The maximum flow value always equals the minimum cut capacity - this proves optimality!