Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

graph

What is the maximum bipartite matching problem?

Izza Mujeeb

Grokking Modern System Design Interview for Engineers & Managers

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, P1P1 and P2P_2 are assigned T2T2, where T2T2 can only be executed by P1P1 or P2P2, 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 MM will be a bipartite graph if it can be effectively decomposed into two disjoint sets, say YY and ZZ, where vertices of the same sets are not to be connected, and edges can only exist between the vertices of YY and ZZ.

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 YY and YY or ZZ and ZZ), 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 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;
}
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

Grokking Modern System Design Interview for Engineers & Managers

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.

Keep Exploring