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.

Improve this question
$\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
    Commented 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$
    – Vinod Chandrasekaran
    Commented 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$
    – Vinod Chandrasekaran
    Commented 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$
    – Vinod Chandrasekaran
    Commented 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$
    – Vinod Chandrasekaran
    Commented Aug 13, 2015 at 4:21

1 Answer 1

Reset to default
3
$\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.

Improve this answer
$\endgroup$
0

Your Answer

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

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