2
$\begingroup$

I have a collection of non-empty sets $S_i$, where $1 \le i \le n$, which are constructed from elements of a universe $U$.

I need an algorithm that gives me a set $T$ of minimum cardinality ($T \subseteq U$), such that $T \cap S_i \ne \phi, \forall i$, where $1 \le i \le n$.

I am not sure whether it is an NP-complete problem and can be reduced to minimum set cover in some way. I thought of reducing it to vertex cover, by taking the sets as vertices, and putting an edge between any two sets if their intersection is non-empty, but that doesn't quite seem to work either.

$\endgroup$
6
  • 2
    $\begingroup$ Remember that to show a problem is NP-hard, you must reduce from a hard problem (e.g. set cover) to your problem of unknown hardness. It seems you are thinking the wrong way around. $\endgroup$
    – Juho
    Aug 12, 2015 at 17:47
  • $\begingroup$ OK.. I think I get your point. You mean that if I have a problem P and a known NP-complete problem N, I must show that assuming I have a solution to P, I can plug it into an algorithm which will convert it into a solution for a corresponding instance of N. Something like this.. $\endgroup$ Aug 13, 2015 at 4:07
  • $\begingroup$ N() { <transform instance of N into instance of P>; P(); <transform output of P into a correct answer for our original instance of N> } $\endgroup$ Aug 13, 2015 at 4:11
  • $\begingroup$ If we reduce from P to N rather than the other way around, we might end up taking a polynomial problem and showing it to be exponential, which would be pointless and a very bad idea (but an interesting intellectual exercise!). $\endgroup$ Aug 13, 2015 at 4:15
  • $\begingroup$ Having said that, in actual practice, this is not really something we need to worry about, right? If we can establish a bijection between the sets of problem instances of P and N, and then also a bijection between the sets of expected outputs, we are done. Since a bijection is a double implication, it doesn't really matter. $\endgroup$ Aug 13, 2015 at 4:21

1 Answer 1

2
$\begingroup$

Hint: For each element $x \in U$, let $A_x = \{i : x \in S_i\}$. Then $T$ is a solution to your problem iff $\{A_x : x \in T\}$ covers all of $\{1,\ldots,n\}$. This problem is known as minimum hitting set.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.