Parameterized Approximation for Capacitated d-Hitting Set with Hard Capacities

In the Capacitated d-Hitting Set problem input is a universe U equipped with a capacity function cap : U → N, and a collection A of subsets of U , each of size at most d. The task is to find a minimum size subset S of U and an assignment ϕ : A → S such that, for every set A ∈ A we have ϕ(A) ∈ A and for every x ∈ U we have |ϕ -1 (x)| ≤ cap(x). Here ϕ -1 (x) is the collection of sets in A mapped to x by ϕ. Such a set S is called a capacitated hitting set. When d = 2 the problem is known under the name Capacitated Vertex Cover. In Weighted Capacitated d-Hitting Set each element of U has a positive integer weight and the goal is to find a capacitated hitting set of minimum weight.

Approximation algorithms for Capacitated Vertex Cover were first studied by Chuzhoy and Naor [SICOMP 2006], who gave a factor 3 approximation algorithm for Capacitated Vertex Cover and showed that the weighted version does not admit an o(log n)-approximation unless P=NP. After a series of improvements spanning a period of 15 years, Kao [SODA 2017] and Wong [SODA 2017] independently obtained d-approximation algorithms for Capacitated d-Hitting Set. This matches the ratio for the classic d-Hitting Set problem, and therefore cannot be improved to d-ϵ for any ϵ > 0 assuming the Unique Games Conjecture. Capacitated Vertex Cover is also well understood from the perspective of parameterized algorithms: van Rooij and van Rooij [SOFSEM 2019] gave a k k |U | O(1) time algorithm to determine whether there exists a solution S of size at most k, showing that the unweighted problem is fixed parameter tractable (FPT) parameterized by the solution size k.

In this paper we initiate the study of parameterized (approximation) algorithms for Capacitated d-Hitting Set. An easy reduction shows that, as opposed to Capacitated Vertex Cover, unweighted Capacitated d-Hitting Set for d ≥ 3 does not admit an FPT algorithm unless FPT=W [1]. Our main result is a parameterized approximation algorithm that runs in time k O(1) and either concludes that there is no solution of size at most k or outputs a solution S of size at most 4/3 • k and weight at most 2 + ϵ times the minimum weight of a solution whose size is at most k. We note that while the running time of our algorithm depends on d, the approximation ratio does not. Thus this parameterized approximation