Combining Edge Weight and Vertex Weight for Minimum Vertex Cover Problem

The Minimum Vertex Cover (MVC) problem is an important NP-hard combinatorial optimization problem. Constraint weighting is an effective technique in stochastic local search algorithms for the MVC problem. The edge weight and the vertex weight have been used separately by different algorithms. We present a new local search algorithm, namely VEWLS, which integrates the edge weighting scheme with the vertex weighting scheme. To the best of our knowledge, it is the first time to combine two weighting schemes for the MVC problem. Experiments over both the DIMACS benchmark and the BHOSLIB benchmark show that VEWLS outperforms NuMVC, the state-of-the-art local search algorithm for MVC, on 73% and 68% of the instances, respectively.