It is well known that the proof of some prominent results in mathematics took a very long time — decades and even centuries.  The first proof of the Micali-Vazirani (MV) algorithm, for finding a maximum cardinality matching in general graphs, was recently completed — over four decades after the publication of the algorithm (1980). MV is still the most efficient known algorithm for the problem. In contrast, spectacular progress in the field of combinatorial  optimization has led to improved running times for most other fundamental problems in the last three decades, including bipartite matching and max-flow.

The proof of the MV algorithm requires an elaborate, new theory of alternating paths and blossoms, from the perspective of  minimum length paths. This talk will give an insight into this theory as well as the algorithm.

This talk is based on this paper.