2025/08/18 by Rajni Dabas, Samir Khuller, Dabas, Rajni +3 · 1 citation
Computer Science · Engineering · #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Vehicle Routing Optimization Methods
paper · pdf · doi:10.48550/arxiv.2508.13055
openalex publication_date 2025/08/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study generalizations of the classical Vertex Cover and Edge Cover problems that incorporate group-wise coverage constraints. Our first focus is the 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 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(ωn3) \) to \( O(mn+n2 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.