# Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover

arXiv: https://arxiv.org/abs/1802.08237 · HTML: https://mlsanity.com/paper/1802.08237/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Feb 2018.

## Built on by (most cited first, 2 of 2)

- [Single-Pass Pivot Algorithm for Correlation Clustering. Keep it simple!](https://mlsanity.com/paper/2305.13560/) (2023)
- [Streaming Kernel PCA Algorithm With Small Space](https://mlsanity.com/paper/2303.04555/) (2023)

## Abstract (arXiv)

We present O(loglog n)-round algorithms in the Massively Parallel Computation (MPC) model, with tildeO(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(loglog Delta)-round MIS algorithm in the Congested Clique model of distributed computing, which improves on the tildeO(√log Delta)-round algorithm of Ghaffari [PODC'17]. - Our O(loglog n)-round (1+ε)-approximate maximum matching algorithm simplifies or improves on the following prior work: O(log2log n)-round (1+ε)-approximation algorithm of Czumaj et al. [STOC'18] and O(loglog n)-round (1+ε)-approximation algorithm of Assadi et al. [SODA'19]. - Our O(loglog n)-round (2+ε)-approximate minimum vertex cover algorithm improves on an O(loglog n)-round O(1)-approximation of Assadi et al. [arXiv'17].