Minimum number of elements needed from n sets

Question

Suppose that we have n sets. They may or may not have common elements. How can we find the minimum number of elements that we should pick so that we have at least one element from each set? For example if we have $S_1 = {1,2,3}$ and $S_2 = {2,5,7}$ we will pick $2$ in order to minimize our number of picks (we will have 1 pick for 2 sets).

I was thinking about a Greedy approach: to find the number with most appearances and remove the according sets until each 2 sets will be disjoint sets. Then add an element from each set. I guess that the complexity of the Greedy approach will be polynomial.

The problem is that I believe that this problem is NP-complete, so that means that it cannot be solved by a polynomial algorithm. Is the Greedy approach wrong/ is it not polynomial?

Also, could we somehow use the vertex-cover problem from graphs to reduce it to our problem to prove that it is NPC?

Answer 1

This problem is known in the literature as the Hitting Set problem. It was shown to be NP-complete in 1972 by Richard Karp in his seminal paper "Reducibility Among Combinatorial Problems." 21 combinatorial and graph theoretical problems were shown to be NP-complete by many-one reduction from Boolean Satisfiability.

Answer 2

Suppose I have $$S_1=\{1,2,3\}\\S_2=\{1,2,4\}\\S_3=\{1,5,6\}\\S_4=\{1,5,7\}\\S_5=\{2,8,9\}\\S_6=\{5,10,11\}$$ The greedy algorithm will select $1$ first, then needs two more numbers to get the rest. But $\{2,5\}$ provides coverage.