Simple Round Compression for Parallel Vertex Cover

Author: Sepehr Assadi.
Abstract: Recently, Czumaj et al. (arXiv 2017) presented a parallel (almost) 2-approximation algorithm for the maximum matching problem in only O((log log n)^2) rounds of the massive parallel computation (MPC) framework, when the memory per machine is O(n). The main approach in their work is a way of compressing O(log n) rounds of a distributed algorithm for maximum matching into only O((log log n)^2) MPC rounds.

In this note, we present a similar algorithm for the closely related problem of approximating the minimum vertex cover in the MPC framework. We show that one can achieve an O(log n) approximation to minimum vertex cover in only O(log log n) MPC rounds when the memory per machine is O(n). Our algorithm for vertex cover is similar to the maximum matching algorithm of Czumaj et al. but avoids many of the intricacies in their approach and as a result admits a considerably simpler analysis (at a cost of a worse approximation guarantee). We obtain this result by modifying a previous parallel algorithm by Khanna and the author (SPAA 2017) for vertex cover that allowed for compressing O(log n) rounds of a distributed algorithm into constant MPC rounds when the memory allowed per machine is O(n√n).
Manuscript: [arXiv]