Vertex Cover of Networks and Its Related Optimization Problems: An Overview.

Abstract

As a well-known NP-hard problem, the vertex cover problem has broad applications, which has aroused the concern of many researchers. In recent years, its related optimization problems, including the weighted vertex cover problem, the $\ell \geq 3$ path vertex cover problem, and the connected vertex cover problem, and other related optimization problems have came into the view of researchers, who have designed various optimization algorithms to solve those related optimization problems. First, based on the existing works, we give detailed descriptions of the vertex cover problem and its related optimization problems and then review the current research progress. Then, we present some main representative optimization algorithms and provide numerical results and corresponding analysis. Finally, we summarize the existing works and present the future research directions.