Bipartite Matching

A Bipartite Graph is a graph whose vertices can be divided into two disjoint (completely separate) sets $U$ and $V$, such that every edge connects a vertex in $U$ to one in $V$. There are absolutely no edges connecting two vertices within the same set.

Maximum Bipartite Matching asks: What is the maximum number of pairs we can match from Set U to Set V such that no vertex is paired more than once?

Real-Life Analogy

Think of a Job Fair.

• Set U: 5 Applicants.
• Set V: 5 Job Openings.
• Edges: Lines connecting an applicant to jobs they are qualified for. (e.g., Alice is qualified for Job 1 and Job 3. Bob is qualified for Job 2).

You are the hiring manager. You want to hire the absolute maximum number of people. If you just greedily assign Alice to Job 1, maybe Charlie was only qualified for Job 1, so now Charlie is unemployed. The goal is to mathematically find the globally optimal assignments.

Modeling it as a Network Flow Problem

Bipartite Matching might not look like a water pipe problem, but we can brilliantly model it as one!

1. Create a "Super Source" ($S$) and a "Super Sink" ($T$).
2. Connect $S$ to every applicant in Set U with a directed edge of Capacity 1.
3. Direct all the qualification edges from Set U to Set V, giving each a Capacity of 1.
4. Connect every job in Set V to the Sink $T$ with a directed edge of Capacity 1.

Why does this work?

Because the Super Source only pushes 1 unit of flow to Alice, Alice can only push 1 unit of flow to a job. This guarantees she cannot accept two jobs. Because Job 1 only accepts 1 unit of flow, it cannot hire both Alice and Charlie.

By running the Ford-Fulkerson or Edmonds-Karp Max Flow algorithm on this exact graph, the resulting Maximum Flow is exactly equal to the maximum number of people hired!

If the Max Flow is 3, then 3 people were successfully matched to jobs.

Bipartite Matching Algorithm (Hopcroft-Karp)

While modeling as Max Flow using Edmonds-Karp gives a time complexity of $O(V \times E^2)$, Bipartite Matching is such a common subproblem that a highly specialized algorithm exists for it: The Hopcroft-Karp Algorithm.

Hopcroft-Karp interleaves Breadth-First Search (BFS) and Depth-First Search (DFS) to find multiple augmenting paths simultaneously in $O(E \sqrt{V})$ time, making it significantly faster for massive matching scenarios like dating apps or ride-sharing driver assignments.

Real-World Applications

• Uber/Lyft: Set U is Drivers, Set V is Riders. Edges are created if a driver is within a 5-minute radius. Run the matching algorithm to optimally dispatch drivers.
• Tinder/Dating Apps: Optimizing potential match queues.
• Medical Residency: The National Resident Matching Program uses variations of bipartite matching (Stable Marriage Problem) to assign doctors to hospitals.