1
$\begingroup$

I am pretty sure this problem has a name, or it can be reworded so it does. We are given a set $X$ and a family $\mathcal F$ of subsets of $X$, the problem is to find a subset $B$ such that $B\cap A\neq \emptyset$ for all $A\in \mathcal F$.

$\endgroup$
8
  • 7
    $\begingroup$ MINIMUM HITTING SET (NP-complete) $\endgroup$ Commented Jan 9, 2015 at 16:43
  • $\begingroup$ Thank you very much, was this question on topic here, or was it bad? $\endgroup$
    – user13448
    Commented Jan 9, 2015 at 16:47
  • $\begingroup$ What if the problem is to count the number of minimum hitting sets? $\endgroup$
    – user13448
    Commented Jan 9, 2015 at 16:54
  • $\begingroup$ What if the problem is to count the number of hitting sets? Even those which ar not minimum? $\endgroup$
    – user13448
    Commented Jan 9, 2015 at 17:02
  • 1
    $\begingroup$ The problem remains in #P if you set $k= |X|$ (i.e. you want to count all the possible hitting sets). $\endgroup$ Commented Jan 9, 2015 at 17:23

0

Your Answer

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