Bipartite Matching: An application
October 2, 2009 1 Comment
Firstly, we define the concept of a matching.
Suppose we are given a graph, G = (V, E). As the name suggests, a matching means a pairing of vertices of the graph. In other words, each vertex is “matched” to exactly one other vertex in the graph to which it had been connected by an edge in E. We say that such edges, which “match” two vertices with one another, are part of the matching.
Formally, a matching is a set of edges, such that no two edges in S are adjacent to each other. (Two edges are adjacent if share a common end-vertex.)
A matching of maximum cardinality is called a maximum matching. (Note that a graph may have more than one matching of maximum cardinality.)
Clearly, we can not get a matching having more than 3 edges for the above graph. (There are only 6 vertices; for each pair of vertices there can be at most one edge in the matching; hence there can not be a matching with greater than 3 edges.) Hence, this is a maximum matching.
We were able to pair up all vertices of G in the above example. Such a matching is called a perfect matching.
A perfect matching may not exist for many graphs.
If the graph we consider is a bipartite graph, then the matching in such a graph is termed as a bipartite matching.
Practical application of bipartite matching: Job recruitment process
Suppose there are ‘n’ companies competing to hire students from a university, and that ‘m’ students are available for hiring. Assume that each company has only one job opening, and hence can hire at most one student.
After the tests and interviews, each company shortlists certain candidates. The company sees no distinction among its shortlisted candidates, and is willing to hire any one of them to fill its opening.
It is clear how this is a problem of bipartite matching.
Let L be the set of companies, and R be the set of students.
An edge exists between, and if r is one of the candidates shortlisted by the company.
Each company can hire at most one (by our assumption; either it hires a student, or goes home empty-handed.)
Quite obviously, each student can work in at most one company (either the student is selected by one company; or goes home empty-handed.)
Hence, this is a clear case of bipartite matching between the set of companies and the set of students.
The university would certainly like to find out the maximum number of students who can get placed through this recruitment process.
In other words, the university wishes to find out the size of the maximum bipartite matching possible for the company-student graph.
There exist polynomial time algorithms for computing a maximum bipartite matching. Hence, the problem can be solved by running any of those algorithms on the given instance of the company-student graph.
Points to ponder:
1. When does a bipartite graph have a perfect matching? What is the common structure of such bipartite graphs, which enable them to have a perfect matching? In particular, there is a very interesting theorem known as Hall’s Marriage Theorem. The theorem has two parts to it: an “if” part, and an “only if” part. One of these is simple to visualize, while the other is somewhat non-intuitive. You could read up on that.
2. There is a concept of maximal matching.
A maximal matching of a graph G = (V, E) is a matching to which no other edge of E can be added without violating the matching property. (Matching property requires that all edges of a matching be non-adjacent.)
The size of this particular maximal matching of G is 2. (Unlike maximum matchings of a graph which are all of the same size, the maximal matchings of a graph can be of different sizes.)
But we can certainly do better than this in terms of getting a matching of higher cardinality.
(You can also observe that the above matching is also a perfect matching of G (all vertices are paired).)
Question: Can you find a relation between the size of a maximal matching and the size of a maximum matching. Let be the size of a particular maximal matching, and let denote the size of any maximum matching (all maximum matching are, by definition, equal in size).
We know that .
Claim: There exists a constant factor,, such that , for all possible .
(Notes: How can we get a matching of greater size using a given maximal matching? Clearly, we can not add an edge to it (by definition of maximality, the resultant set will not be a matching.) So, we need to remove an edge from the maximal matching. Suppose we remove a particular edge, . We are, in effect, freeing two vertices, and , which are available to be paired up with some other free vertices. Hence, on removing one particular edge from a maximal matching, we can hope to add at most two new edges in its place. This suggests that the size of a maximum matching is at most twice the size of a maximal matching (i.e. k = 2).
I’m not sure about the correctness of the above explanation, as it omits certain details, and may not be rigorous in terms of exploring all possible alternatives for building a maximum matching. On an informal level, this explanation might suffice.)