CR-DIS: An Efficient Heuristic Algorithm for Minimum Weighted Vertex Cover Problem

The minimum weighted vertex cover (MWVC) problem is a well-known NP-hard combinatorial optimization problem. In this problem, each vertex of the graph is assigned a positive weight, and the objective is to identify a set of vertices such that every edge is covered by at least one vertex from the set, while minimizing the sum of all vertices' weights in the set. It has greater generality and broader applications than the minimum vertex cover (MVC) problem. Due to its NP-hard nature, efficiently solving the MWVC problem is a significant challenge. This paper introduces a highly efficient heuristic algorithm named CR-DIS for MWVC, which consists of two components: a construction with reductions and a dynamic improvement search framework. We compare CR-DIS with three state-of-the-art algorithms on a large number of graphs. Experimental results indicate that CR-DIS performs at a superior level, especially on large sparse graphs, yielding more best solutions and, in many instances, achieving smaller solutions with similar running times.