Hungarian Algorithm - The Algorithm in Terms of Bipartite Graphs

The Algorithm in Terms of Bipartite Graphs

During the algorithm we maintain a potential y and an orientation of (denoted by ) which has the property that the edges oriented from T to S form a matching M. Initially, y is 0 everywhere, and all edges are oriented from S to T (so M is empty). In each step, either we modify y so that its value increases, or modify the orientation to obtain a matching with more edges. We maintain the invariant that all the edges of M are tight. We are done if M is a perfect matching.

In a general step, let and be the vertices not covered by M (so consists of the vertices in S with no incoming edge and consists of the vertices in T with no outgoing edge). Let be the set of vertices reachable in from by a directed path only following edges that are tight. This can be computed by breadth-first search.

If is nonempty, then reverse the orientation of a directed path in from to . Thus the size of the corresponding matching increases by 1.

If is empty, then let . is positive because there are no tight edges between and . Increase y by on the vertices of and decrease y by on the vertices of . The resulting y is still a potential. The graph changes, but it still contains M. We orient the new edges from S to T. By the definition of the set Z of vertices reachable from increases (note that the number of tight edges does not necessarily increase).

We repeat these steps until M is a perfect matching, in which case it gives a minimum cost assignment. The running time of this version of the method is : M is augmented n times, and in a phase where M is unchanged, there are at most n potential changes (since Z increases every time). The time needed for a potential change is .