Exponentially Faster Massively Parallel Maximal Matching
Open Access
- 11 October 2023
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 70 (5) , 1-18
Abstract
The study of approximate matching in the Massively Parallel Computations (MPC) model has recently seen a burst of breakthroughs. Despite this progress, we still have a limited understanding of maximal matching which is one of the central problems of parallel and distributed computing. All known MPC algorithms for maximal matching either take polylogarithmic time which is considered inefficient, or require a strictly super-linear space of n 1+Ω (1) per machine. In this work, we close this gap by providing a novel analysis of an extremely simple algorithm, which is a variant of an algorithm conjectured to work by Czumaj, Lacki, Madry, Mitrovic, Onak, and Sankowski [ 15 ]. The algorithm edge-samples the graph, randomly partitions the vertices, and finds a random greedy maximal matching within each partition. We show that this algorithm drastically reduces the vertex degrees. This, among other results, leads to an O (log log Δ) round algorithm for maximal matching with O(n) space (or even mildly sublinear in n using standard techniques). As an immediate corollary, we get a 2 approximate minimum vertex cover in essentially the same rounds and space, which is the optimal approximation factor under standard assumptions. We also get an improved O (log log Δ) round algorithm for 1 + ε approximate matching. All these results can also be implemented in the congested clique model in the same number of rounds.Keywords
This publication has 29 references indexed in Scilit:
- Distributed MIS via All-to-All Communication2017
- Randomized Composable Coresets for Matching and Vertex Cover2017
- Brief Announcement2017
- Access to Data and Number of Iterations2015
- Parallel algorithms for geometric graph problems2014
- Distributed Approximate MatchingSIAM Journal on Computing, 2009
- Vertex cover might be hard to approximate to withinJournal of Computer and System Sciences, 2008
- MapReduceCommunications of the ACM, 2008
- A fast and simple randomized parallel algorithm for the maximal independent set problemJournal of Algorithms, 1986
- A fast and simple randomized parallel algorithm for maximal matchingInformation Processing Letters, 1986