A multi-start iterated greedy algorithm for the minimum weight vertex cover P3 problem

Given a vertex-weighted graph G = (V, E) and a positive integer k >= 2, the minimum weight vertex cover P-k (MWVCPk) problem is to find a vertex subset F subset of V with minimum total weight such that every path of order k in G contains at least one vertex in F. For any integer k >= 2, the MWVCPk problem for general graphs is NP-hard. In this paper, we restrict our attention to the MWVCP3 problem and present a multi-start iterated greedy algorithm to solve the MWVCP3 problem. The experiments are carried out on randomly generated instances with up to 1000 vertices and 250000 edges. Our work is the first one to adopt heuristic algorithms to solve the MWVCP3 problem, and the experimental results show that our algorithm performs reasonably well in practice. (C) 2019 Elsevier Inc. All rights reserved.