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 < 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 < k < d$?
- $1 \le k < d$ and $d$ arbitrary?