Algorithms in a Nutshell

Bipartite Matching

Matching problems exist in numerous forms. Consider the following scenario. Five applicants have been interviewed for five job openings. The applicants have listed the jobs for which they are qualified. The task is to match applicants to jobs such that each job opening is assigned to exactly one qualified applicant. It may be surprising to discover that we can use Ford-Fulkerson to solve the Bipartite Matching problem. This technique is known in computer science as "problem reduction." We reduce the Bipartite Matching problem to a Maximum Flow problem in a flow network by showing (a) how to map the Bipartite Matching problem input into the input for a Maximum Flow problem, and (b) how to map the output of the Maximum Flow problem into the output of the Bipartite Matching problem.

Input/Output

Input

A Bipartite Matching problem consists of a set of 1≤i≤n elements, s_i∈S; a set of 1≤j≤m partners, t_j∈T; and a set of 1≤k≤p acceptable pairs, p_k∈P, that associate an element s_i∈S with a partner t_j∈T. The sets S and T are disjoint, which gives this problem its name.

Output

A set of pairs (s_i,t_j) selected from the original set of acceptable pairs, P. These pairs represent a maximum number of pairs allowed by the matching. The algorithm guarantees that no greater number of pairs is possible to be matched (although there may be other arrangements that lead to the same number of pairs).

Solution

Instead of devising a new algorithm to solve this problem, we reduce a Bipartite ...