顶点覆盖是覆盖图中所有边的顶点子集。它用于确定给定的图是否具有 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-完全的。