set cover where only certain special subsets are allowed I am trying to solve a problem which turns out to be a form of the set cover problem. I've implemented the greedy Set cover approximation algorithm for set cover, but it turns out to not be accurate enough for my needs.

Specifically I have a fixed, finite, list of special sets and I am trying to create a function which when given a set returns the smallest list of special sets which cover that given set, and that list should contain no sets which contain elements not in that given set. The fixed list seems like it should make the problem easier to solve than set cover, but I'm not sure how the additional requirement of no extra elements affects the difficulty. My sets also have a known maximum size which should also make this easier to solve. 

A toy version of the problem is as follows:


  Let $U$ be the set $\{a,b,c,d,e,f,g,h\}$. All the sets we mention from
  here on will be subsets of this set.
  
  Let $S$ be a list of special sets. For this version of the problem we
  can use the following list: 
  
  $$ S = [\{a,b,c,d,e,f,g,h\}, \{a,b,c,d\}, \{e,f,g,h\}, \{a,e\}, \{b,f\}, \{c,g\}, \{d,h\}, \{a,b\}, \{b,c\}, \{c,d\}, \{d,e\}, \{e,f\}, \{f,g\},\{g,h\}, \{a\}, \{b\}, \{c\}, \{d\}, \{e\}, \{f\}, \{g\}, \{h\}]$$
  
  For a given set $G$ what is the smallest list of sets which are part
  of $S$ which cover $G$, (that is where the union of the sets in the
  list is $G$).


For the above toy problem, the greedy approximation I've implemented, if presented with a set like $\{b, c, g, h\}$, produces $[\{c, g\}, \{b\}, \{h\}]$ instead of the smaller list $[\{b, c\}, \{g, h\}]$.

Has this sort of problem been well studied? Is there a known non-approximate algorithm given the additional constraints, that would be better than naive dynamic programming? A well-known name for the version of set cover where extra elements are not allowed would also be useful.
Your problem is hardly easier than the general set cover problem.


Given a set $G=\{b, c, g, h\}$, we remove all elements in $S$ that are not contained in $G$, obtaining a collection of set $C=[\{c,g\}, \{b,c\}, \{g,h\}, \{b\}, \{c\}, \{g\}, \{h\}]$. Now the problem becomes the standard set cover problem with $G$ being the universe and a collection of 7 subsets. Since this reduction process takes $O(n^2)$ time where $n$ is the total number of elements in $U$, your problem cannot not significant easier than the general set cover problem unless there are further conditions to be exploited.

Unfortunately, the general set cover problem is NP-hard. It is one of Karp's 21 NP-complete problems. Even more unfortunately, the simple greedy algorithm achieves about the best approximation ratio, $H(s')$, where $S'$ is the maximum cardinality of the sets. Here $H(n)$ is the $n$-th harmonic number.

If you have to obtain the exact minimum set cover, you will have to resort to exponential algorithms. One simple simplification that can be done is to remove all elements in $C$ that are subsets of another element of $C$. That is, we can replace $C$ by $[\{c,g\}, \{b,c\}, \{g,h\}]$. A simple brute force algorithm is just to test all subsets of $C$ of size 1, those of size 2, those of size 3, etc. A common way to attack the problem is by integer linear programming.

Just in case, you might want to take a look at some literature on the set cover problems. For example, An Exact Algorithm for Unicost Set Covering and LP techniques for set cover.