Distributed half-integral matching and beyond

DOI10.1007/978-3-031-32733-9_15MaRDI QIDQ6148072zbMATH OpenOpenAlexFDO

Authors Sameep Dahal, Jukka Suomela

Publication date 11 January 2024

Published in Structural Information and Communication Complexity (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2303.05250, https://aaltodoc.aalto.fi/handle/123456789/122148

zbMATH Keywords

distributed graph algorithmsfractional matchinghalf-integral matchingmaximal matching

Mathematics Subject Classification ID

Computer system organization (68Mxx) Communication complexity, information complexity (68Q11) Graph theory (including graph drawing) in computer science (68R10)

Abstract: By prior work, it is known that any distributed graph algorithm that finds a maximal matching requires $Omega(lo{g}^{\ast }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 $Delta=2d$, and any distributed graph algorithm with round complexity $T(Delta)$ that only depends on $Delta$ 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.

Cites work

• A fast and simple randomized parallel algorithm for maximal matching
• A linear-time approximation algorithm for the weighted vertex cover problem
• A Local 2-Approximation Algorithm for the Vertex Cover Problem
• A Lower Bound on Probabilistic Algorithms for Distributive Ring Coloring
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Distributed Computing: A Locality-Sensitive Approach
• Distributed maximal matching, greedy is optimal
• Improved deterministic distributed matching via rounding
• Linear-in- lower bounds in the LOCAL model
• Locality in Distributed Graph Algorithms
• Lower Bounds for Maximal Matchings and Maximal Independent Sets
• On the distributed complexity of computing maximal matchings
• Some simple distributed algorithms for sparse networks
• The locality of distributed symmetry breaking

This page was built for publication: Distributed half-integral matching and beyond

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6148072)