寻找最小组件集合的算法

我正在寻找一种算法来解决以下问题。我有给定集合 (a-h) 的多个子集 (1-n)。我想找到最小的子集集合，它允许我通过组合来构造所有给定的子集。该集合可以包含 1-n 中尚不存在的子集。

  a b c d e f g h
1 1
2 1   1
3   1     1   1
4 1       1
5   1         1
6 1     1   1   1
7 1       1 1   1
8 1   1       1
9 1         1   1

下面是两个可能的集合，其中最小的包含七个子集。我用 x 表示新的子集。

1 1
x   1
x     1
x       1
x         1
x           1
x             1
x               1

1 1
x   1         
x     1
x       1        
x         1    
x           1   1
x             1

我相信这一定是一个已知的问题，但我对算法不是很熟悉。非常感谢任何帮助，以及更好的主题标题的建议。

Thanks!

Update

图形着色让我受益匪浅，谢谢。然而，就我而言，子集是允许重叠的。例如：

  a b c d
1 1 1 1  
2 1 1 1 
3 1 1 1
4     1 1
5 1 1 1 1

图形着色给了我这个解决方案：

x 1 1
x     1
x       1     

但这也是有效的，而且更小：

1 1 1 1  
4     1 1

这个问题被称为集合基础，它是 NP 完全的（Larry J. Stockmeyer：集合基础问题是 NP 完全的。技术报告 RC-5431，IBM，1975）。其图问题的表述为二分维数 http://en.wikipedia.org/wiki/Bipartite_dimension。由于一般来说很难解决，因此查看数据是否有任何有用的属性可能会很有用（例如，集合很小吗？解决方案很小吗？所有集合都可以出现吗？）

我想不出一个简单的 ILP 公式。相反，您可以尝试将问题简化为 Clique Cover，这已得到更好的研究，可以使用以下任一简化方法：或来自也不是等人。 http://dx.doi.org/10.1007/978-3-642-13509-5_19。我已经写了一篇论文讨论Clique Cover 的算法 http://dx.doi.org/10.1145/1412228.1412236，并写了一个派系覆盖解算器 http://www.user.tu-berlin.de/hueffner/ecc/具有精确求解器和两种启发式方法。