Challenge: Bipartite Matchings

In this lesson, we’ll apply our maximum flow implementation to solve matching problems in bipartite graphs. Recall that an undirected graph is called bipartite if we can partition its nodes into two sets (the left and the right partition) such that there are no edges inside a partition. We learned previously how to identify bipartite graphs in the challenge lesson of the graph traversal chapter.

The maximum matching problem

Bipartite graphs can be used to formulate various kinds of matching problems. For example, assume that you are the CEO of a company and assign tasks to your employees. There are $n_1$ employees and $n_2$ ​​ tasks, but not every employee can perform each task. Your goal is to assign employees to tasks, such that the number of working employees is maximized. The assignment should be 1 to 1, meaning that every employee would only perform one task, and every task would be done by only one employee.

We can model this problem using a bipartite graph. There are $n_1$ nodes in the left partition, representing the workers, and $n_2$ nodes in the right partition, representing the tasks. We’ll draw an edge from an employee $u$ to a task $v$ if $u$ can perform the task $v$. The resulting bipartite graph might look like this: