2

在一个完整的n分无向图中，每个分集有n个顶点。我的问题是在图中找到一个最小权重n -clique。我想知道这个问题是否可以在多n时间内解决。

条款的更多细节：

Complete k-partite graph：当且仅当它们属于不同的部分集时，顶点相邻的图（维基百科）。图中有 k 个子集。在我的问题中，k = n。

Clique：图 G 中的一个 clique 是 G 的一个完全子图；也就是说，它是顶点的子集 S，使得 S 中的每两个顶点都由 G 中的一条边连接（维基百科）。

Min-weight Clique：图中的每条边都有一个权重。团的权重是团中所有边的权重之和。目标是找到一个权重最小的集团。

请注意，所需 clique 的大小是n，它是完整 n 部图中的最大 clique 大小，并且总是可以实现的。

我已经搜索了几个小时，似乎没有研究解决确切的问题。有什么建议么？

4

2 回答 2

3

是的，通过 CLIQUE 的这种减少是 NP 难的。

令 (G, k) 为 CLIQUE 的实例（确定是否存在基数至少为 k 的集团）。准备一个 k 部图 H，其中 G 中每个顶点的 k 个副本以及两个顶点 v 和 w 之间的边当且仅当它们位于不同的部分并且它们是 G 中相邻顶点的副本。G 中存在一个 k 团当且仅当在 H 中存在一个 k-clique。（使用权重：使现有边的权重为 1，并以权重 0 引入缺失的边。）

（当然这是在文献中，但现在是星期天，我不想看。）

于 2013-07-07T18:41:43.660 回答
0

通过将位置与每个二分集和设施与每个二分集的每个顶点相关联，可以轻松地将二次分配简化为这个问题。与同一设施相关联的两个顶点之间的任何边的权重设置为无穷大。由于二次分配是 NP-hard 的，所以这个问题也是 NP-hard 的。

于 2013-07-07T20:02:33.140 回答