2024/09/23 by Ansaripour, Matin, Danaei, Alireza, Mehlhorn, Kurt
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2409.14849
It is known since 1975 (\citeHK75) that maximum cardinality matchings in bipartite graphs with n nodes and m edges can be computed in time O(√(n) m). Asymptotically faster algorithms were found in the last decade and maximum cardinality bipartite matchings can now be computed in near-linear time~\citeNearlyLinearTimeBipartiteMatching, AlmostLinearTimeMaxFlow,AlmostLinearTimeMinCostFlow. For general graphs, the problem seems harder. Algorithms with running time O(√(n) m) were given in~\citeMV80,Vazirani94,Vazirani12,Vazirani20,Vazirani23,Goldberg-Karzanov,GT91,Gabow:GeneralMatching. Mattingly and Ritchey~\citeMattingly-Ritchey and Huang and Stein~\citeHuang-Stein discuss implementations of the Micali-Vazirani Algorithm. We describe an implementation of Gabow's algorithm~\citeGabow:GeneralMatching in C++ based on LEDA~\citeLEDAsystem,LEDAbook and report on running time experiments. On worst-case graphs, the asymptotic improvement pays off dramatically. On random graphs, there is no improvement with respect to algorithms that have a worst-case running time of O(n m). The performance seems to be near-linear. The implementation is available open-source.