A Nearly Linear-Time Distributed Algorithm for Exact Maximum Matching
Taisuke Izumi, Naoki Kitamura, Yutaro Yamaguchi · Society for Industrial and Applied Mathematics eBooks · 2024
In this paper, we propose a randomized Õ(µ(G))-round algorithm for the maximum cardinality matching problem in the CONGEST model, where µ(G) means the maximum size of a matching of the input graph G. The proposed algorithm substantially improves the current best worst-case running time. The key technical ingredient is a new randomized algorithm of finding an augmenting path of length ℓ with high probability within Õ(ℓ) rounds, which positively settles an open problem left in the prior work by Ahmadi and Kuhn [DISC’20].