Proceedings

InfVC: An Inference-Enhanced Local Search Algorithm for the Minimum Vertex Cover Problem in Massive Graphs

Rui Sun, Peiyan Liu, Yiyuan Wang, Zhaohui Liu, Liping Du, Jian Gao

Download BibTeX Cite

Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence. Main Track. Pages 8977-8986.

https://doi.org/10.24963/ijcai.2025/998

Keywords

  • Search: S: Local search
  • Search: S: Heuristic search

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.

Rui Sun, Peiyan Liu, Yiyuan Wang, Zhaohui Liu, Liping Du, and Jian Gao. 2025. InfVC: An Inference-Enhanced Local Search Algorithm for the Minimum Vertex Cover Problem in Massive Graphs. In Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-25. IJCAI, 8977–8986. https://doi.org/10.24963/ijcai.2025/998
Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards