9
$\begingroup$

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?
$\endgroup$

1 Answer 1

5
$\begingroup$

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.

$\endgroup$

Your Answer

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