A MapReduce Algorithm for Minimum Vertex Cover Problems and Its Randomization

Abstract

MapReduce is a programming paradigm for large-scale distributed information processing. This paper proposes a MapReduce algorithm for the minimum vertex cover problem, which is known to be NP-hard. The MapReduce algorithm can efficiently obtain a minimal vertex cover in a small number of rounds. We show the effectiveness of the algorithm, through experimental evaluation and comparison with exact and approximate algorithms that it demonstrates high quality in a small number of MapReduce rounds. We also confirm from experimentation that the algorithm has good scalability, allowing high-quality solutions under restricted computation times due to increased graph size. Moreover, we extend our algorithm to randomized one to obtain good expected approximate ratio.