Abstract
Minimum vertex cover (MinVC) is a prominent
NP-hard problem in artificial intelligence, with
considerable importance in applications. Local
search solvers define the state of the art in solving MinVC. However, there is no single MinVC
solver that works best across all types of MinVC
instances, and finding the most suitable solver for
a given application poses considerable challenges.
In this work, we present a new local search framework for MinVC called MetaVC, which is highly
parametric and incorporates many effective local
search techniques. Using an automatic algorithm
configurator, the performance of MetaVC can be
optimized for particular types of MinVC instances.
Through extensive experiments, we demonstrate
that MetaVC significantly outperforms previous
solvers on medium-size hard MinVC instances, and
shows competitive performance on large MinVC
instances. We further introduce a neural-networkbased approach for enhancing the automatic configuration process, by identifying and terminating unpromising configuration runs. Our results demonstrate that MetaVC, when automatically configured
using this method, can achieve improvements in the
best known solutions for 16 large MinVC instances