122
Capacitated Partition Vertex Cover and Partition Edge Cover
arXiv:2512.17844v1 Announce Type: new
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 primary 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. Our main contributions are: $(i)$ an $(f+1)$-approximation algorithm for the weighted soft-capacitated C-PVC problem, which runs in $n^{O(\omega)}$ time, 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.
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 primary 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. Our main contributions are: $(i)$ an $(f+1)$-approximation algorithm for the weighted soft-capacitated C-PVC problem, which runs in $n^{O(\omega)}$ time, 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.
Anonymous
No comments yet.