Projects per year
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 boundeddegree graphs. However, all prior O(1)round algorithms for maximal fractional matching use arbitrarily finegrained fractional values. In particular, none of them is able to find a halfintegral solution, using only values from {0,12,1}. We show that the use of finegrained 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.
Original language  English 

Title of host publication  Structural Information and Communication Complexity  30th International Colloquium, SIROCCO 2023, Proceedings 
Editors  Sergio Rajsbaum, Sergio Rajsbaum, Alkida Balliu, Dennis Olivetti, Joshua J. Daymude 
Publisher  Springer 
Pages  339356 
Number of pages  18 
ISBN (Electronic)  9783031327339 
ISBN (Print)  9783031327322 
DOIs  
Publication status  Published  2023 
MoE publication type  A4 Conference publication 
Event  International Colloquium on Structural Information and Communication Complexity  Madrid, Spain Duration: 6 Jun 2023 → 9 Jun 2023 Conference number: 30 
Publication series
Name  Lecture Notes in Computer Science 

Publisher  Springer 
Volume  13892 
ISSN (Print)  03029743 
ISSN (Electronic)  16113349 
Conference
Conference  International Colloquium on Structural Information and Communication Complexity 

Abbreviated title  SIROCCO 
Country/Territory  Spain 
City  Madrid 
Period  06/06/2023 → 09/06/2023 
Fingerprint
Dive into the research topics of 'Distributed HalfIntegral Matching and Beyond'. Together they form a unique fingerprint.Projects
 1 Active

LocalMend /Suomela: Local Checking, Solving, and Mending—New Perspectives of Distributed Computing (LocalMend)
Suomela, J., Lievonen, H., Melnyk, D., Vahidi, H., Studeny, J. & Akbari, A.
01/09/2020 → 31/08/2024
Project: Academy of Finland: Other research funding
Prizes

Best Student Paper Award at 30TH INTERNATIONAL COLLOQUIUM ON STRUCTURAL INFORMATION AND COMMUNICATION COMPLEXITY
Dahal, Sameep (Recipient), 2023
Prize: Award or honor granted for a specific work