Mixed Graph Covering with Target Constraints
摘要
The target-constrained mixed graph covering (TMGC) problem considers a graph where edges and vertices are each assigned a cost and a weight. The goal is to select a minimum-cost subset of vertices and edges subject to the covering-target constraint that its covered weight (i.e., the total weight of the selected vertices, selected edges, and edges incident to the selected vertices) meets or exceeds a given threshold. This problem models real-world scenarios, like optimizing the removal of facilities (vertices) and roads (edges) in a network while ensuring the value of the remaining network (including the value of remaining facilities and their connecting roads) remains below a specified limit. From a theoretical perspective, this TMGC model extends the weighted partial vertex cover problem in two significant ways: it incorporates covering weights for both edges and vertices, and it allows a direct selection of edges alongside vertices to satisfy the covering target. Despite this increased complexity and generality compared to (the partial version of) the classic vertex cover problem, we develop a 2-approximation primal-dual algorithm for TMGC, whose ratio 2 matches the known lower bound for the simpler vertex cover problem.