# I want to figure out whether my problem described below is reducible to the set cover problem

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.

• 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.
– Juho
Aug 12, 2015 at 17:47
• 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.. Aug 13, 2015 at 4:07
• N() { <transform instance of N into instance of P>; P(); <transform output of P into a correct answer for our original instance of N> } Aug 13, 2015 at 4:11
• 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!). Aug 13, 2015 at 4:15
• 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. Aug 13, 2015 at 4:21

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.