A Theory of Alternating Paths and Blossoms, from the Perspective of Minimum Length

This event consists of two talks. The first talk will take place from 2 to 3 p.m., and will be followed by a break with light refreshments from 3 to 3:30 p.m. The second talk will take place from 3:30 to 4:30 p.m.

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 in 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 new ideas contained in the MV algorithm and its proof remain largely unknown, and hence unexplored, for use elsewhere.

The purpose of this two-talk sequence is to rectify that shortcoming. These talks are based on this paper.

Talk 1 (2–3 p.m.)
Vazirani will start by providing basic algorithmic background, including the bipartite case and Edmonds' 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. Vazirani will show why, in the absence of this property, an exponential-time algorithm appears to be called for, even 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. 

Vazirani will end this talk by showing the powerful graph search procedure of double depth-first search (DDFS) in a simplified setting. 

This is a key idea underlying not only the algorithm but also its proof. For people who are interested in the first talk only, this may be a good "take-home message.''

Talk 2 (3:30–4:30 p.m.)
Vazirani will attempt to provide an in-depth understanding of the footholds mentioned above. This is encapsulated in an elaborate new theory of alternating paths and blossoms, from the perspective of minimum length paths. 

He will also use these insights to provide an in-depth understanding of the algorithm. 

Vijay Vazirani is a distinguished professor at the University of California, Irvine. A description of his research appears in the citation of his 2022 INFORMS John von Neumann Theory Prize. His co-edited book, Online and Matching-Based Market Design, appeared in July 2023.

===================================================================

The Simons Institute regularly captures photos and video of activity around the Institute for use in publications and promotional materials. 

If you require special accommodation, please contact our access coordinator at simonsevents@berkeley.edu with as much advance notice as possible.