Distributed half-integral matching and beyond

Loading...
Thumbnail Image
Journal Title
Journal ISSN
Volume Title
A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä
Date
2024-01-08
Major/Subject
Mcode
Degree programme
Language
en
Pages
Series
Theoretical Computer Science, Volume 982
Abstract
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 [Formula presented]. 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.
Description
Funding Information: This work was supported in part by the Research Council of Finland , Grant 333837 . We would like to thank the anonymous reviewers for their helpful feedback, and the members of Aalto Distributed Algorithms group for discussions. This is an extended version of a preliminary conference report [8] . Publisher Copyright: © 2023 The Author(s)
Keywords
Computational complexity, Distributed graph algorithms, Fractional matching, Maximal matching
Other note
Citation
Dahal , S & Suomela , J 2024 , ' Distributed half-integral matching and beyond ' , Theoretical Computer Science , vol. 982 , 114278 . https://doi.org/10.1016/j.tcs.2023.114278