Local Search 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.

Local search solvers for MinVC

I have developed several local search solvers for MinVC. The source codes are available below.

FastVC is very simple and works particularly well for massive 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. Note that BMS is a generic probabilistic heuristic for efficiently choosing a good-quality element from a large set.
---Reference: Shaowei Cai: Balance between Complexity and Quality: Local Search for Minimum Vertex Cover in Massive Graphs, Proc. of IJCAI-2015, pp.747-753.
Besides CC, there are two key ideas in NuMVC: two-stage exchange, which selects two vertices to be exchanged separately and performs the exchange in two stages; edge weighting with forgetting, which not only increases weights of uncovered edges but also decreases some weights for each edge periodically.
The performance of NuMVC is much (at least several times) better than previous MinVC local search algorithms.
---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.
  • NuMVC (v2015.8)
  • A more efficient implementation of NuMVC. This version 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.
    ---Reference: 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)
    EWCC is improved from EWLS by using the configuration checking (CC) strategy. Indeed, the CC strategy was first proposed in EWCC.
    CC for MinVC works as follows: given an MVC local search algorithm which maintains a candidate solution C consisting those vertices selected for cover, for a vertex which is not in C, if all its neighboring vertices never change their states (being selected or not for cover) since the last time v was removed from C, then v should not be added back to C.
    ---Reference: Shaowei Cai, Kaile Su, Abdul Sattar: Local search with edge weighting and configuration checking heuristics for minimum vertex cover, Artif. Intell. 175(9-10), 1672-1696 (2011).
    EWLS solves MinVC by iteratively solving its decision version (given a positive integer k, searching for a k-sized vertex cover). It focuses on finding a good partial vertex cover and then extends it to a vertex cover. EWLS is an iterated local search and updates edge weights when it reaches a local optimum. EWLS establishes a new record for a 20-year challenging instance frb100-40.
    ---Reference: Shaowei Cai, Kaile Su, Abdul Sattar: Local search with edge weighting and configuration checking heuristics for minimum vertex cover, Artif. Intell. 175(9-10), 1672-1696 (2011).

    Verfiers for Vertex Cover and Independent Set


    Return to homepage.