Bipartite Matching via Max Flow
What You'll Learn
You'll learn how to transform a bipartite matching problem into a maximum flow problem by cleverly adding a source, sink, and unit-capacity edges.
The Core Idea
A bipartite graph has two sets of vertices where edges only connect vertices from different sets (think: jobs and applicants, or students and projects). A matching assigns edges so no vertex appears twice—like pairing each job to at most one applicant.
Here's the elegant insight: model this as a flow network!
The Construction
- Add a source vertex
sthat connects to every vertex in the left set (e.g., all applicants) - Add a sink vertex
tthat every vertex in the right set connects to (e.g., all jobs) - Give every edge capacity 1
Now the original bipartite edges go left→right, source edges go s→left, and sink edges go right→t.
Why This Works
When you run max flow on this network:
- Each unit of flow represents one matching pair
- The capacity-1 constraint ensures no vertex is matched more than once
- Flow conservation ensures each vertex gets at most one incoming and one outgoing edge
- The max flow value equals the size of the maximum matching!
Example Analogy
Imagine a hiring fair: applicants (left) can apply to jobs (right). The "hiring office" (source) sends each applicant in, and each job reports back to "HR" (sink) when filled. With capacity-1 pipes, each person gets exactly one job, and each job gets exactly one person—a perfect matching!
Key Takeaway: By adding a source, sink, and unit-capacity edges to a bipartite graph, maximum matching becomes a maximum flow problem solvable with any max flow algorithm (Edmonds-Karp, Dinic's, etc.).