**Hungarian algorithm** is an efficient procedure to find a maximum weight matching in a bipartite graph with parts and and a weight function Usually it is described in terms of potential functions on 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 Here we describe this point of view.

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

Otherwise, we construct a bipartite digraph by orienting all the edges in from to and the remaining edges in the opposite direction. We also construct the length function by setting for all and for all Observe that there no negative length (directed) cycles in . Indeed, any directed cycle in contains equally many edges in from and in Note that would mean that and so is not maximum among all matchings of size as whereas

Let and be subsets of resp. that are unsaturated by We find (say, using the Bellman-Ford algorithm) a minimum length directed path between and By construction of is an augmenting path for So is a matching satisfying

Claim: is maximum among all matchings of size

We’ll prove this claim below. For now, we remark that it is obvious that this procedure, repeated with taking place of will find matchings of maximum weight among all matchings of size In the end it remains to select among these at most matchings one with maximum weight.

Now let us prove the claim. It certainly holds for as the procedure will select a maximum weight edge in and will consist of this edge. So we can assume Let be a matching of size and of maximum weight. We need to show that As in the subgraph there

exists a connected component that is a augmenting path

But is a shortest augmenting path, so

On the other hand, is a matching of size and so by induction. Now as claimed. QED.

As described, we need to do less that loops of this procedure. In each loop, the Bellman-Ford dominates the complexity, so in total we need operations. In fact, we can stop as soon as we reached the situation when

Let a matching have maximum among matchings of size and any matching of size satisfy Then for any matching of size bigger than

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

In particular, the complexity above can be improved to

Tags: combinatorics, graph theory, MAS324, maths

## Leave a Reply