(1- ϵ )-Approximate Maximum Weighted Matching in poly(1/ ϵ , log n ) Time in the Distributed and Parallel Settings
Shang-En Huang, Hsin-Hao Su · 2023
The maximum weighted matching (mwm) problem is one of the most well-studied combinatorial optimization problems in distributed graph algorithms. Despite a long development on the problem, and the recent progress of Fischer, Mitrovic, and Uitto [16] who gave a poly(1/ϵ, log n)-round algorithm for obtaining a (1 − ϵ)-approximate solution for unweighted maximum matching, it had been an open problem whether a (1 − ϵ)-approximate mwm can be obtained in poly(1/ϵ, log n) rounds in the CONGEST model. Algorithms with such running times were only known for special graph classes such as bipartite graphs [1] and minor-free graphs [8]. For general graphs, the previously known algorithms require exponential in (1/ϵ) rounds for obtaining a (1 − ϵ)-approximate solution [13] or achieve an approximation factor of at most 2/3 [1]. In this work, we settle this open problem by giving a deterministic poly(1/ϵ, log n)-round algorithm for computing a (1 − ϵ)-approximate mwm for general graphs in the CONGEST model. Our proposed solution extends the algorithm of Fischer, Mitrovic, and Uitto [16], blends in the sequential algorithm from Duan and Pettie [11] and the work of Faour, Fuchs, and Kuhn [13]. Interestingly, this solution also implies a CREW PRAM algorithm with poly(1/ϵ, log n) span using only O(m) processors, and a poly(1/ϵ)-passes algorithm in the semi-streaming model.