2022/12/29 by Shang-En Huang, Hsin-Hao Su, Huang, Shang-En +1
Computer Science · #Caching and Content Delivery #Complexity and Algorithms in Graphs #Cryptography and Data Security #Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.2212.14425
openalex publication_date 2022/12/29 · openalex created_date 2023/01/06 · openalex updated_date 2026/07/28
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 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 [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 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 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 poly(1/ε) passes. When ε is smaller than a constant o(1) but at least 1/logo(1) n, our algorithm is more efficient than both Ahn and Guha's poly(1/ε, log n)-passes algorithm [AG13] and Gamlath, Kale, Mitrovic, and Svensson's (1/ε)O(1/ε2)-passes algorithm [GKMS19].