Two Heuristic Algorithms for the Minimum Weighted Connected Vertex Cover Problem Under Greedy Strategy

Abstract

The Minimum Weighted Connected Vertex Cover problem (MWCVC) is to find a subset $F\subset V(G)$ with minimum weight in a node-weighted graph $G$ , such that when removing the set $F$ , the inducing graph of remaining vertices holds no edges, and the graph induced from set $F$ in $G$ is required to be connected. This problem comes from the classical combinatorial problem in graph theory, i.e., the Vertex Cover Problem. A large number of results on algorithms for the MWCVC problem have been reported. In this paper, we proposed two heuristic algorithms, denoted as VCC and LCVCC, to find a connected vertex cover set in a general weighted graph. The time complexity of both two algorithms are less than $O(n^{4})$ . We compare these two algorithms with two known heuristic algorithms GR and GD (proposed by Dagdeviren in 2021) on connected graphs, and draw a conclusion that both of VCC and LCVCC perform better than GR or GD. Relatively speaking, LCVCC is expected to have better performance in dense graphs than VCC.

Keywords

• Minimum weighted connected vertex cover problem
• heuristic algorithm
• greedy strategy
• algorithm performance