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

Question

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.

Answer 1

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.

Answer 2

You would get the solution by finding the union of all the sets, then picking one element of each set and removing it from the solution set. Problem is which element to pick :-( By picking the same value in several sets, you reduce the number of values that are actually removed from the superset.

If a set has no element that is a member of another set, then we pick any element, and it makes no difference. If there are elements that are members of other sets, then there is always an optimal solution where we picked an element that was a member of another set. In the example, that's enough to solve the problem: The union of the numbers is { 1, 2, 3, 4, 5, 6, 7 }. We remove the 7 since { 7 } has this element, but no other set does. From the remaining sets we have to remove according to the rules above the numbers 2, 2 or 3, 3 or 4, and 4. We remove 2 and 4 because we have to which solves the problem.