Parameterized Approximation for Capacitated d -Hitting Set with Hard Capacities
Daniel Lokshtanov, Abhishek Sahu, Saket Saurabh, Vaishali Surianarayanan, Jie Xue · Society for Industrial and Applied Mathematics eBooks · 2025
In the CAPACITATED d-HlTTING Set problem input is a universe U equipped with a capacity function cap : U → ℕ, 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 and for every x ∈ U we have |φ-1(χ)| ≤ cap(x ). Here φ-1(χ) 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-HlTTING Set each element of U has a positive integer weight and the goal is to find a capacitated hitting set of minimum weight.