顶点覆盖是NP完全的证明

先决条件—— 顶点覆盖问题 , NP完全性 问题—— 给定一个图G（V，E）和一个正整数k，问题是确定是否存在一个最大k的顶点子集V’，使得图中的每一条边都连接到V’中的某个顶点。

解释—— 首先让我们理解问题实例的概念。问题的实例只不过是给定问题的输入。顶点覆盖问题的一个例子是图G（V，E）和正整数k，该问题是检查G中是否存在最大大小为k的顶点覆盖。根据定义，NP完全问题是一个NP和NP难问题，证明一个问题是NP完全的陈述包括两部分：

1. 顶点覆盖在NP中的证明- 如果任何问题属于NP，那么，给定问题的“证书”（解决方案）和问题的一个实例（在本例中为图G和正整数k），我们将能够在多项式时间内验证（检查给出的解决方案是否正确）证书。

   顶点覆盖问题的证书是V的子集V’，它包含顶点覆盖中的顶点。我们可以使用以下策略（对于图G（V，E）），检查集合V’是否是大小为k的顶点覆盖：

   let count be an integer
   set count to 0
   for each vertex v in V’
       remove all edges adjacent to v from set E
       increment count by 1
       if count = k and E is empty
       then
           the given solution is correct
       else
           the given solution is wrong
   

   显而易见，这可以在多项式时间内完成。因此，顶点覆盖问题属于NP类。
2. 证明顶点覆盖是NP难的—— 为了证明顶点覆盖是NP难的，我们考虑了一些已经被证明是NP难的问题，并证明了这个问题可以归结为顶点覆盖问题。为此，我们考虑团问题，它是NP完全的（因此NP-hard）。
   

   “在计算机科学中，团问题是在图中寻找团（顶点的子集，彼此相邻，也称为完全子图）的计算问题。”

   在这里，我们考虑在给定图中是否存在大小k的团的问题。因此，团问题的一个例子是图G（V，E）和非负整数k，我们需要检查团的存在性 尺寸k英寸。

   现在，我们需要证明团问题的任何实例（G，k）都可以简化为顶点覆盖问题的实例。考虑图G’，它包含所有不在G中的边，但在图中使用G中的所有顶点。我们称之为G的补充。现在，发现图G中是否存在大小k的团的问题与在G′中是否发现席胡的大小V v – k的问题相同。我们需要证明事实的确如此。

   假设G中有一个大小为k的团。让团中的顶点集为V′。这意味着|V’|=k。在补码图G’中，让我们选择任何边（u，V）。那么u或v中至少有一个必须在集合v–v’中。这是因为，如果u和v都来自集合v’，那么边（u，v）将属于v’，这反过来意味着边（u，v）在G中。这是不可能的，因为（u，v）不在G中。因此，G’中的所有边都被集合v–v’中的顶点覆盖。

   现在假设有一个大小为| V |–k的顶点覆盖V”。这意味着G’中的所有边都连接到V’中的某个顶点。因此，如果我们从G’中选取任何边（u，v），它们都不能在集合v’之外。这意味着 使u和v都在集合v之外的边（u，v）在G中，即这些边构成大小为k的团。

因此，我们可以说，图G中存在一个大小为k的团，当且仅当G’中存在一个大小为| V |–k的顶点覆盖，因此，团问题的任何实例都可以简化为顶点覆盖问题的实例。因此，顶点覆盖是NP难的。由于顶点覆盖既属于NP类又属于NP难类，所以它是NP完全的。

为了理解证明，请考虑下面的示例图及其补充：

请参见—— 哈密顿路径是NP完全的证明