---
title: "InfVC: An Inference-Enhanced Local Search Algorithm for the Minimum Vertex Cover Problem in Massive Graphs"
authors:
  - "Rui Sun"
  - "Peiyan Liu"
  - "Yiyuan Wang"
  - "Zhaohui Liu"
  - "Liping Du"
  - "Jian Gao"
doi: "10.24963/ijcai.2025/998"
url: "https://ijcai.org/proceedings/2025/998"
pdf: "https://ijcai.org/proceedings/2025/0998.pdf"
venue: "Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence"
year: 2025
pages: "8977-8986"
track: "Main Track"
keywords:
  - "Search: S: Local search"
  - "Search: S: Heuristic search"
---

# 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

*Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence*, pages 8977-8986. DOI: [10.24963/ijcai.2025/998](https://doi.org/10.24963/ijcai.2025/998)

## 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.