有没有办法在一个完全图中找到最小完全子图？

Question

给定一个具有N个顶点的无向赋权完全图G=(V,E)，我想知道寻找具有M个顶点(M <= N)的最小完全子图(具有最小边权和)是否是NP难的。

Answer 1

这个问题是NP-困难的，因为clique problem的决策形式可以归结为NP-hard。

团问题的决策形式是在给定一个无向图和一个整数k的情况下，询问是否存在一个有k个顶点的完全子图。这个问题是NP难的。给定这个问题的一个实例，通过为原始图中存在的任何边分配权重1，为原始图中不存在的任何边分配权重2，在相同数量的顶点上构造一个完整的加权图。那么一个最小权完全子图的每个边权都等于1当且仅当在原始图中有一个大小为k的完全子图。