algorithm - 组元组，使得组中的每个项目与其他成​​员不共享共同元素

Question

所以我遇到了一个现实世界的问题，它是这样的:我们有一个对列表，我们需要将它们分类到组中。我们希望最大限度地减少我们拥有的组总数，并限制组中的任何成员不能与组中的任何其他成员共享元素。

这是一个例子。我们的元组列表是 (A, B), (B, C), (C, A), (D, E), (F, G)。我们可以通过 [(A, B), (D, E), (F, G)], [(B, C)], [(C, A)] 来组成三组。

是否可以在多项式时间内最优地解决这个问题？贪婪的解决方案有多糟糕？这可能是作为一个不同的问题提出的，但我不太清楚如何将它减少到其他问题(想到图形着色)。

Answer 1

所述问题可以被认为是 edge-coloring problem :你有一个图，其中每个元组条目都是一个节点，边由元组给出。然后将元组聚类成组对应于查找不共享端点(匹配)的边组，然后可以在边着色中为这些边分配相同的颜色。换句话说，每个边着色都会给你一个聚类，每个聚类都会给你一个边着色。不幸的是，找到最佳边缘着色是 NP-hard，因此您的问题通常是 NP-hard。有针对此问题的近似算法可以产生常数因子近似值，但除非 P=NP 否则没有确切的算法。

如果您将此问题泛化为每个元组允许任意数量的元素，那么此问题会变得更加困难。这个问题的一般版本确实是NP-hard，并且很难通过图形着色的减少来近似。我将在特定情况下展示一个减少的例子，但它概括得很好。

给定这样一张图:

 A -- B -- C
 |    |    |
 D -- E -- F

我们将创建一组元组，每个节点一个，其中元组中的每个条目都是与该节点相邻的一组边。例如，在上图中，我们将形成这些元组:

( AB, AD )
( AB, BC, BE )
( CB, CF )
( AD, DE )
( BE, DE, EF )
( CF, EF)

现在，假设其中两个元组不重叠。这意味着对应于这些元组的两个节点不能相邻，因为如果它们相邻，它们之间的边将是元组中的公共(public)元素，因此它们不能聚类。另一方面，如果两个节点不相邻，则它们的元组可以组合在同一个簇中，因为一个元组中的边不会出现在另一个元组中。

鉴于此设置，原始图的任何着色都提供了一种聚类元组的方法(将给定相同颜色的节点的所有元组放入同一组；它们都不相邻，因此它们不会冲突)，并且对元组进行聚类的任何方式都会给出一种着色(将与聚类中每个元组对应的所有节点着色为相同的颜色)。因此，找到最小簇数对应于找到原始图的色数，这是NP-hard 并且不知道承认任何接近真实值的近似算法。