Hitting sets with a subfamily Let $F$ be a family of $d$-element subsets of a finite universe $U$ of objects.
A family $H$ of $k$-element subsets of $U$, with $1 \le k &lt; d$, is a $(k,d)$-hitting-set of $F$ if for each $V \in F$ there exists at least one set $W \in H$ such that $W \subset V$.

Given a collection $F$ as above, the $(k,d)$-hitting-set problem is to find a smallest $(k,d)$-hitting-set $H$ for $F$.

When $k = 1$ we have the standard hitting-set problem, and there are lots of previous results for it.
I know of parameterized analyses for the case with $k = 1$ and $d \le 3$ (see Brankovic and Fernau, for example).

Does anyone know any results regarding the complexity or the hardness of approximation of the $(k,d)$-hitting-set problem with:


$k = 1$ and $d = 4$?
$d = 4$ and $1 &lt; k &lt; d$?
$1 \le k &lt; d$ and $d$ arbitrary?
For a constant $d$ the $(k,d)$-hitting set problem is not harder than the original $d$-hitting set (i.e. $k=1$) in view of both approximation and parametrized complexity.
There is a simple reduction from $kd$-HS to $d$-HS. For an instance $(U,\mathcal{F},d,k)$ of the first problem we get an instance of $(U',\mathcal{F'},d)$ of the second one in which every element $e \in U'$ corresponds to a $k$-element subset of $U$, and each set in $\mathcal{F'}$ corresponds to a set in $\mathcal{F}$ in the same way (i.e. mapping all $k$-element subsets of $U$ to elements in $U'$). Since $k$ is a constant the size of new instance is a polynomial function of the size of the first instance ($O(n^k)$).
A hitting set for the first problem corresponds to a hitting set of same cardinality for the second problem and vice versa, hence the reduction is approximation preserving.