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

Question

所以我遇到了一个像这样的现实世界问题:我们有一个我们需要分组成对的列表.我们希望最小化我们拥有的组的数量,其中约束是组的任何成员都不能与该组的任何其他成员共享元素.

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

是否有可能在多项式时间内最优地解决这个问题？贪婪的解决方案有多糟糕？这可能是一个不同的问题,但我无法弄清楚如何将它减少到其他东西(图形着色浮现在脑海中).

Answer 1

所述问题可以被认为是边缘着色问题:你有一个图表,其中每个元组条目是一个节点,边缘由元组给出.将元组聚类成组然后对应于查找不共享端点(匹配)的边缘组,然后可以在边缘着色中为其指定相同的颜色.换句话说,每个边缘着色为您提供聚类,每个聚类为您提供边缘着色.不幸的是,这是NP难的找到最好的边染色,所以你的问题是一般NP难的.这个问题有近似算法产生常数因子近似,但除非P = NP,否则没有精确的算法.

如果你将这个问题推广到每个元组允许任意数量的元素,那么这个问题会变得更加困难.这个问题的一般版本确实是NP- hard,并且很难通过图着色的减少来近似.我将展示一个特定案例减少的例子,但它很好地概括了.

给出如下图:

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

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

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

现在,假设这些元组中的两个不重叠.这意味着对应于那些元组的两个节点不能相邻,因为如果它们是,则它们之间的边缘将是元组中的公共元素,因此它们不能被聚类.另一方面,如果两个节点不相邻,则它们的元组可以在同一个集群中组合在一起,因为一个元组中的边不会出现在另一个元组中.

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