NuMVC: an efficient local search algorithm for minimum vertex cover The Minimum Vertex Cover (MVC) problem is a prominent NP-hard combinatorial optimization problem of great importance in both theory and application. Local search has proved successful for this problem. However, there are two main drawbacks in state-of-the-art MVC local search algorithms. First, they select a pair of vertices to exchange simultaneously, which is time-consuming. Secondly, although using edge weighting techniques to diversify the search, these algorithms lack mechanisms for decreasing the weights. To address these issues, we propose two new strategies: two-stage exchange and edge weighting with forgetting. The two-stage exchange strategy selects two vertices to exchange separately and performs the exchange in two stages. The strategy of edge weighting with forgetting not only increases weights of uncovered edges, but also decreases some weights for each edge periodically. These two strategies are used in designing a new MVC local search algorithm, which is referred to as NuMVC. \parWe conduct extensive experimental studies on the standard benchmarks, namely DIMACS and BHOSLIB. The experiment comparing NuMVC with state-of-the-art heuristic algorithms show that NuMVC is at least competitive with the nearest competitor namely PLS on the DIMACS benchmark, and clearly dominates all competitors on the BHOSLIB benchmark. Also, experimental results indicate that NuMVC finds an optimal solution much faster than the current best exact algorithm for Maximum Clique on random instances as well as some structured ones. Moreover, we study the effectiveness of the two strategies and the run-time behaviour through experimental analysis.

This software is also peer reviewed by journal TOMS.

References in zbMATH (referenced in 13 articles , 1 standard article )

Showing results 1 to 13 of 13.
Sorted by year (citations)

  1. Wang, Yiyuan; Pan, Shiwei; Al-Shihabi, Sameh; Zhou, Junping; Yang, Nan; Yin, Minghao: An improved configuration checking-based algorithm for the unicost set covering problem (2021)
  2. Chu, Yi; Liu, Boxiao; Cai, Shaowei; Luo, Chuan; You, Haihang: An efficient local search algorithm for solving maximum edge weight clique problem in large graphs (2020)
  3. Wang, Yiyuan; Cai, Shaowei; Chen, Jiejiang; Yin, Minghao: SCCWalk: an efficient local search algorithm and its improvements for maximum weight clique problem (2020)
  4. Zhu, Zheng; Fang, Chao; Katzgraber, Helmut G.: (\boldsymbolborealis) -- a generalized global update algorithm for Boolean optimization problems (2020)
  5. Cai, Shaowei; Li, Yuanjie; Hou, Wenying; Wang, Haoran: Towards faster local search for minimum weight vertex cover on massive graphs (2019)
  6. Zhang, Yongfei; Wu, Jun; Zhang, Liming; Zhao, Peng; Zhou, Junping; Yin, Minghao: An efficient heuristic algorithm for solving connected vertex cover problem (2018)
  7. Luo, Chuan; Cai, Shaowei; Su, Kaile; Huang, Wenxuan: CCEHC: an efficient local search algorithm for weighted partial maximum satisfiability (2017)
  8. Li, Ruizhi; Hu, Shuli; Zhang, Haochen; Yin, Minghao: An efficient local search framework for the minimum weighted vertex cover problem (2016)
  9. Xu, Hong; Kumar, T. K. Satish; Koenig, Sven: A new solver for the minimum weighted vertex cover problem (2016)
  10. Fichte, Johannes Klaus; Szeider, Stefan: Backdoors to tractable answer set programming (2015)
  11. Gao, Jian; Wang, Jianan; Yin, Minghao: Experimental analyses on phase transitions in compiling satisfiability problems (2015) ioport
  12. Cai, Shaowei; Su, Kaile: Local search for Boolean satisfiability with configuration checking and subscore (2013)
  13. Cai, Shaowei; Su, Kaile; Luo, Chuan; Sattar, Abdul: NuMVC: an efficient local search algorithm for minimum vertex cover (2013)