Distributed Half-Integral Matching and Beyond

Sameep Dahal, Jukka Suomela*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference article in proceedingsScientificpeer-review

1 Citation (Scopus)
19 Downloads (Pure)

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 {0,12,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.
Original languageEnglish
Title of host publicationStructural Information and Communication Complexity - 30th International Colloquium, SIROCCO 2023, Proceedings
EditorsSergio Rajsbaum, Sergio Rajsbaum, Alkida Balliu, Dennis Olivetti, Joshua J. Daymude
PublisherSpringer
Pages339-356
Number of pages18
ISBN (Electronic)978-3-031-32733-9
ISBN (Print)978-3-031-32732-2
DOIs
Publication statusPublished - 2023
MoE publication typeA4 Conference publication
EventInternational Colloquium on Structural Information and Communication Complexity - Madrid, Spain
Duration: 6 Jun 20239 Jun 2023
Conference number: 30

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume13892
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceInternational Colloquium on Structural Information and Communication Complexity
Abbreviated titleSIROCCO
Country/TerritorySpain
CityMadrid
Period06/06/202309/06/2023

Fingerprint

Dive into the research topics of 'Distributed Half-Integral Matching and Beyond'. Together they form a unique fingerprint.

Cite this