Hong Xu, T. K. Satish Kumar, and Sven Koenig. A new solver for the minimum weighted vertex cover problem. In Proceedings of the 13th International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming (CPAIOR), 392–405. 2016. doi:10.1007/978-3-319-33954-2_28.
[full text] [slides] [BibTeX▼]

Abstract

Given a vertex-weighted graph $$G = \langle V, E \rangle$$, the minimum weighted vertex cover (MWVC) problem is to choose a subset of vertices with minimum total weight such that every edge in the graph has at least one of its endpoints chosen. While there are good solvers for the unweighted version of this NP-hard problem, the weighted version---i.e., the MWVC problem---remains understudied despite its common occurrence in many areas of AI---like combinatorial auctions, weighted constraint satisfaction, and probabilistic reasoning. In this paper, we present a new solver for the MWVC problem based on a novel reformulation to a series of SAT instances using a primal-dual approximation algorithm as a starting point. We show that our SAT-based MWVC solver (SBMS) significantly outperforms other methods.