Enhancing Removal Reductions for Finding Minimum Weight Vertex Covers

The Minimum Weight Vertex Cover (MinWVC) problem has applications in clustering aggregation, electronic auctions, map labeling, etc. Given a simple undirected graph, a vertex cover is a vertex subset such that any edge in this graph has endpoints in it. In MinWVC, every vertex has a weight, and the task is to obtain a vertex cover and minimize its total vertex weight, i.e., the MinWVW problem looks for a lightest cover.The reduction approach checks a subgraph and determines whether certain vertices lie in an optimal cover in low complexity. In reality, reductions usually face a trade-off between effectiveness and efficiency. More specifically, the more cases in which they need to examine vertices’ belonging to an optimal solution, the exponentially more run time they consume.This paper presents a general theorem that guides us in finding effective and efficient reduction rules. These rules are not only able to address cases that have already been handled by current rules but are also usable in some other cases, which illustrate the advantages of our approach.