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$
  • 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 '15 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$ – Vinod Chandrasekaran Aug 13 '15 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$ – Vinod Chandrasekaran Aug 13 '15 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$ – Vinod Chandrasekaran Aug 13 '15 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$ – Vinod Chandrasekaran Aug 13 '15 at 4:21
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$

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.