Capacitated Partition Vertex Cover and Partition Edge Cover

Abstract

Our first focus is the Capacitated Partition Vertex Cover (C-PVC) problem in hypergraphs. In C-PVC, we are given a hypergraph with capacities on its vertices and a partition of the hyperedge set into $\omega$ distinct groups. The objective is to select a minimum size subset of vertices that satisfies two main conditions: (1) in each group, the total number of covered hyperedges meets a specified threshold, and (2) the number of hyperedges assigned to any vertex respects its capacity constraint. A covered hyperedge is required to be assigned to a selected vertex that belongs to the hyperedge. This formulation generalizes classical Vertex Cover, Partial Vertex Cover, and Partition Vertex Cover. We investigate two variants: soft capacitated (multiple copies of a vertex are allowed) and hard capacitated (each vertex can be chosen at most once). Let $f$ denote the rank of the hypergraph (i.e., the maximum number of vertices contained in any single hyperedge). Our main contributions are: $(i)$ an $(f+1)$-approximation algorithm for the weighted soft-capacitated C-PVC problem, which runs in polynomial time for constant \(ω\), and $(ii)$ an $(f+\epsilon )$-approximation algorithm for the unweighted hard-capacitated C-PVC problem, which runs in $n^{O(\omega /\epsilon )}$ time. 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 weight, 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(\omega n^3)$ to $O(mn+n^2\log n)$ and simplifying the algorithmic structure over prior unweighted approaches.