This paper introduces the target-constrained mixed graph cover (TMGC) problem. Given a graph with n vertices and m edges, where each element (vertex or edge) is assigned a cost and a weight, the goal is to select a minimum-cost subset of elements subject to the covering-target constraint that its covered weight – the total weight of the selected vertices, selected edges, and edges incident to the selected vertices – meets or exceeds a given threshold. The TMGC problem models real-world scenarios, such as optimizing the removal of facilities (represented by vertices) and roads (represented by edges) in a network, while ensuring the value of the remaining network (including the value of remaining facilities and their connecting roads) stays below a set limit. From a theoretical perspective, the 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 that runs in <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$O((n+m)\log (n+m))$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <mo stretchy="false">(</mo> <mi>n</mi> <mo>+</mo> <mi>m</mi> <mo stretchy="false">)</mo> <mo>log</mo> <mo stretchy="false">(</mo> <mi>n</mi> <mo>+</mo> <mi>m</mi> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> time. Notably, the ratio 2 aligns with the known lower bound for the simpler vertex cover problem. Moreover, when the algorithm is applied exclusively to vertex selections (i.e., assuming infinite edge costs), the runtime is reduced to <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$O(n\log n+m)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo>log</mo> <mi>n</mi> <mo>+</mo> <mi>m</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>, matching the efficiency of the current fastest 2-approximation for vertex cover. Our technique extends to a variant of TMGC in which selected edges cover their end-vertices in addition to themselves. The primal-dual approach yields an approximation ratio equal to the graph’s maximum degree (or 2, if the maximum degree is smaller).

Minimum-Cost Mixed Graph Covers with Targeted Weight Constraints

期刊论文
发表日期：

2026年2月4日

查看全文

Xujin Chen,
Xiyuan Deng,
Xiaodong Hu,
Changjun Wang

摘要

This paper introduces the target-constrained mixed graph cover (TMGC) problem. Given a graph with n vertices and m edges, where each element (vertex or edge) is assigned a cost and a weight, the goal is to select a minimum-cost subset of elements subject to the covering-target constraint that its covered weight – the total weight of the selected vertices, selected edges, and edges incident to the selected vertices – meets or exceeds a given threshold. The TMGC problem models real-world scenarios, such as optimizing the removal of facilities (represented by vertices) and roads (represented by edges) in a network, while ensuring the value of the remaining network (including the value of remaining facilities and their connecting roads) stays below a set limit. From a theoretical perspective, the 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 that runs in $O((n+m)\log (n+m))$ $O ((n + m) log (n + m))$ time. Notably, the ratio 2 aligns with the known lower bound for the simpler vertex cover problem. Moreover, when the algorithm is applied exclusively to vertex selections (i.e., assuming infinite edge costs), the runtime is reduced to $O(n\log n+m)$ $O (n log n + m)$ , matching the efficiency of the current fastest 2-approximation for vertex cover. Our technique extends to a variant of TMGC in which selected edges cover their end-vertices in addition to themselves. The primal-dual approach yields an approximation ratio equal to the graph’s maximum degree (or 2, if the maximum degree is smaller).