NuMWVC: A novel local search for minimum weighted vertex cover problem

Abstract

The problem of finding a minimum weighted vertex cover (MWVC) in a graph is a well-known combinatorial optimisation problem with important applications. This article introduces a novel local search algorithm called NuMWVC for MWVC based on three ideas. First, four reduction rules are introduced during the initial construction phase. Second, a strategy called configuration checking with aspiration, which aims for reducing cycling in local search, is proposed for MWVC for the first time. Moreover, a self-adaptive vertex removing strategy is proposed to save time spent on searching solutions for which the quality is likely far from optimality. Experimental results show that NuMWVC outperforms state-of-the-art local search algorithms for MWVC on the standard benchmarks, massive graphs and real-world problem (map labeling problem) instances.

Keywords:

• Minimum weighted vertex cover problem
• local search
• heuristic search

Acknowledgements

The authors of this article wish to extend their sincere gratitude to all the anonymous reviewers for their effort work.

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

This work was supported in part by Jilin province education department 13th five-year science and technology project under Grant Nos. JJKH20190726KJ, JJKH20190756SK, JJKH20180465KJ, Jilin province science and technology department project under Grant Nos. 20190103030JH, 20190201186JC, Certificate of China Postdoctoral Science Foundation Grant No. 2019M651208 and the National Natural Science Foundation of China (NSFC) under Grant No. 61806082.