A MapReduce Algorithm for Minimum Vertex Cover Problems and Its Randomization

keywords: MapReduce, minimum vertex cover, Hadoop, optimization, algorithm design, randomized algorithm
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 which demonstrates a 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 a good expected approximate ratio.
reference: Vol. 39, 2020, No. 5, pp. 952–972