NuMVC: An Efficient Local Search Algorithm for Minimum Vertex Cover

DOI10.1613/JAIR.3907zbMATH Open1280.90098arXiv1402.0584OpenAlexW2122448854MaRDI QIDQ4917618FDOQ4917618

Kaile Su, Shaowei Cai, Chuan Luo, Abdul Sattar

Publication date: 2 May 2013

Published in: Journal of Artificial Intelligence Research (Search for Journal in Brave)

Abstract: 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. We 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.

Full work available at URL: https://arxiv.org/abs/1402.0584

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial optimization (90C27) Nonnumerical algorithms (68W05)

Cited In (20)

• SCCWalk: an efficient local search algorithm and its improvements for maximum weight clique problem
• Dual-neighborhood iterated local search for routing and wavelength assignment
• Title not available (Why is that?)
• \(\boldsymbol{borealis}\) -- a generalized global update algorithm for Boolean optimization problems
• An efficient local search algorithm with large neighborhoods for the maximum weighted independent set problem†
• An efficient local search algorithm for minimum positive influence dominating set problem
• An efficient local search framework for the minimum weighted vertex cover problem
• A vertex weighting-based double-tabu search algorithm for the classical \(p\)-center problem
• An approximation Lagrangian-based algorithm for the maximum clique problem via deterministic annealing neural network
• NuMVC
• Towards faster local search for minimum weight vertex cover on massive graphs
• Local search for Boolean satisfiability with configuration checking and subscore
• An efficient local search algorithm for solving maximum edge weight clique problem in large graphs
• CCEHC: an efficient local search algorithm for weighted partial maximum satisfiability
• Improved local search for the minimum weight dominating set problem in massive graphs by using a deep optimization mechanism
• An improved configuration checking-based algorithm for the unicost set covering problem
• Backdoors to tractable answer set programming
• Focused jump-and-repair constraint handling for fixed-parameter tractable graph problems closed under induced subgraphs
• Can local optimality be used for efficient data reduction?
• An efficient heuristic algorithm for solving connected vertex cover problem

Uses Software

• BHOSLIB
• DIMACS

This page was built for publication: NuMVC: An Efficient Local Search Algorithm for Minimum Vertex Cover

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4917618)