optimization - 涵盖元素的子集的最小列表

Question

给定一个包含元素的集合列表：

[setA: {a, b, e},
 setB: {d, e, c}.
 setC: {a, d}
]

L以及需要涵盖的元素列表：[x, y, z, ...]

从 L 中找到最小的集合列表，其并集包含列表中的所有元素L。

这个问题是否与 Set-Cover 相同（暗示它是 NP-Complete）？或者我是否缺少一些使它易于处理的东西？

假设可以确定元素 x 是否存在于恒定时间内的集合中。

标签： optimizationsetset-cover

Answer 1

你有两个列表。第一个是集合L ₁的列表，而第二个是覆盖L ₂的元素列表。在多项式时间内从L ₁中的每个集合中丢弃所有不在L ₂中的元素， 您将得到集合覆盖问题。因此，如果您有一个多项式时间算法来解决您的问题，那么您也将获得 Set Cover 问题的多项式时间答案。