Improved massively parallel computation algorithms for MIS, matching, and vertex cover

Mohsen Ghaffari, Themis Gouleakis, Christian Konrad, Slobodan Mitrović, Ronitt Rubinfeld

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

42 Citations (Scopus)

Abstract

We present O(log log n)-round algorithms in the Massively Parallel Computation (MPC) model, with Õ(n) memory per machine, that compute a maximal independent set, a 1 + approximation of maximum matching, and a 2 + approximation of minimum vertex cover, for any n-vertex graph and any constant > 0. These improve the state of the art as follows: • Our MIS algorithm leads to a simple O(log log ∆)-round MIS algorithm in the CONGESTED-CLIQUE model of distributed computing, which improves on the Õ(log ∆)-round algorithm of Ghaffari [PODC'17]. • Our O(log log n)-round (1+)-approximate maximum matching algorithm simplifies or improves on the following prior work: O(log2 log n)-round (1 +)-approximation algorithm of Czumaj et al. [STOC'18] and O(log log n)-round (1 + )- approximation algorithm of Assadi et al. [arXiv'17]. • Our O(log log n)-round (2 +)-approximate minimum vertex cover algorithm improves on an O(log log n)-round O(1)approximation of Assadi et al. [arXiv'17].

Original languageEnglish
Title of host publicationPODC 2018 - Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing
PublisherAssociation for Computing Machinery (ACM)
Pages129-138
Number of pages10
ISBN (Print)9781450357951
DOIs
Publication statusPublished - 23 Jul 2018
Event37th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC 2018 - Egham, United Kingdom
Duration: 23 Jul 201827 Jul 2018

Conference

Conference37th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC 2018
CountryUnited Kingdom
CityEgham
Period23/07/1827/07/18

Keywords

  • Congested clique
  • Massively parallel computation
  • Maximal independent set
  • Maximum matching
  • Vertex cover

Fingerprint Dive into the research topics of 'Improved massively parallel computation algorithms for MIS, matching, and vertex cover'. Together they form a unique fingerprint.

Cite this