An efficient local search for partial vertex cover problem

In this paper, an efficient local search framework, namely GRASP-PVC, is proposed to solve the minimum partial vertex cover problem. In order to speed up the convergence, a novel least-cost vertex selecting strategy is applied into GRASP-PVC. As far as we know, no heuristic algorithms have ever been reported to solve this momentous problem and we compare GRASP-PVC with a commercial integer programming solver CPLEX as well as a 2-approximation algorithm on two standard benchmark libraries called DIMACS and BHOSLIB. Experimental results evince that GRASP-PVC finds much better partial vertex covers than CPLEX and the approximation algorithm on most instances. Additional experimental results also confirm the validity of the least-cost vertex selecting strategy.