Related Tags

graph

# What is the maximum bipartite matching problem?

Izza Mujeeb

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

### Overview

Let’s consider five processors and seven tasks. A processor can only run one task at a time, and a task can only be selected by a single processor. For example, $P1$ and $P_2$ are assigned $T2$, where $T2$ can only be executed by $P1$ or $P2$, but not both at the same time.

### Maximum bipartite matching problem

Now, what if we wanted to ensure efficiency by matching the maximum number of tasks to the maximum number of processors? This is one of the maximum bipartite matching problems, the need to match as many entities as possible, and this is where bipartite matching comes into play.

### Bipartite Graph

A graph $M$ will be a bipartite graph if it can be effectively decomposed into two disjoint sets, say $Y$ and $Z$, where vertices of the same sets are not to be connected, and edges can only exist between the vertices of $Y$ and $Z$.

### Bipartite Matching

Bipartite matching is the opting of edges in such a way that there will be no adjacent edges—no same set edges (between $Y$ and $Y$ or $Z$ and $Z$), and each edge will have unique endpoints. Therefore, the maximum matching will be the highest number of edges possible in the bipartite graph. Once this is achieved, no new matches can be added. Otherwise, the graph is no longer a bipartite graph.

Tasks (purple) can run on specific processors (yellow). Bold lines show a possible maximum matching.

### Maximum bipartite matching solution

In the above scenario, obtaining the maximum number of tasks that can be run on corresponding processors is the solution to our problem, but how do we do that exactly?

Such a problem can be solved very effectively by the Ford Fulkerson algorithm, which connects and disconnects all possible edges in the graph till the maximum match number is found, such as the highest edge count.

### C++ example

#include <iostream>#include <string.h>using namespace std;// this function recursively uses the DFS approach to find out the most optimal combination// of edge connections by adding and removing edges one by onebool isMatchingPossible(bool graph[7][5], int task, bool visited[], int assigned[]) {	for (int processor = 0; processor < 5; processor++) {		if (graph[task][processor] && visited[processor] != true) {			visited[processor] = true;			if (assigned[processor] == -99 || isMatchingPossible(graph, assigned[processor], visited, assigned)) {				assigned[processor] = task;				return true;			}		}	}	return false;}// this function returns the maximum number of matches that can be made in a bipartite graphint maximumMatching(bool graph[7][5]) {	int assigned[5], totalProcessorsAssigned = 0;	bool visited[5];	for (int processor = 0; processor < 5; processor++)		assigned[processor] = -99;	for (int task = 0; task < 7; task++) {		for (int processor = 0; processor < 5; processor++)			visited[processor] = false;		if (isMatchingPossible(graph, task, visited, assigned) == true)			totalProcessorsAssigned++;	}	return totalProcessorsAssigned;}// main codeint main(){ 	bool graph[7][5] = { {1, 0, 0, 0, 0},{1, 1, 0, 0, 0}, {0, 0, 0, 1, 0}, {0, 0, 1, 0, 0}, {0, 0, 0, 0, 1}, {0, 0, 0, 1, 0}, {0, 0, 0, 0, 1} };	cout << "The processors can run a maximum of "<< maximumMatching(graph) <<" tasks at one time." << endl;		return 0;}
Maximum bipartite matching of processors and tasks

### Explanation

In the above code, we use maximumMatching, which takes graph[7][5] that contains 7 tasks and 5 processors that run specific tasksFor example: processors 1 and 2 can run task 2. We use isMatchingPossibleA recursive function. to find the maximum possible matches.

• Line 13: We use if (graph[task][processor] && visited[processor] != true) to find an unvisited processor and mark it visited for the task passed through the function.
• Line 17: The assigned[processor] == -99 is true when the processor is not allocated. Otherwise, we call isMatchingPossible recursively to find another processor.
• Line 19: We use assigned[processor] = task, which assigns the task to the unassigned processor.
• Line 32: We use int assigned[5] to define an integer array to keep a track of which task will be assigned to which processor during the matching.
• Line 34: We use bool visited[5] to define a boolean array to keep a record of the processors visited during traversal to avoid cycles.
• Line 44: The isMatchingPossible keyword performs the DFS traversal for each task to find a possible match.

### Other real-world examples

• Jobs are assigned to a maximum number of people who are interested in specific jobs.
• One crucial case in point would be effectively matching available kidney donors to kidney transplant recipients.

### Time complexity

O(mn): Where m denotes the number of edges, while n denotes vertex count.

RELATED TAGS

graph

CONTRIBUTOR

Izza Mujeeb