A Massively Parallel Algorithm for Minimum Weight Vertex Cover
share
We present a massively parallel algorithm, with near-linear memory per machine, that computes a (2+ε)-approximation of minimum-weight vertex cover in O(loglog d) rounds, where d is the average degree of the input graph. Our result fills the key remaining gap in the state-of-the-art MPC algorithms for vertex cover and matching problems; two classic optimization problems, which are duals of each other. Concretely, a recent line of work—by Czumaj et al. [STOC'18], Ghaffari et al. [PODC'18], Assadi et al. [SODA'19], and Gamlath et al. [PODC'19]—provides O(loglog n) time algorithms for (1+ε)-approximate maximum weight matching as well as for (2+ε)-approximate minimum cardinality vertex cover. However, the latter algorithm does not work for the general weighted case of vertex cover, for which the best known algorithm remained at O(log n) time complexity.
READ FULL TEXT