Hungarian algorithm, take 1

Hungarian algorithm is an efficient procedure to find a maximum weight matching in a bipartite graph \Gamma=(V_1\cup V_2,E) with parts V_1 and V_2 and a weight function w:E\to\mathbb{R}_+. Usually it is described in terms of potential functions on V=V_1\cup V_2, and looks quite mysterious, as it hides the origin of the procedure, that is a variation of the augmenting path method for finding a maximum (unweighted) matching in \Gamma. Here we describe this point of view.

Let M be a matching of maximum weight w(M) among all matchings of size |M|. If M is a maximum (unweighted) matching then we are done.

Otherwise, we construct a bipartite digraph D=(V,A) by orienting all the edges in M from V_2 to V_1, and the remaining edges E\setminus M in the opposite direction. We also construct the length function \ell: A\to\mathbb{R} by setting \ell(a)=w(a) for all a\in M, and \ell(a)=-w(a) for all a\in A\setminus M. Observe that there no negative length (directed) cycles in D. Indeed, any directed cycle C in D contains equally many edges in C\cap M from M and in C\setminus M. Note that \ell(C)<0 would mean that w(C\cap M)< w(C\setminus M), and so w(M) is not maximum among all matchings of size |M|, as w(C\triangle M)> w(M), whereas |C\triangle M|=|M|.

Let V_1^M and V_2^M be subsets of V_1, resp. V_2 that are unsaturated by M. We find (say, using the Bellman-Ford algorithm) a minimum length directed path P between V_1^M and V_2^M. By construction of D, P is an augmenting path for M. So M'=M\triangle P is a matching satisfying |M'|=|M|+1.

Claim: w(M') is maximum among all matchings of size |M'|.

We’ll prove this claim below. For now, we remark that it is obvious that this procedure, repeated with M' taking place of M, will find matchings of maximum weight among all matchings of size 1,2,3,\dots In the end it remains to select among these at most \min(|V_1|,|V_2|) matchings one with maximum weight.

Now let us prove the claim. It certainly holds for |M'|=1, as the procedure will select a maximum weight edge in E and M' will consist of this edge. So we can assume |M'|\geq 2. Let N be a matching of size |M'|, and of maximum weight. We need to show that w(N)\leq w(M'). As |N|=|M|+1, in the subgraph N\cup M there
exists a connected component Q that is a M-augmenting path Q.
But P is a shortest M-augmenting path, so \ell(Q)\geq\ell(P).
On the other hand, N\triangle Q is a matching of size |M|, and so w(N\triangle Q)\leq w(M), by induction. Now w(N)=w(N\triangle Q)-\ell(Q)\leq w(M)-\ell(Q)\leq w(M)-\ell(P)=w(M'), as claimed. QED.

As described, we need to do less that n=|V| loops of this procedure. In each loop, the Bellman-Ford dominates the complexity, so in total we need O(n^2|E|) operations. In fact, we can stop as soon as we reached the situation when w(M')\leq w(M).

Let a matching M have maximum w(M) among matchings of size |M|, and any matching M' of size |M'|=|M|+1 satisfy w(M')\leq w(M). Then w(N)\leq w(M) for any matching N of size bigger than |M|.

Proof. Suppose N be a matching contradicting the claim, minimal w.r.t. |N\triangle M|. Let D be the digraph constructed from \Gamma, w, and M as above. The connected components of |N\triangle M| induce oriented cycles and directed paths on D. Each such component will have a nonnegative total length, as neither there can be a negative length cycle in D (see above) nor can there be a negative length M-augmenting path (otherwise we can construct M'). But this implies that w(M)\geq w(N), contradiction. QED.

In particular, the complexity above can be improved to O(n|M||E|).

Advertisements

Tags: , , ,

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


%d bloggers like this: