algorithm - 这是NP优化吗？

Question

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

条款的更多细节:

完整的 k 分图:当且仅当它们属于不同的分集 (wikipedia) 时，顶点才相邻的图。图中有 k 个部分集。在我的问题中，k = n。

团:图G中的团是G的完全子图；也就是说，它是顶点的子集 S，使得 S 中的每两个顶点都由 G 中的一条边 (wikipedia) 连接。

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

请注意，所需团的大小为n，这是完整n-分图中最大的团大小，并且总是可以达到的。

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

Answer 1

是的，通过 CLIQUE 的这种归约，它是 NP-hard。

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

(当然这是在文献中，但这是星期天，我不想看。)