A Theory of Alternating Paths and Blossoms from the Perspective of Minimum Length
本文首次完整且正确地证明了Micali-Vazirani算法，该算法是寻找一般图最大基数匹配的最有效已知算法，通过揭示底层结构中的丰富性质来实现线性时间效率。
The Micali–Vazirani (MV) algorithm for finding a maximum cardinality matching in general graphs, which was published in 1980, remains to this day the most efficient known algorithm for the problem. The current paper gives the first complete and correct proof of this algorithm. The MV algorithm resorts to finding minimum-length augmenting paths. However, such paths fail to satisfy an elementary property, called breadth first search honesty in this paper. In the absence of this property, an exponential time algorithm appears to be called for—just for finding one such path. On the other hand, the MV algorithm accomplishes this and additional tasks in linear time. The saving grace is the various “footholds” offered by the underlying structure, which the algorithm uses in order to perform its key tasks efficiently. The theory expounded in this paper elucidates this rich structure and yields a proof of correctness of the algorithm. It may also be of independent interest as a set of well-knit graph-theoretic facts. Funding: This work was supported in part by the National Science Foundation [Grant CCF-2230414].