Algorithm Design Of Vertex Cover K-path Problem

Given a vertex-weighted graph G=(V,E)and a positive integer k?2,the minimum weight vertex cover Pk problem(MWVCPk)is to find a vertex subset F ?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.Therefore,the researchers mainly study this problem from the perspective of approximation algorithm and exact algorithm on special graphs.In the first part of 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.In the second part of this paper,we study MWVCP3 on Series-Parallel graphs and present a dynamic programming algorithm for it with runtime O(|V|).