Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover
share
We present O( 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(Δ)-round MIS algorithm in the Congested Clique model of distributed computing. This result improves exponentially on the Õ(√(Δ))-round algorithm of Ghaffari [PODC'17]. -- Our O( n)-round (1+ϵ)-approximate maximum matching algorithm simplifies and improves on a rather complex O(^2 n)-round (1+ϵ)-approximation algorithm of Czumaj et al. [STOC'18]. -- Our O( n)-round (2+ϵ)-approximate minimum vertex cover algorithm improves on an O( n)-round O(1)-approximation of Assadi et al. [arXiv'17].
READ FULL TEXT