What Is Bipartite Matching? The Assignment Problem, Explained

You have six workers and six jobs. Not every worker can do every job, and you want to assign as many as possible. No worker gets two jobs. No job gets two workers. How many can you match?

That is bipartite matching. Finding a matching is easy. Finding the maximum one is where things get interesting.

What Makes a Graph Bipartite

A bipartite graph splits its vertices into two disjoint groups, call them L and R, where every edge goes from L to R. No edges within L. No edges within R.

The classic examples are obvious once you see them: workers and jobs, students and dorm rooms, tasks and time slots. Any situation where you're pairing two types of things under constraints maps directly onto this structure.

A matching is a subset of edges where no vertex appears more than once. In the worker/job graph, that means a valid assignment: each worker gets at most one job, each job gets at most one worker.

The maximum bipartite matching is the largest possible such assignment. Not every pair matched. Just the most pairs you can form without conflicts.

Why Greedy Order Fails

Suppose L = {Alice, Bob, Carol} and R = {Python, Java, Go}, with these skills:

Alice  →  Python, Java
Bob    →  Java, Go
Carol  →  Python, Go

Easy. Alice/Python, Bob/Java, Carol/Go. Three pairs, everyone matched. Perfect.

Now change Carol to only know Python:

Alice  →  Python, Java
Bob    →  Java, Go
Carol  →  Python

Assign Alice to Python first, and you strand Carol. The maximum matching is still three (Alice/Java, Bob/Go, Carol/Python), but a greedy algorithm that locks in assignments in whatever order it encounters them can miss it entirely. That is the specific problem bipartite matching algorithms exist to solve.

The greedy approach works great right up until it doesn't, at which point it has quietly locked you into a suboptimal corner with no way out.

Augmenting Paths: The Insight That Makes It Work

An augmenting path starts at an unmatched vertex in L, alternates between unmatched and matched edges, and ends at an unmatched vertex in R. Find one, flip every edge's status along it, and the matching gains exactly one more pair.

Here is how it plays out with the example above. You started with Alice/Python and Bob/Java. Carol is unmatched. Trace the path: Carol (unmatched) takes the unmatched edge to Python, Python is matched to Alice, Alice can reach Java via an unmatched edge, Java is unmatched in R. Path: Carol → Python → Alice → Java.

Flip: Carol/Python becomes matched, Alice/Python becomes unmatched, Alice/Java becomes matched. Now you have Carol/Python, Alice/Java, Bob/Go. Three pairs. Done.

Keep finding and flipping augmenting paths until none exist, and you have the maximum matching. No more paths means no better assignment is possible. This is the core insight behind every bipartite matching algorithm.

Kuhn's Algorithm: DFS for Each Left Vertex

The simplest implementation searches for augmenting paths with DFS. For each unmatched vertex in L, run a DFS. If you find an augmenting path, flip it. Repeat until no augmenting path exists.

def max_bipartite_matching(graph, n_left, n_right):
    # graph[u] = list of right-side neighbors of left vertex u
    match_left = [-1] * n_left
    match_right = [-1] * n_right

    def dfs(u, visited):
        for v in graph[u]:
            if visited[v]:
                continue
            visited[v] = True
            if match_right[v] == -1 or dfs(match_right[v], visited):
                match_left[u] = v
                match_right[v] = u
                return True
        return False

    result = 0
    for u in range(n_left):
        visited = [False] * n_right
        if dfs(u, visited):
            result += 1

    return result

Time complexity: O(V * E). You run DFS for each of the V left vertices, and each DFS is O(E). For dense graphs that is O(V³). Space is O(V) for the match arrays plus O(V) for the visited set per call.

This is Kuhn's algorithm. It works, and for most interview problem sizes it is fast enough.

When You Need Something Faster

For large inputs, O(V * E) is too slow. Hopcroft-Karp brings this down to O(E * sqrt(V)).

The idea: instead of finding one augmenting path at a time, find all shortest augmenting paths in a single BFS pass, then augment all of them simultaneously in a DFS phase. Shortest augmenting paths don't interfere with each other. The number of BFS phases needed is at most O(sqrt(V)), because after that the remaining paths are too long to improve the matching meaningfully.

For sparse graphs with V and E in the hundreds of thousands, Hopcroft-Karp is what you reach for. For most interview problems, Kuhn's is fine.

What This Algorithm Actually Solves

Four types of problems reduce to maximum bipartite matching.

Assignment problems. Maximize compatible pairings given constraints. Workers to jobs, students to courses, servers to requests.

Maximum independent set in bipartite graphs. By König's theorem, the minimum vertex cover in a bipartite graph equals the size of the maximum matching. From there, maximum independent set equals total vertices minus minimum vertex cover. Two optimization problems that look totally unrelated turn out to have the same answer. That is König's theorem, and it is one of the more surprising results in combinatorics.

Minimum path cover in DAGs. Cover all vertices of a DAG with the fewest vertex-disjoint paths. This reduces to maximum bipartite matching on a transformed graph.

Scheduling with resource constraints. When no two conflicting events can share a resource, the feasibility question often maps here.

Why Bipartite Matching Shows Up in Coding Interviews

Bipartite matching is not a common interview topic at most companies. It appears at a specific tier: Jane Street, Two Sigma, Google hard rounds, anything with a competitive programming flavor.

The pattern recognition is the skill. Two types of entities, constraints that forbid certain pairings, a goal to maximize assignments. When you see that structure, bipartite matching should surface. The interviewer is not expecting you to implement Hopcroft-Karp from scratch in 45 minutes. They want to see that you can name the shape of the problem.

LeetCode 1349 (Maximum Students Taking Exam) uses bitmask DP rather than explicit matching, but its underlying structure is bipartite. The minimum spanning tree and union-find do not help here, regardless of how tempting they feel.

The concepts you need before tackling matching problems: comfort with what bipartite graphs are, fluency with DFS on graphs, and familiarity with BFS vs DFS tradeoffs. The algorithm builds directly on those.

How to Walk Through It in an Interview

Model the graph first. State explicitly which vertices are on the left, which are on the right, what the edges represent. This is where candidates lose time, staying vague when they should be concrete about the structure.

Then give the algorithm at a high level: find augmenting paths iteratively using DFS, flip matched and unmatched edges along each path, stop when none remain.

Then give the complexity. O(V * E) for Kuhn's. Mention Hopcroft-Karp as the O(E * sqrt(V)) upgrade if asked. Knowing there is a faster option, even if you can't implement it cold, signals the right depth of understanding.

If you want to practice narrating graph problems out loud under time pressure, SpaceComplexity runs voice-based mock interviews with real-time feedback on both your solution and your explanation.