证明多项式时间减少是从 Clique 问题到 Vertex Cover 问题
顶点覆盖是覆盖图中所有边的顶点子集。它用于确定给定的图是否具有3SAT到顶点覆盖。
Clique被称为所有直接连接的顶点的子集。它确定图中是否存在大小为k的团。
证明-顶点覆盖可以减少到集团。
证明
给定一个图G=(V,E)和整数k。
得到它的补图G'=(V,E')。
求解CLIQUE(G',|V|-k)。
如果有解决方案，则返回yes。否则，它返回为no。
为了证明这种减少，我们需要展示以下内容-
如果VERTEX-有解COVER(G,k)，那么CLIQUE(G',|V|-k)必有解，反之亦然。
假设G有一个顶点覆盖V'⊆V，其中|V|'=k。然后，对于所有u,vεV，如果(u,v)εE，则uεV'或vεV'或两者兼而有之，因为顶点覆盖必须覆盖所有边。
矛盾的是，对于所有u,vεV，如果u不属于V'，则(u,v)ε/E并且因此(u,v)εE。
对于任何一对都不在G的顶点覆盖V'中的顶点，它们之间在G中有一条边。
所有不在V'中的顶点对的并集就是V-V'。因此，根据定义，V−V'是G中的一个集团，并且V−V'的大小为|V|-k。
这个操作可以在多项式时间内完成。由于VERTEX-COVER可以在多项式时间内简化为CLIQUE，CLIQUEεNP和VERTEX-COVER是NP-完全的，CLIQUE也是NP-完全的。