NuMWVC: A Novel Local Search for Minimum Weighted Vertex Cover Problem

Ruizhi Li, Shaowei Cai, Shuli Hu, Minghao Yin, Jian GaoAAAI 2018 · DOI

Abstract

The Minimum Weighted Vertex Cover (MWVC) problem is a fundamental NP-hard optimization task with significant applications in massive real-world networks. Traditional local search heuristics often struggle with the scale of modern datasets, failing to find high-quality solutions efficiently. This paper introduces NuMWVC, a high-performance local search algorithm specifically designed for massive graphs. NuMWVC integrates graph reduction rules, a configuration checking strategy with an "aspiration" override, and a self-adaptive vertex removal mechanism. Empirical evaluations on a wide range of massive real-world networks demonstrate that NuMWVC consistently outperforms state-of-the-art solvers in both solution quality and computational efficiency.

Introduction

The Minimum Weighted Vertex Cover (MWVC) problem involves finding a subset of vertices in a weighted graph such that every edge is incident to at least one vertex in the subset, while minimizing the total weight. As real-world networks—such as social networks and web crawls—grow to include millions of nodes and edges, existing solvers like MS-ITS and DLSWCC often encounter scalability issues. These algorithms frequently fail to find initial solutions or become trapped in local optima due to the vast search space. NuMWVC addresses these challenges through a two-stage approach: an initial construction phase utilizing graph reductions and an iterative local search phase.

Methodology

NuMWVC's efficiency stems from three core components designed to handle massive scale:

1. Graph Reduction Rules

Before the search begins, the algorithm applies four reduction rules to identify "inferred weighted vertices"—nodes that must belong to an optimal solution based on local neighborhood structures. This pruning significantly reduces the search space before the local search phase begins.

2. Configuration Checking with Aspiration (CCA)

To prevent cycling during local search, Configuration Checking (CC) restricts vertex re-addition unless its neighborhood has changed. NuMWVC enhances this with an Aspiration criterion: if adding a vertex immediately yields a new "best-ever" solution, the algorithm bypasses the CC rule. This allows the search to break out of restrictive states when a global improvement is found.

3. Self-adaptive Removing (SAR)

NuMWVC dynamically adjusts the intensity of its search. It starts by removing a set number of vertices ($\alpha$). If the algorithm fails to find a better solution after a certain number of iterations ($\beta$), it automatically decreases the number of vertices removed. This dynamically shifts the algorithm from broad exploration to fine-tuned exploitation near potential optima.

Experimental Evaluation

The performance of NuMWVC was evaluated against leading solvers MS-ITS and DLSWCC using a diverse set of massive real-world graphs, including social networks (Twitter, Facebook), web graphs (Google, BerkStan), and citation networks (DBLP, Citeseer).

Table 1: Comparison of NuMWVC with state-of-the-art solvers MS-ITS and DLSWCC on massive real-world instances. Bold values indicate the best average weight found.

As shown in the experimental results in Table 1, NuMWVC demonstrates superior robustness and speed. On instances where MS-ITS failed to return a valid solution (marked N/A), NuMWVC provided high-quality results efficiently. For example, on the ca-AstroPh dataset, NuMWVC found a superior solution in approximately 543 seconds, whereas MS-ITS required over 16,000 seconds to find a lower-quality solution. Overall, NuMWVC found better or equal solutions compared to DLSWCC in 49 out of 56 instances.

Conclusion

NuMWVC represents a significant advancement in solving the MWVC problem for massive graphs. By combining effective reduction rules with adaptive local search strategies, it achieves a balance between exploration and exploitation that traditional methods lack. Future research may explore the application of SAR and CCA strategies to other combinatorial optimization problems, such as the Maximum Weight Clique problem, and investigate parallelization techniques for even larger datasets.

Reference: Li, R., Cai, S., Hu, S., Yin, M., & Gao, J. (2018). NuMWVC: A Novel Local Search for Minimum Weighted Vertex Cover Problem. Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence (AAAI-18).

Summary updated

BibTeX
@inproceedings{li2018numwvc,
  author = {Ruizhi Li and Shaowei Cai and Shuli Hu and Minghao Yin and Jian Gao},
  title = {{NuMWVC: A Novel Local Search for Minimum Weighted Vertex Cover Problem}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.1609/aaai.v32i1.12137},
}
Figure