Massively Parallel Computation of Matching and MIS in Sparse Graphs

Soheil Behnezhad, Sebastian Brandt, Mahsa Derakhshan, Manuela Fischer, Mohammadtaghi Hajiaghayi, Richard Karp, Jara Uitto

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


The Massively Parallel Computation (MPC) model serves as a common abstraction of many modern large-scale parallel computation frameworks and has recently gained a lot of importance, especially in the context of classic graph problems. In this work, we mainly consider maximal matching and maximal independent set problems in the MPC model. These problems are known to admit efficient MPC algorithms if the space available per machine is near-linear in the number n of nodes. This is not only often significantly more than what we can afford, but also allows for easy if not trivial solutions for sparse graphs---which are common in real-world large-scale graphs. We are, therefore, interested in the low-memory MPC model, where the space per machine is restricted to be strongly sublinear, that is, nδ for any constant 0 < δ < 1. We parametrize our algorithms by the arboricity λ of the input graph. Our key ingredient is a degree reduction technique that reduces these problems in graphs with arboricity λ to the corresponding problems in graphs with maximum degree poly(λ, log n) in O(log2 log n) rounds, giving rise to O(√ log λ ⋅ log log λ + log 2 log n)-round algorithms. Our result is particularly interesting for graphs with poly log n arboricity as for such graphs, we get O(log 2 log n)-round algorithms. This covers most natural families of sparse graphs and almost exponentially improves over previous algorithms that all required log Ω(1) n rounds in this regime of MPC. Finally, our maximal matching algorithm can be employed to obtain a (1+ε)-approximate maximum cardinality matching, a (2+ε)-approximate maximum weighted matching, as well as a 2-approximate minimum vertex cover in essentially the same number of rounds.
Original languageEnglish
Title of host publicationPODC '19 - Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing
ISBN (Electronic)978-1-4503-6217-7
Publication statusPublished - 2019
MoE publication typeA4 Conference publication
EventACM Symposium on Principles of Distributed Computing - Toronto, Canada
Duration: 29 Jul 20192 Aug 2019
Conference number: 38


ConferenceACM Symposium on Principles of Distributed Computing
Abbreviated titlePODC


Dive into the research topics of 'Massively Parallel Computation of Matching and MIS in Sparse Graphs'. Together they form a unique fingerprint.

Cite this