Title: Simple Round Compression for Parallel Vertex Cover,
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\sqrt{n})$.