Be the first user to complete this post

  • 0
 Add to List
Hard

506. Maximum Bipartite Matching Problem

Problem:

Given a bipartite graph, write an algorithm to find the maximum matching.

The maximum bipartite matching solves many problems in the real world like if there are M jobs and N applicants. Each applicant can do some jobs. Your task is to assign these jobs to the applicants so that maximum applicants get the job. Given the condition is one applicant will be assigned one job and vice versa.

Before we continue solving the problem, first we will understand what is bipartite matching and how we can obtain the maximum matching. If you are new to bipartite graphs, please read about it first here - Introduction to Bipartite Graphs. 

Bipartite Matching- Matching in the bipartite graph where each edge has unique endpoints or in other words, no edges share any endpoints. For Instance, if there are M jobs and N applicants. Each applicant can do some jobs. In matching one applicant is assigned one job and vice versa. See the example below.

Maximum Bipartite Matching - If we have M jobs and N applicants, we assign the jobs to applicants in such a manner that we obtain the maximum matching means, we assign the maximum number of applicants to jobs. Once a maximum match is found, no other edge can be added and if an edge is added it's no longer matching. There could be more than one maximum matching in a given bipartite graph. Below is the maximum bipartite matching of the example given above. 

Solution: 

Reduce Bipartite Matching to Flow Network: We can construct Flow network out of bipartite graph by following steps

  •  Create a source and a target vertex. 
  • Add the edges from the source vertex to all the vertices of one set( for example, all applicants) in the bipartite graph.
  • Add edges from all the vertices of another set( all jobs) in the bipartite graph to the target vertex. 
  • Mark the capacity of each edge as 1.
  • See the image where the above example is converted into a flow network.

Once the flow network is constructed we can reduce the Maximum Bipartite Matching problem to the Max Flow Network problem. (Please read about "Max Flow Problem – Introduction" before continuing reading.) Then we can use Max Flow – Ford-Fulkerson Algorithm to solve the maximum bipartite matching. 

Bipartite graph represented by an adjacency matrix, let's say it is adjMatrix[][], where the jobs will be represented by rows and applicants will be represented by columns. If an applicant x is can do jobs a, b, c then in matrix  adjMatrix[x][a]=1, adjMatrix[x][b]=1 and adjMatrix[x][b]=1, else it will be 0.

The simplest solution would be to add a row and column for source and target vertices in the adjacency matrix and follow the Max Flow – Ford-Fulkerson Algorithm to get the maximum flow or in this case, it will be maximum matching as well but this will increase the space complexity. This can be resolved considering that, given the capacities are all 1, we will either use an edge completely (sending 1 unit of flow) or not use an edge at all. Follow the steps below -

  1. Maintain an assign[] array to keep track of which job is assigned to which applicant. For instance, assign[1]=2 means job number 1 is assigned to applicant number 2.
  2. Each applicant will maintain a visited[] array to keep track of which jobs the candidate was already considered (to avoid going in loops).
  3. For each applicant do the Depth-First Search (DFS) (to find a job). 
    1. Iterate through all the jobs and for each job
      • check if applicant can do this job and applicant was never considered for this job (adjMatrix[applicant][job] == 1 && visited[job]==false), if yes then mark visited[job]==true (applicant is being considered for this job now and will not be considered again)
      • check if the job is not assigned to any other applicant (assign[job]==-1) - then assign the job to this applicant OR If the job was assigned earlier to any other applicant say 'X' earlier then make the recursive call for applicant 'X' (do another DFS) to check if some other job can be assigned applicant 'X' If that happens, assign this job to the current applicant and break the current loop 3a and check for the next applicant. and If this job cannot be assigned to this applicant then check for the next job.
  4. See the code above example for better understanding.

Output:

Maximum number of applicants that could get jobs are: 6

References - 

Related Problems: