2023/03/09 by Sameep Dahal, Jukka Suomela, Dahal, Sameep +1
Computer Science · #Complexity and Algorithms in Graphs #Cooperative Communication and Network Coding #Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Parallel #Privacy-Preserving Technologies in Data #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.2303.05250
openalex publication_date 2023/03/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
By prior work, it is known that any distributed graph algorithm that finds a maximal matching requires Ω(log^* n) communication rounds, while it is possible to find a maximal fractional matching in O(1) rounds in bounded-degree graphs. However, all prior O(1)-round algorithms for maximal fractional matching use arbitrarily fine-grained fractional values. In particular, none of them is able to find a half-integral solution, using only values from \0, \frac12, 1\. We show that the use of fine-grained fractional values is necessary, and moreover we give a complete characterization on exactly how small values are needed: if we consider maximal fractional matching in graphs of maximum degree Δ= 2d, and any distributed graph algorithm with round complexity T(Δ) that only depends on Δ and is independent of n, we show that the algorithm has to use fractional values with a denominator at least 2d. We give a new algorithm that shows that this is also sufficient.