2026-09-10T09:44:54Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27725 2026-09-09T12:19:35Z ddc:004 open_access

Capacitated Partition Vertex Cover and Partition Edge Cover Dabas, Rajni Khuller, Samir Rivkin, Emilie Approximation algorithms capacitated vertex cover iterative rounding We study generalizations of the classical Vertex Cover and Edge Cover problems that incorporate group-wise coverage. 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 ω 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 (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 n^O(ω) time, and (ii) an (f+ε)-approximation algorithm for the unweighted hard-capacitated C-PVC problem, which runs in n^O(ω/ε) time. 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 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(ω n³) to O(mn + n²log n) and simplifying the algorithmic structure over prior unweighted approaches (that rely on the tropical matching problem). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Rajni Dabas and Samir Khuller and Emilie Rivkin 2026 Is Part Of LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2026.8 urn:nbn:de:0030-drops-277257 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.8 eng https://creativecommons.org/licenses/by/4.0/legalcode