Distributed half-integral matching and beyond

Sameep Dahal; Jukka Suomela

doi:10.1016/j.tcs.2023.114278

Distributed half-integral matching and beyond

Sameep Dahal, Jukka Suomela^*

^*Corresponding author for this work

Research output: Contribution to journal › Article › Scientific › peer-review

27 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 [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 2^d. We give a new algorithm that shows that this is also sufficient.

Original language	English
Article number	114278
Journal	Theoretical Computer Science
Volume	982
Early online date	8 Nov 2023
DOIs	https://doi.org/10.1016/j.tcs.2023.114278
Publication status	Published - 8 Jan 2024
MoE publication type	A1 Journal article-refereed

Funding

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] .

Keywords

Computational complexity
Distributed graph algorithms
Fractional matching
Maximal matching

Access to Document

10.1016/j.tcs.2023.114278Licence: CC BY

SCI_Dahal_etal_Theoretical_Computer_Science_2023Final published version, 782 KBLicence: CC BY

Cite this

@article{4756ea29901248dfad383e85e31b3a84,

title = "Distributed half-integral matching and beyond",

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.",

keywords = "Computational complexity, Distributed graph algorithms, Fractional matching, Maximal matching",

author = "Sameep Dahal and Jukka Suomela",

note = "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: {\textcopyright} 2023 The Author(s)",

year = "2024",

month = jan,

day = "8",

doi = "10.1016/j.tcs.2023.114278",

language = "English",

volume = "982",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier",

}

TY - JOUR

T1 - Distributed half-integral matching and beyond

AU - Dahal, Sameep

AU - Suomela, Jukka

N1 - 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)

PY - 2024/1/8

Y1 - 2024/1/8

N2 - 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.

AB - 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.

KW - Computational complexity

KW - Distributed graph algorithms

KW - Fractional matching

KW - Maximal matching

UR - https://www.scopus.com/pages/publications/85176130012

U2 - 10.1016/j.tcs.2023.114278

DO - 10.1016/j.tcs.2023.114278

M3 - Article

AN - SCOPUS:85176130012

SN - 0304-3975

VL - 982

JO - Theoretical Computer Science

JF - Theoretical Computer Science

M1 - 114278

ER -

Distributed half-integral matching and beyond

Abstract

Funding

Keywords

Access to Document

Other files and links

Fingerprint

LocalMend /Suomela: Local Checking, Solving, and MendingNew Perspectives of Distributed Computing (LocalMend)

Cite this

Distributed half-integral matching and beyond

Abstract

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Projects

LocalMend /Suomela: Local Checking, Solving, and MendingNew Perspectives of Distributed Computing (LocalMend)

Cite this

LocalMend /Suomela: Local Checking, Solving, and MendingNew Perspectives of Distributed Computing (LocalMend)