$(1-ε)$-Approximate Maximum Weighted Matching in Distributed, Parallel, and Semi-Streaming Settings
Shang-En Huang, Hsin-Hao Su · arXiv (Cornell University) · 2022
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 [FMU22] who gave a $\text{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 $\text{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 [AKO18] and minor-free graphs [CS22]. For general graphs, the previously known algorithms require exponential in $(1/ε)$ rounds for obtaining a $(1-ε)$-approximate solution [FFK21] or achieve an approximation factor of at most 2/3 [AKO18]. In this work, we settle this open problem by giving a deterministic $\text{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 [FMU22], blends in the sequential algorithm from Duan and Pettie [DP14] and the work of Faour, Fuchs, and Kuhn [FFK21]. Interestingly, this solution also implies a CREW PRAM algorithm with $\text{poly}(1/ε, \log n)$ span using only $O(m)$ processors. In addition, with the reduction from Gupta and Peng [GP13], we further obtain a semi-streaming algorithm with $\text{poly}(1/ε)$ passes. When $ε$ is smaller than a constant $o(1)$ but at least $1/\log^{o(1)} n$, our algorithm is more efficient than both Ahn and Guha's $\text{poly}(1/ε, \log n)$-passes algorithm [AG13] and Gamlath, Kale, Mitrovic, and Svensson's $(1/ε)^{O(1/ε^2)}$-passes algorithm [GKMS19].