Combinatorial Optimization on Graphs
[Introduction][Vertex Cover Problems] [Clique Problems ] [Coloring Problems] [Graph Benchmarks]
Heuristic algorithms 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.
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.
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.
Heuristic algorithms for Minimum Weight Vertex Cover
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 on massive sparse graphs
Latest version: FastWVC (2018)
Reference:
Shaowei Cai, Yuanjie Li, Wenying Hou, Haoran Wang: Towards faster local search for minimum weight vertex cover on massive graphs. Inf. Sci. 471: 64-79 (2019)
DynWVC
Introduction: DynWVC is a local search solver for MWVC, which uses dynamic strategies for scoring function and vertex selection heuristics. It performs well on both massive graphs (better than FastWVC) and real world application benchmarks on map labelling.
Latest version: DynWVC2 (2018)
Reference:
Shaowei Cai, Wenying Hou, Jinkun Lin, Yuanjie Li: Improving Local Search for Minimum Weight Vertex Cover by Dynamic Strategies. IJCAI 2018: 1412-1418
Verfiers for Vertex Cover and Independent Set
- Here is a verifier program for the vertex cover problem, which verifies whether a given solution (vertex set) is a vertex cover of a given graph (in DIMACS format).
- Here is a verifier program for the independent set problem, which verifies whether a given solution (vertex set) is an independent set of a given graph (in DIMACS format).