Forgetting Alternation and Blossoms: A New Framework for Fast Matching Augmentation and Its Applications to Sequential/Distributed/Streaming Computation
Taisuke Izumi, Naoki Kitamura, Yutaro Yamaguchi · 2025
Read Forgetting Alternation and Blossoms: A New Framework for Fast Matching Augmentation and Its Applications to Sequential/Distributed/Streaming Computation by Taisuke Izumi, Naoki Kitamura, Yutaro Yamaguchi (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-08210.txt.
Description
Taisuke Izumi, Naoki Kitamura, and Yutaro Yamaguchi offer a new framework for fast matching augmentation in graphs that avoids the classic blossom machinery. Maximum matching is a core graph problem, and the Micali Vazirani algorithm from 1980 remains among the fastest general methods. Its correctness proof, however, resisted completion for over forty years, largely because shortest alternating paths tangle with nested blossoms.
The new structure theorem describes those paths without blossom details by forgetting edge alternation as early as possible. Alternating base trees, refined from the authors earlier distributed work, carry the argument. A resulting algorithm is slightly slower but far easier to implement and verify, with uses in sequential, distributed, and streaming settings.
Catalog record
| CREATOR | Taisuke Izumi, Naoki Kitamura, Yutaro Yamaguchi |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 136 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-08210