Given a set of elements and each of those elements have features (out of a finite set). What algorithm can I use to find the smallest set of features so that every element would have at least one of those features?
I try to look at using the Set Cover algorithm, but cannot find how to use it here.
In addition, if I add another constraint of picking a maximum of $k$ features, how can I find the set that would provide the most coverage?
For example. If I have all the flag of countries in the world, each of them have some colors (assuming there is no flag with gradients here). How can I find the smallest set of colors so that every flag has at least one of those color.
If I have
F = { USA, France, Germany, Italy, Sweden, Romania, Gabon }
USA -> { red, white, blue }
France -> { blue, white, red }
Germany -> { black, red, yellow }
Italy -> { red, white, green }
Sweden -> { blue, yellow }
Romania -> { blue, yellow, red }
Gabon -> { green, yellow, blue }
C = { red, blue, white, black, yellow, green, orange }
I would like the algorithm to return:
{yellow, red}
To your first question: What you are given is exactly the set cover problem: You have $n$ elements and $m$ sets of those elements (For each attribute you can group all elements with that attribute in one set). Note that this is known to be NP-complete. On Wikipedia https://en.wikipedia.org/wiki/Set_cover_problem you can find out how to solve it using ILP.
Update:
Note that your second problem is also NP-complete because it is more general than your first problem. In other words: If you can solve your second problem in general then this gives you a method to solve your first problem.