NuMVC: An Efficient Local Search Algorithm for Minimum Vertex Cover

Shaowei Cai, Kaile Su, Chuan Luo, Abdul Sattar

Abstract

The Minimum Vertex Cover (MVC) problem is a fundamental NP-hard combinatorial optimization problem with significant theoretical and practical implications. While local search algorithms have demonstrated success in solving MVC instances, existing state-of-the-art methods suffer from two primary limitations: the high computational cost of simultaneous vertex exchange and the lack of a mechanism to decay edge weights, which can lead to search stagnation. This paper introduces NuMVC, a local search algorithm that addresses these issues through two novel strategies: two-stage exchange and edge weighting with forgetting. Experimental results on DIMACS and BHOSLIB benchmarks demonstrate that NuMVC significantly outperforms existing heuristic solvers and finds optimal solutions faster than state-of-the-art exact algorithms on several instance types.

Introduction

In a graph $G = (V, E)$, a vertex cover is a subset of vertices $C \subseteq V$ such that every edge in $E$ is incident to at least one vertex in $C$. The Minimum Vertex Cover problem seeks the smallest such subset. Given its NP-hard nature, local search heuristics are often employed to find high-quality solutions for large-scale instances.

Traditional local search algorithms for MVC typically operate by exchanging a vertex in the current cover with one outside the cover. However, the authors identify two critical bottlenecks in these approaches. First, selecting a pair of vertices to swap simultaneously is computationally expensive, often requiring $O(N^2)$ time. Second, while edge weighting is used to diversify the search by prioritizing uncovered edges, most algorithms only increase these weights. Over time, accumulated weights from early search phases can mislead the algorithm, trapping it in suboptimal regions of the search space.

The NuMVC Algorithm

NuMVC introduces two key algorithmic innovations designed to improve search efficiency and diversification.

1. Two-Stage Exchange Strategy

Rather than evaluating all possible pairs $(u, v)$ for a swap—where $u$ is removed from the cover and $v$ is added—NuMVC decomposes the move into two distinct stages:

  • Stage 1 (Removal): The algorithm greedily selects a vertex to remove from the current cover based on its "benefit" (the reduction in cover size or improvement in edge coverage).
  • Stage 2 (Addition): The algorithm then selects an uncovered edge and chooses one of its endpoints to add back into the cover.

This decomposition reduces the complexity of a single search step from quadratic to linear ($O(N)$). Consequently, NuMVC can perform three to four times more iterations per second than its predecessors, allowing for a more thorough exploration of the search space within the same time budget.

2. Edge Weighting with Forgetting

To prevent the search from being dominated by outdated information, NuMVC implements a "forgetting" mechanism. While it continues to increase the weights of uncovered edges to encourage their eventual coverage, it also introduces a decay factor $\rho$. When the average edge weight reaches a predefined threshold, all weights are scaled down. This ensures that the algorithm remains responsive to the current local topology of the graph rather than being anchored by the history of the search.

3. Configuration Checking (CC)

NuMVC also incorporates the Configuration Checking (CC) heuristic. CC prevents the algorithm from immediately re-adding a vertex that was recently removed unless its neighborhood has changed. This acts as a dynamic tabu mechanism, effectively reducing cycles and encouraging the exploration of new configurations.

Experimental Evaluation

The performance of NuMVC was evaluated against leading competitors, including PLS, COVER, and EWCC, using two major benchmark suites:

  • DIMACS: A standard set of graphs from various domains, including coding theory and fault diagnosis.
  • BHOSLIB (Benchmarks with Hidden Optimum Solutions): A suite of random graphs generated near phase transitions, specifically designed to be difficult for local search algorithms.

Key Findings

  • BHOSLIB Dominance: NuMVC demonstrated clear superiority on the BHOSLIB suite. It solved 33 out of 40 instances with a 100% success rate. On the most challenging instances where competitors like PLS and COVER achieved success rates between 0% and 17%, NuMVC maintained an 82.5% success rate.
  • DIMACS Performance: NuMVC proved competitive with PLS, the previous state-of-the-art, and showed superior speed on structured instances within the suite.
  • Comparison with Exact Solvers: When compared against the best-known exact algorithms for the Maximum Clique problem (the mathematical dual of MVC), NuMVC found optimal solutions on large random and structured graphs significantly faster.
  • Robustness: Analysis of the algorithm's runtime behavior showed that NuMVC's performance follows an exponential distribution. This suggests the algorithm is robust against stagnation and is well-suited for parallel execution.

Conclusion

NuMVC represents a significant advancement in local search for the Minimum Vertex Cover problem. By simplifying the vertex exchange process and introducing a forgetting mechanism for edge weights, the algorithm achieves a balance between high-speed iteration and effective search diversification. While challenges remain—particularly with "brock" graphs designed to defeat greedy heuristics—the strategies introduced in NuMVC provide a robust framework that may be applicable to other subset-selection problems in combinatorial optimization.

Summary updated

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.
BibTeX
@article{cai2013numvc,
  author = {Shaowei Cai and Kaile Su and Chuan Luo and Abdul Sattar},
  title = {{NuMVC: An Efficient Local Search Algorithm for Minimum Vertex Cover}},
  journal = {J. Artif. Intell. Res.},
  year = {2013},
  url = {https://openreview.net/forum?id=xyZ-m9EyrB},
}
Figure