Given an amount of sets with numbers, find a set of numbers not including any of the given

Given an amount of sets with numbers (0-20 e.g) , we are asked to find the maximum set of numbers from 0-20 that doesn't include any of the given sets(it can include numbers from a set,but not the whole set) For example :Setting the max number 8 and given the sets

{1,2}
{2,3}
{7}
{3,4}
{5,6,4},
one maximum solution is the set {1, 3, 5, 6, 8}. I was thinking of representing it as a graph and then inducting it to the Max Independent Set problem, but that seems to work only if the sets were consisted only from pairs,which doesn't stand.Any idea?Thanks in advance.

I was thinking of representing it as a graph and then inducting it to the Max Independent Set problem

I think that´s a good start. The problem you are looking for is independent set but in hypergraphs instead of regular graphs.

The opposite of the independent set problem in hypergraphs is the vertex cover problem as it is in regular graphs. Well, that problem is equal to the hitting set problem: https://en.wikipedia.org/wiki/Vertex_cover#Vertex_cover_in_hypergraphs.

Something that i will do is:

• Sepparate from the universe set all elements that doesn´t appear in a given set and insert those elements inside the solution set: In your example the number 8. So the universe will be $\{1, 2, 3, 4, 5, 6, 7\}$ and the solution set will be $\{8\}$

• Transform the hitting set instance into set cover. We will have the following subsets in your example: $\{1\}$ , $\{1, 2\}$ , $\{2, 4\}$, $\{4,5\}$, $\{5\}$, $\{5\}$, $\{3\}$.

• We find the minimum hitting set and we pick the complement of the minimum hitting set, we add those elements to the solution set and we are done. In your example the minimum hitting set will be: $\{2, 4, 7\}$. The complement will be $\{1, 3 ,5 ,6\}$. By adding the elements of the complement set to the solution set we have the solution to the problem.

StackExchange Computer Science Q#41793, answer score: 2