MaximumWeightedMatching

28 June 2011 (Source codes (in c#) and additional readings attached)

Given a bipartite graph G(X, Y, E), where X= {x1, x2, … xn}, Y = {y1, y2, … yn} and E is a set of weighted edges connecting X and Y, find out the maximum weighted matching between X and Y. Every X is matched to only one Y. Every Y is matched to only one X.

Step 1.

Initialize labels of X. L(x) = max{weight(x, y)}, for all y in Y

Initialize labels of Y. L(y) = 0, for each y in Y

The purpose is to give initial labels guaranteeing that L(x)+L(y) >= weight(x, y).

Step 2.

Initialize Equality Graph.

Equality Graph EG is a sub graph of the original graph G. EG =(X, Y, E’), where E’ contains only edges (x, y) that satisfies L(x)+L(y) = weight(x, y). So EG contains all nodes from X and Y, but just some of the edges from E.

Step 3.

Initialize a matching between X and Y in EG. (Note: the mapping in EG, not G)

Just arbitrarily map an x to y if there is an edge (x,y) in EG.

Step 4. (Main Loop)

While (not totally matched yet)

{

Step 4.1

Check if there is any augmenting path in EG for the current matching. The nodes in X visited during the check is recorded in S. The nodes in Y visited during the check recorded in T.

IF(no augmenting path found)

{

Step 4.2

Adjust the labels of X and Y.

Find out the minimum L(x) + L(y) – weight(x, y), ( x in S, and y in Y-T).

Then for any x in S, L(x) = L(x) - the min value; for any y in T, L(y)+= the min value.

The purpose is to introduce new edges into EG while keeping all the old edges in EG.

                        GO TO Step 2. (reconstruct EG and matching)

}

ELSE // an augmenting path is found

{

            Enlarge the matching.

            This is done by flipping the augmenting path.

}

}

Step 4.1. IN DETAILS:

Starting from all free (unmatched) nodes in X, conduct a breath-first search in EG.

If any free node in Y is discovered, an augmenting path is found and returned.

If a matched node in Y is discovered, just put it into the search queue.

When searching from Y to X, only nodes matched with the current y node are considered and they are put into queue. The purpose is to get an alternating path (which can form an augmenting path). All previously visited nodes are ignored.

An alternating path consists of (unmatched edge, matched edge, unmatched edge, ..., matched edge, unmatched edge).

The basic idea is:

Staring with an initial equality graph and matching.

Find the maximum matching in the equality graph (by finding augmenting path).

If the matching is perfect, return.

Otherwise, decrease the labels properly and start search again.

Because more and more edges are added to the quality graph, eventually it’s maximum matching contains all X Y nodes.

And it is proved that a perfect matching in a equality graph is equal to the maximum weighted matching in the original graph.

Additional readings:

(1)   HKU-handouts give a general idea of the algorithm. But my implementation is slightly different in finding augmenting path. The condition Nl(S) = T in the handout is actually for determining if it can further extend the breath-firth search, in order to determine if an augmenting path exists or not.

In my algorithm, I just conduct the search for augmenting path until no free nodes in Y can be found. Then all nodes visited during the search are assigned to S and T according to they belong to X or Y.

The way to update labels is exactly the same.

(2)   UCB-handouts are very good for understanding the alternating path / augmenting path and why an augmenting path can enlarge a matching.

(3)   Toronto-handouts are good for understanding why using labels (cover) to find out the maximum weighted matching. They are actually the same thing. Minimum weighted cover (label) == Maximum weighted matching.