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:

  1. $k = 1$ and $d = 4$?
  2. $d = 4$ and $1 < k < d$?
  3. $1 \le k < d$ and $d$ arbitrary?

1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.