U.C.
Berkeley — CS270: Algorithms Lecture 3
Professor Vazirani and Professor Rao
Lecturer: Umesh Vazirani Last revised March 20, 2012
Lecture 3
1 Maximum Weighted Matchings
Given a weighted bipartite graph G = (U, V, E) with weights w : E → R the problem
is to find the maximum weight matching in G. A matching is assigns every vertex in U
to at most one neighbor in V , equivalently it is a subgraph of G with induced degree at
most 1. By adding edges with weight 0 we can assume wlog that G is a complete bipartite
graph. Finding maximum cardinality matchings is a standard problem in undergraduate
algorithms.
1.1 Maximum Matching
An augmenting path is a path whose endpoints are unmatched vertices that alternates
between unmatched and matched edges. A matching has maximum cardinality if and only
if there are no augmenting paths.
Augmenting paths can be found by a breadth first search starting at unmatched vertices
in U alternating between unmatched and matched edges. If the breadth first search reaches
an unmatched vertex in V we have found an augmenting path and can extend the matching.
1.2 Maximum Weighted Matchings
The maximum weight matching problem is solved using the primal dual framework, it is
useful to think in terms of upper bounds on the weight of a matching. The sum of the
weights of the maximum weight edges incident on U is clearly an upper bound on the
weight of a matching. The bound is not tight, for the path of length 3 where the middle
edge has weight 2 and the others have weight 1 the upper bound is 3 while the maximum
weight of a matching is 2.
The upper bound is generalized by assigning prices p(u) to the nodes, such that the sum
of the prices of the endpoints exceeds the weight of an edge, that is for all edges (u, v) we
have p(u) + p(v) ≥ w(u, v). The sum of the prices over all the vertices is an upper bound
on the weight of a matching,
X X X
w(u, v) ≤ p(u) + p(v) = p(w) (1)
(u,v)∈M (u,v)∈M w∈G
This form of upper bound can be made tight for the length 3 path, by assigning 1 to the
endpoints of the path.
The best upper bound on the weight of a matching using this approach corresponds to
the weight cover for G, that is the smallest sum over prices such that all edges are covered;
p(u) + p(v) ≥ w(u, v). The weight of a any cover is greater than the weight of a matching,
this fact will be crucial for designing the algorithm.
Notes for Lecture 3: 2
The primal dual algorithm maintains a cover and iteratively reduces the weight of the
cover by finding maximum matchings on tight edges,
1. The initial cover is chosen to be p(u) = maxu∈e w(e), p(v) = 0, this is a cover as
p(u) + p(v) ≥ w(u, v) is true for all edges.
2. The edges (u, v) for which p(u) + p(v) = w(u, v) are called the tight edges. Compute a
maximum matching M on the tight edges, if the matching M has size |U |, the problem
is solved as we found a matching and cover having the same weight.
3. Perform a breadth first search starting from unmatched vertices in U alternating
between unmatched and matched edges. Let U 0 and V 0 be the vertices in U and V
that are reachable in this manner.
The augmenting path characterization of the maximum matching shows that there is
no tight edge between U 0 and V \V 0 . Let δ be the minimum excess over edges between
U 0 and V \ V 0 .
4. Update the prices by setting p(u) → p(u) − δ for u ∈ U 0 and p(v) → p(v) + δ for
v ∈ V 0 . The new prices form a cover due to the choice of δ and the edges in the
maximum matching continue to be tight.
The total price has decreased due to this step as |U 0 | > |V 0 |, this follows as V 0 consists
of matched vertices and the neighbors of these vertices belong to U 0 . At least one edge
between U 0 and V \ V 0 becomes tight for every update. Repeat step 2 with the new
set of tight edges.
Analysis: Progress is made as the size of the maximum matching over tight edges
is monotonically increasing. With some data structures, we can ensure that the size of
the matching increases in O(m log n) time. Thus, in time O(nm log n) we have a perfect
matching and a corresponding feasible price function of the same value. That is, we have a
maximum weight matching.
1.3 Maximum Matching Game.
This solution was rather clever, standard tools can be applied by framing the maximum
weighted matching problem as a two player zero sum game. This formulation can be found
in the homework.
The maximum fractional matching problem is a relaxation of the maximum matching.
The two values can differ in general, but for bipartite graphs they are equal. We include a
proof for completeness.
Claim 1
In a bipartite weighted graph, there exist a maximum matching with weight equal to the
weight of the maximum fractional matching.
Proof: The proof strategy is to start with a maximum weight fractional matching F and
construct an “integer” matching from it with the same value. Remember that a maximum
fractional
P P for a graph G = (V, E) is a vector (xe )e∈E such that: xe ∈ [0, 1], ∀v ∈ V
matching
xe ≤ 1, and e xe we is maximized.
e3v
Notes for Lecture 3: 3
In particular, a maximum “integer” matching is when xe ∈ {0, 1}. It is sufficient to show a
procedure to construct a matching F 0 with more integer xe ’s than F. Then, repeating this
procedure enough times one obtains an integer matching.
Let H = (V, E 0 ) be a subgraph of G where E 0 = {e ∈ E : xe 6∈ {0, 1}}. If H has no edges
we are done. Otherwise, suppose that H has a cycle C = (v1 , v2 , ..., vk , v1 ). Since H is
also bipartite, then C has even length. Let = min{min{xe , 1 − xe }}, and let us build the
e∈C
fractional matchings (x0e ) and (x00e ) as follows:
0 x(vi ,vi+1 ) + if i is odd
x(vi ,vi+1 ) =
x(vi ,vi+1 ) − if i is even.
x(vi ,vi+1 ) + if i is even
x00(vi ,vi+1 ) =
x(vi ,vi+1 ) − if i is odd.
For every vertex in C we are adding and Psubtracting ,Pso the conditions for the fractional
matching are not violated. Moreover, e xe we = 12 ( e x0e we + e x00e we ) , which implies
P
that both matchings (x0e ) and (x00e ) are also optimal. But one of (x0e ) or (x00e ) has more
integer coordinates than (xe ). Then we may assume that H has no cycles.
In that case, let P = (v1 , v2 , ..., vk ) be the longest path in H. For any edge e incident to v1
(or vk ,) xe = 0, otherwise P is not the longest path, H has a cycle, or the edge (v1 , v2 ) (or
(vk−1 , vk )) is not possible. We construct the matchings (x0e ) and (x00e ) exactly as before, and
we notice that P needs to be of even length; otherwise (xe ) is not optimal. By a similar
analysis, (x0e ) and (x00e ) are also optimal, and one of them has more integer coordinates than
(xe ). This concludes the proof. 2