InfVC: An Inference-Enhanced Local Search Algorithm for the Minimum Vertex Cover Problem in Massive Graphs
Abstract
The minimum vertex cover (MVC) problem is a classic NP-hard combinatorial optimization problem with extensive real-world applications. In this paper, we propose an efficient local search algorithm, InfVC, to solve the MVC in massive graphs, which comprises three ideas. First, we introduce an inference-driven optimization strategy that explores better feasible solutions through inference rules. Second, we develop a structural-determined perturbation strategy that is motivated by the structure features of high-quality solutions, prioritizing high-degree vertices into the candidate solution to guide the search process to some potential high-quality search area. Third, we design a self-adaptive local search framework that dynamically balances exploration and exploitation through a perturbation management mechanism. Extensive experiments demonstrate that InfVC outperforms all the state-of-the-art algorithms on almost massive instances.
Cite
Text
Sun et al. "InfVC: An Inference-Enhanced Local Search Algorithm for the Minimum Vertex Cover Problem in Massive Graphs." International Joint Conference on Artificial Intelligence, 2025. doi:10.24963/IJCAI.2025/998Markdown
[Sun et al. "InfVC: An Inference-Enhanced Local Search Algorithm for the Minimum Vertex Cover Problem in Massive Graphs." International Joint Conference on Artificial Intelligence, 2025.](https://mlanthology.org/ijcai/2025/sun2025ijcai-infvc/) doi:10.24963/IJCAI.2025/998BibTeX
@inproceedings{sun2025ijcai-infvc,
title = {{InfVC: An Inference-Enhanced Local Search Algorithm for the Minimum Vertex Cover Problem in Massive Graphs}},
author = {Sun, Rui and Liu, Peiyan and Wang, Yiyuan and Liu, Zhaohui and Du, Liping and Gao, Jian},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2025},
pages = {8977-8986},
doi = {10.24963/IJCAI.2025/998},
url = {https://mlanthology.org/ijcai/2025/sun2025ijcai-infvc/}
}