The Bipartite Matching Problem (Part II)

Now that we are acquainted with the necessary background, lets try and formulate the problem with enough mathematical precision so that we can ask concrete questions and start thinking about algorithms to solve it. We set up the Bipartite Matching Problem as follows:

Let X {=} \{x_{1}, x_{2},...,x_{n}\} and Y {=} \{y_{1}, y_{2},...,y_{n}\} be two sets and let their Cartesian product X \times Y , represent the set of all possible ordered pairs of the form (x,y) , where x\in X and y\in Y . Then, a matching S can be defined as a set of ordered pairs, each from X \times Y with the property that each member of X and each member of Y appears in at most one pair in S. A perfect matching is a set S’ such that each member of X and each member of Y appear in exactly one pair in S’.

Recall the definition of a bipartite graph  G = (V, E). It is an undirected graph whose vertex set can be partitioned as V = X \cup Y with the property that every edge e \in E has one vertex in X and one vertex in Y. Consequently, in the case of graph, the edges can be viewed as pairs of nodes and we say that a matching in a graph G = (V, E), is a set of edges M \subseteq E with the property that each vertex appears in at most one edge of M. A set of edges M is called a perfect matching if each vertex of the graph appears in exactly one edge of M.
The Bipartite Matching Problem is that of finding a matching in G of the largest possible of size.

As a side note, the Stable Matching Problem and the Gale-Shapley algorithm proposed to solve it, is particularly interesting too. It is in fact the original version of the current problem.

Advertisements

One comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s