Heuristic solvers for Minimum Vertex Cover

Minimum Vertex Cover (MinVC) is to find the minimum sized vertex cover in an undirected graph, where a vertex cover is a vertex set such that every edge in the graph has at least one endpoint in it. MinVC is equivalent to Maximum Clique (MaxClq) and Maximum Independent Set (MaxIS) problems, and MinVC algorithms can be used to solve them directly.

I have developed several heuristic solvers for MinVC, based on the local search method. I maintain the important ones below, and provide their source codes or executable binaries.
The solvers on this page can only be used for research and education purpose.

FastVC

Introduction: FastVC is very simple and works particularly well for massive sparse graphs. It is based on two low-complexity heuristics, one for initial construction of VC, and the other is named Best from Multiple Selection (BMS), which is used to choose the removing vertex in each exchanging step.
Latest version: FastVC 1.1 (Nov. 2015)

Reference:
Shaowei Cai: Balance between Complexity and Quality: Local Search for Minimum Vertex Cover in Massive Graphs, Proc. of IJCAI-2015, pp.747-753.

NuMVC

Introduction: NuMVC has been widely acknowledged as the representative state of the art solver for MinVC. It is steady and robust on a wide range of MinVC benchmarks. It integrates several powerful techniques: configuration checking, two-stage exchange step, edge weighting with forgetting.
Latest version: NuMVC 1.1 (Aug. 2015)
Version 1.1 has two changes, both are about data structure but not algorithmic: 1) replaces big static arrays with dynamic allocated arrays so that NuMVC can handle massive graphs, and 2) uses a heap (an advanced data structure) for initial VC construction, making the algorithm much faster on some massive graphs.
Earlier versions: NuMVC 1.0 (2013)

Reference:
Shaowei Cai, Kaile Su, Chuan Luo, Abdul Sattar: NuMVC: An Efficient Local Search Algorithm for Minimum Vertex Cover, J. Artif. Intell. Res. 46 (2013), pp.687-716.
Shaowei Cai, Jinkun Lin, Chuan Luo: Finding A Small Vertex Cover in Massive Sparse Graphs: Construct, Local Search, and Preprocess. J. Artif. Intell. Res. 59: 463-494 (2017)

Verfiers for Vertex Cover and Independent Set


Return to homepage.