Hungarian Maximum Matching Algorithm

The Hungarian algorithm finds a maximum independent edge set on a graph. The algorithm starts with any matching  and constructs a tree via a breadth-first search to find an augmenting path, namely a path  that starts and finishes at unmatched vertices whose first and last edges are not in  and whose edges alternate being outside and inside . If the search succeeds, the symmetric difference of  and the edges in  yields a matching with one more edge than . That edge is added, and then another search is performed for a new augmenting path. If the search is unsuccessful, the algorithm terminates and  must be the largest-size matching.

As an added bonus, the tree data provides a vertex cover.

If the tree search is unsuccessful, as it is at the end, then the size of the vertex cover is the same as the size of the matching, which proves that the final matching has the maximum size possible.

REFERENCES

Brualdi, R. A. Introductory Combinatorics, 4th ed. New York: Elsevier, 1997.

Cook, W. J.; Cunningham, W. H.; Pulleyblank, W. R.; and Schrijver, A. Combinatorial Optimization. New York: Wiley, 1998.

Hopcroft, J. and Karp, R. "An  Algorithm for Maximum Matching in Bipartite Graphs." SIAM J. Comput. 2, 225-231, 1975.

 Wagon, S. "The Hungarian Maximum Matching Algorithm." http://demonstrations.wolfram.com/TheHungarianMaximumMatchingAlgorithm/.West, D. B. Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, pp. 127-130, 2000.

Zwick, U. "Lecture Notes on: Maximum Matching in Bipartite and Non-Bipartite Graphs." http://www.cs.tau.ac.il/~zwick/grad-algo-0910/match.pdf. 2009.