What is the maximum bipartite matching problem?

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$ .

Click here to learn about bipartite graphs.

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.


#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 one
bool 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 graph
int 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 code
int 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;
}

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.

Free Resources

License: Creative Commons-Attribution-ShareAlike 4.0 (CC-BY-SA 4.0)