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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Mixed Graph Covering with Target Constraints

  • Xujin Chen,
  • Xiyuan Deng,
  • Xiaodong Hu,
  • Changjun Wang

摘要

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.