{"ID":2881209,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.13055","arxiv_id":"2508.13055","title":"Weighted Partition Vertex and Edge Cover","abstract":"We study generalizations of the classical Vertex Cover and Edge Cover problems that incorporate group-wise coverage constraints. Our first focus is the \\emph{Weighted Prize-Collecting Partition Vertex Cover} (WP-PVC) problem: given a graph with weights on both vertices and edges, and a partition of the edge set into $ω$ groups, the goal is to select a minimum-weight subset of vertices such that, in each group, the total weight (profit) of covered edges meets a specified threshold. This formulation generalizes classical vertex cover, partial vertex cover and partition vertex cover. We present two algorithms for WP-PVC. The first is a simple 2-approximation that solves \\( n^ω \\) LP's, improving over prior work by Bandyapadhyay et al.\\ by removing an enumerative step and the extra \\( ε\\)-factor in approximation, while also extending to the weighted setting. The second is a bi-criteria algorithm that applies when \\( ω\\) is large, approximately meeting profit targets with a bounded LP-relative cost. We also study a natural generalization of the edge cover problem, the \\emph{Weighted Partition Edge Cover} (W-PEC) problem, where each edge has an associated weights, and the vertex set is partitioned into groups. For each group, the goal is to cover at least a specified number of vertices using incident edges, while minimizing the total weight of the selected edges. We present the first exact polynomial-time algorithm for the weighted case, improving runtime from \\( O(ωn^3) \\) to \\( O(mn+n^2 \\log n) \\) and simplifying the algorithmic structure over prior unweighted approaches. We also show that the prize-collecting variant of the W-PEC problem is NP-Complete via a reduction from the knapsack problem.","short_abstract":"We study generalizations of the classical Vertex Cover and Edge Cover problems that incorporate group-wise coverage constraints. Our first focus is the \\emph{Weighted Prize-Collecting Partition Vertex Cover} (WP-PVC) problem: given a graph with weights on both vertices and edges, and a partition of the edge set into $ω...","url_abs":"https://arxiv.org/abs/2508.13055","url_pdf":"https://arxiv.org/pdf/2508.13055v1","authors":"[\"Rajni Dabas\",\"Samir Khuller\",\"Emilie Rivkin\"]","published":"2025-08-18T16:20:58Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}