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 Independent Set (MaxIS) problems, and also Maximum Clique (MaxClq) of the complementary graphs, and MinVC algorithms can be used to solve them directly.

I have developed several heuristic solvers for MinVC, based on the local search method.
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.

Minimum Weight Vertex Cover (MWVC) problem is a generalized version of MVC on vertex weighted graphs, and the goal is to find a vertex cover with as small weight as possible.

FastWVC

Introduction: FastWVC is a local search solver for MWVC, and it works particularly well for massive sparse graphs
Latest version: FastWVC (2018)

Verfiers for Vertex Cover and Independent Set


Return to homepage.