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