  The Minimum Vertex Cover (MVC) problem is a prominent NP-hard combinatorial
optimization problem of great importance in both theory and application. Local
search has proved successful for this problem. However, there are two main
drawbacks in state-of-the-art MVC local search algorithms. First, they select a
pair of vertices to exchange simultaneously, which is time-consuming. Secondly,
although using edge weighting techniques to diversify the search, these
algorithms lack mechanisms for decreasing the weights. To address these issues,
we propose two new strategies: two-stage exchange and edge weighting with
forgetting. The two-stage exchange strategy selects two vertices to exchange
separately and performs the exchange in two stages. The strategy of edge
weighting with forgetting not only increases weights of uncovered edges, but
also decreases some weights for each edge periodically. These two strategies
are used in designing a new MVC local search algorithm, which is referred to as
NuMVC. We conduct extensive experimental studies on the standard benchmarks,
namely DIMACS and BHOSLIB. The experiment comparing NuMVC with state-of-the-art
heuristic algorithms show that NuMVC is at least competitive with the nearest
competitor namely PLS on the DIMACS benchmark, and clearly dominates all
competitors on the BHOSLIB benchmark. Also, experimental results indicate that
NuMVC finds an optimal solution much faster than the current best exact
algorithm for Maximum Clique on random instances as well as some structured
ones. Moreover, we study the effectiveness of the two strategies and the
run-time behaviour through experimental analysis.
