Massively Parallel Computation of Matching and MIS in Sparse Graphs

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

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussaConference article in proceedingsScientificvertaisarvioitu

Abstrakti

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.
AlkuperäiskieliEnglanti
OtsikkoPODC '19 - Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing
KustantajaACM
Sivut481-490
ISBN (elektroninen)978-1-4503-6217-7
DOI - pysyväislinkit
TilaJulkaistu - 2019
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisussa
TapahtumaACM Symposium on Principles of Distributed Computing - Toronto, Kanada
Kesto: 29 heinäk. 20192 elok. 2019
Konferenssinumero: 38

Conference

ConferenceACM Symposium on Principles of Distributed Computing
LyhennettäPODC
Maa/AlueKanada
KaupunkiToronto
Ajanjakso29/07/201902/08/2019

Sormenjälki

Sukella tutkimusaiheisiin 'Massively Parallel Computation of Matching and MIS in Sparse Graphs'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

Siteeraa tätä