Maximum Matching in Bipartite
Graphs
In many situations we are
faced with a problem of pairing elements of two sets. The traditional example
is boys and girls for a dance, but you can easily think of more serious
applications. It is convenient to represent elements of two given sets by vertices
of a graph, with edges between vertices that can be paired. A matching
in a graph is a subset of its edges with the property that no two edges share
a vertex. A maximum matching—more precisely, a maximum cardinality matching—is
a matching with the largest number of edges. (What is it for the graph in
Figure 10.8? Is it unique?) The maximum-matching problem is the problem of
finding a maximum matching in a given graph. For an arbitrary graph, this is a
rather difficult problem. It was solved in 1965 by Jack Edmonds [Edm65]. (See
[Gal86] for a good survey and more recent references.)
We limit our discussion in
this section to the simpler case of bipartite graphs. In a bipartite graph, all the
vertices can be partitioned into two disjoint sets V and U , not necessarily of the same size, so that
every edge connects a vertex in one of these sets to a vertex in the other set.
In other words, a graph is bipartite if its vertices can be colored in two
colors so that every edge has its vertices colored in different colors; such
graphs are also said to be 2-colorable. The graph in Figure
10.8 is bipartite. It is not difficult to prove that a graph is bipartite if
and only if it does not have a cycle of an odd length. We will assume for the
rest of this section that
the vertex set of a given
bipartite graph has been already partitioned into sets V and U as required by the definition (see Problem 8
in Exercises 3.5).
Let us apply the
iterative-improvement technique to the maximum-cardinality-matching problem.
Let M be a matching in a bipartite
graph G = V
, U, E . How can we improve it, i.e., find a new matching with more edges? Obviously, if every vertex in either V or U is matched (has a mate),
i.e., serves as an endpoint of an edge in M, this cannot be done and M is a maximum matching. Therefore, to have a
chance at improving the current matching, both V and U must contain unmatched (also called free)
vertices,
i.e., vertices that are not inci-dent to any edge in M. For example, for the matching Ma = {(4, 8), (5, 9)} in the graph in Figure 10.9a, vertices 1, 2, 3, 6, 7, and 10 are free, and vertices 4, 5, 8, and 9 are matched.
Another obvious observation
is that we can immediately increase a current matching by adding an edge
between two free vertices. For example, adding (1, 6) to the matching Ma = {(4, 8), (5, 9)} in the graph in Figure 10.9a yields a larger
matching Mb = {(1, 6), (4, 8), (5, 9)} (Figure 10.9b). Let us now try to find a
matching larger than Mb by matching vertex 2. The only way to do this would be to include
the edge (2, 6) in a new matching. This
inclusion requires removal of (1, 6), which can be compensated by
inclusion of (1, 7) in the new matching. This new matching Mc = {(1, 7), (2, 6), (4, 8), (5, 9)} is shown in Figure 10.9c.
In general, we increase the
size of a current matching M by constructing a simple
path from a free vertex in V to a free vertex in U whose edges are alternately in E − M and in M. That is, the first edge of the path does not
belong to M, the second one does, and so
on, until the last edge that does not belong to M. Such a path is called augmenting with respect
to the matching M. For example, the path 2, 6, 1, 7 is an augmenting path with respect to the
matching Mb in Figure 10.9b. Since the length of an
augmenting path is always odd, adding to the matching M the path’s edges in the odd-numbered positions
and deleting from it the path’s edges in the even-numbered positions yields a
matching with one more edge than in M. Such a matching adjustment
is called augmentation. Thus, in Figure 10.9, the matching Mb was obtained by augmentation of the matching Ma along the augmenting path 1, 6, and the matching Mc was obtained by augmentation of the matching Mb along the augmenting path 2, 6, 1, 7. Moving further, 3, 8, 4, 9, 5, 10 is an augmenting path for the matching Mc (Figure 10.9c). After adding to Mc the edges (3, 8), (4, 9), and (5, 10) and deleting (4, 8) and (5, 9), we obtain the matching Md = {(1, 7), (2, 6), (3, 8), (4, 9), (5, 10)} shown in Figure 10.9d. The
matching Md is not only a maximum matching but also perfect,
i.e., a matching that matches all the vertices of the graph.
Before we discuss an
algorithm for finding an augmenting path, let us settle the issue of what
nonexistence of such a path means. According to the theorem discovered by the
French mathematician Claude Berge, it means the current matching is maximal.
THEOREM
A
matching M is a maximum matching if and
only if there exists no augmenting path with respect to M.
PROOF
If an
augmenting path with respect to a matching M exists, then the size of the matching can be increased by
augmentation. Let us prove the more difficult part: if no augmenting path with
respect to a matching M exists, then the matching is
a maximum matching. Assume that, on the contrary, this is not the case for a
certain matching M in a graph G. Let M∗ be a maximum matching in G; by our assumption, the number of edges in M∗ is at least one more than
the number of edges in M, i.e., |M∗| > |M|. Consider the edges in the
symmetric difference
⊕ M∗ = (M − M∗) ∪ (M∗ − M), the set of all the edges that
are either in M
or in M∗ but not
in both. Note that |M∗ − M| > |M − M∗| because |M∗| > |M| by
assumption. Let G be the subgraph of G made up of all the edges in M ⊕ M∗ and
their endpoints. By definition of a matching, any vertex in G ⊆ G can be incident to no more than one edge in M and no
more than one edge in M∗. Hence,
each of the vertices in G has degree 2 or less, and therefore every
connected component of G is either a path or an even-length cycle of
alternating edges from M − M∗ and
∗ − M. Since |M∗ − M| > |M
− M∗| and the number of edges from M − M∗ and
∗ − M
is the same for any even-length cycle of alternating edges in G
, there must exist at least one path of alternating edges
that starts and ends with an edge from
∗ − M. Hence, this is an augmenting path for the
matching M, which contradicts the assumption that no such path exists.
Our discussion of augmenting
paths leads to the following general method for constructing a maximum matching
in a bipartite graph. Start with some initial matching (e.g., the empty set).
Find an augmenting path and augment the current matching along this path. When
no augmenting path can be found, terminate the algorithm and return the last
matching, which is maximum.
We now give a specific
algorithm implementing this general template. We will search for an augmenting
path for a matching M by a BFS-like traversal of
the graph that starts simultaneously at all the free vertices in one of the
sets V and U, say, V . (It would be logical to select the smaller of
the two vertex sets, but we will ignore this observation in the pseudocode
below.) Recall that an augmenting path, if it exists, is an odd-length path
that connects a free vertex in V with a free vertex in U and which, unless it consists of a single
edge, “zigs” from a vertex in V to another vertex’ mate in U , then “zags” back to V along the uniquely defined edge from M, and so on until a free vertex in U is reached. (Draw augmenting paths for the
matchings in Figure 10.9, for example.) Hence, any candidate to be such a path
must have its edges alternate in the pattern just described. This motivates the
following rules for labeling vertices during the BFS-like traversal of the
graph.
Case 1 (the queue’s front vertex w is in V ) If u is a free vertex adjacent to w, it is used as the other endpoint of an
augmenting path; so the labeling stops and augmentation of the matching commences. The
augmenting path in question is obtained by moving backward along the vertex
labels (see below) to alternately add and delete its edges to and from the
current matching. If u is not free and connected to
w by an edge not in M, label u with w unless it has been already labeled.
Case 2 (the front vertex w is in U ) In this case, w must be matched and we label its mate in V with w.
Here is pseudocode of the
algorithm in its entirety.
ALGORITHM MaximumBipartiteMatching(G)
//Finds a maximum matching in
a bipartite graph by a BFS-like traversal //Input: A bipartite graph G = V
, U, E
//Output: A
maximum-cardinality matching M in the input graph
initialize set M of edges with some valid
matching (e.g., the empty set) initialize queue Q with all the free vertices in V (in any order)
queue Q with all the free
vertices in V (in any order)
while not Empty(Q) do
w ← Front(Q); Dequeue(Q)
if w ∈ V
for every vertex u adjacent
to w do
if u is free
//augment
M ← M ∪ (w, u)
v ← w
while v is labeled do M ← M − (v, u)
u ← vertex indicated by v’s
label;
v ← vertex indicated by u’s
label; M ← M ∪ (v, u)
remove all vertex labels
reinitialize Q with all free
vertices in V
break //exit the for loop
else //u is matched
if (w, u) ∈ M and u
is unlabeled
label u with w
Enqueue(Q, u)
else //w ∈ U (and
matched)
label the mate v of w with w
Enqueue(Q, v)
return M //current matching is maximum
An application of this
algorithm to the matching in Figure 10.9a is shown in Figure 10.10. Note that
the algorithm finds a maximum matching that differs from the one in Figure
10.9d.
How efficient is the
maximum-matching algorithm? Each iteration except the last one matches two
previously free vertices—one from each of the sets V and U. Therefore, the total number of iterations
cannot exceed n/2 + 1, where n = |V | + |U | is the number of vertices in
the graph. The time spent on each iteration is in O(n + m), where m = |E| is the number of edges in the graph. (This
assumes that the information about the status of each vertex—free or matched
and the vertex’ mate if the latter—can be retrieved in constant time, e.g., by
storing it in
an array.) Hence, the time
efficiency of the algorithm is in O(n(n + m)). Hopcroft
and Karp [Hop73] showed how the efficiency can
be improved to O(
n(n + m)) by combining several iterations into a single
stage to maximize the number of edges added to the matching with one search.
We were concerned in this
section with matching the largest possible number of vertex pairs in a
bipartite graph. Some applications may require taking into ac-count the quality
or cost of matching different pairs. For example, workers may execute jobs with
different efficiencies, or girls may have different preferences for their
potential dance partners. It is natural to model such situations by bipartite
graphs with weights assigned to their edges. This leads to the problem of
maxi-mizing the sum of the weights on edges connecting matched pairs of
vertices. This problem is called maximum-weight matching. We
encountered it under a differ-ent name—the assignment problem—in Section 3.4.
There are several sophisti-cated algorithms for this problem, which are much
more efficient than exhaustive search (see, e.g., [Pap82], [Gal86], [Ahu93]).
We have to leave them outside of our discussion, however, because of their
complexity, especially for general graphs.
Exercises 10.3
For each matching shown below
in bold, find an augmentation or explain why no augmentation exists.
2. Apply the maximum-matching algorithm to the following bipartite
graph:
a. What is the largest and what
is the smallest possible cardinality of a matching in a bipartite graph G = V
, U, E with n vertices in each vertex set V and U and at least n edges?
What is the largest and what is the smallest number of distinct
solutions the maximum-cardinality-matching problem can have for a bipartite
graph G = V , U, E with n vertices in each vertex set V and U
and at least n
edges?
a. Hall’s Marriage Theorem
asserts
that a bipartite graph G = V , U, E has a matching that matches all vertices of the set V if and only if for each subset S ⊆ V , |R(S)| ≥ |S| where R(S) is the set of all vertices adjacent to a vertex in S.
Check this property for the following graph with (i) V = {1, 2, 3, 4} and (ii) V = {5, 6, 7}.
You have to devise an algorithm that returns yes if there is a
matching in a bipartite graph G = V
, U, E that matches all vertices in V and returns no otherwise. Would you base your
algorithm on checking the condition of Hall’s Marriage Theorem?
Suppose there are five committees A, B, C, D, and E composed of six persons a, b, c, d, e, and f as follows: committee A’s members are b and e; committee B’s members are b, d, and e; committee C’s members are a, c, d, e, and f ; committee D’s members are b, d, and e; committee E’s members are b and e. Is there a system of distinct representatives, i.e., is it possible to
select a representative from each
committee so that all the selected persons are distinct?
Show how the maximum-cardinality-matching problem for a bipartite
graph can be reduced to the maximum-flow problem discussed in Section 10.2.
Consider the following greedy algorithm for finding a maximum
matching in a bipartite graph G = V
, U, E . Sort all the vertices in nondecreasing order of their degrees.
Scan this sorted list to add to the current matching (initially empty) the edge
from the list’s free vertex to an adjacent free vertex of the lowest degree. If
the list’s vertex is matched or if there are no adjacent free vertices for it,
the vertex is simply skipped. Does this algorithm always produce a maximum
matching in a bipartite graph?
Design a linear-time algorithm for finding a maximum matching in a
tree.
Implement the
maximum-matching algorithm of this section in the language of your choice.
Experiment with its performance on bipartite graphs with n vertices in each of the vertex sets and
randomly generated edges (in both dense and sparse modes) to compare the
observed running time with the algorithm’s theoretical efficiency.
Domino puzzle A domino is a 2 × 1 tile that can be oriented
either hori-zontally or vertically. A tiling of a given board composed of 1 × 1 squares is covering it with dominoes exactly
and without overlap. Is it possible to tile with dominoes an 8 × 8 board without two unit squares at its
diagonally opposite corners?
Related Topics
Privacy Policy, Terms and Conditions, DMCA Policy and Compliant
Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.