A local search algorithm to solve the NP-Hard Minimum-Weighted Vertex Cover (MWVC) problem. This is my C++ implementation of the original FastWVC algorithm with some slight changes, referenced from the paper Towards faster local search for minimum weight vertex cover on massive graphs, published in 2018. A copy of the paper is uploaded in this repository.
Instead of employing a typical deterministic universal, optimal or approximation algorithm, local search is a heuristic "stop anytime" method which moves between candidate solutions by applying local changes, until a candidate is deemed sufficiently optimal or until the time bound is reached. "Stochastic" implies an aspect of randomness in this process. In this case, local changes are applied by removing and then adding (somewhat random) candidate nodes from the current cover to reach a new candidate solution, until it has been running for 2 seconds. Details are commented in fastwvc.cpp.
This algorithm was developed for and tested on the Kattis problem Minimum Weighted Vertex Cover. It sets a time limit of 2 seconds. Specifics can be found here.
- Build the executable with your favourite C++ compiler
clang++ fastwvc.cpp -std=c++20 -o fastwvc
- Run the executable with the graph input
./fastwvc
8 9
1 1 999 1 1 1 999 100
0 1
1 2
1 4
2 3
2 5
3 6
4 5
5 6
6 7
This implementation scores a 35.69/40 on Kattis, where 40 means an optimal result for all 40 input graphs.