顶点覆盖问题(Vertex Cover)的描述如下:给定 % <![CDATA[ <G,k> %]]> ,其中 G 是一个无向图,问图中是否存在点集 V % <![CDATA[ \lvert V \rvert <= k %]]> , 使得 V 中的每一个顶点覆盖 G 中所有的边。即 G 中每一条边的起点或终点都为 V 中的一个点。以下图为例, % <![CDATA[ <A,B> %]]> 就是一个符合条件的点集,因为图中的 4 条边,每一条边都连接了 % <![CDATA[ <A,B> %]]> 中至少一个点。

为了证明其 NP 完全,我们首先还是证明其是 NP 问题。给定一个 G 和一个 V ,我们只需要遍历 G 中的每一个边,检查其是否与 V 中一个点相连,即可判定 V 的正确性。显然这个过程是可以在多项式时间内完成了,所以顶点覆盖问题是一个 NP 问题。

接下来,为了证明其是 NP 难问题,我们将 3-SAT 归约到顶点覆盖问题。3-SAT 的形式如下:

\begin{cases} C = C_1 \cap C_2 \cap \cdots \cap C_n \\ C_i = x_a^i \cup x_b^i \cup x_c^i \end{cases}

那么给定一个 3-SAT 表达式,我们作一下操作:

  1. 将每一个簇中的三个变量相互连接。
  2. 将不同簇中不一致的相同变量相连。 不一致的意思是,存在两个不同簇的相同变量 x_a^i x_a^j ,若 x_a^i 为真,则 x_a^j 为假;若 x_a^i 为假,则 x_a^j 为真。

这样我们就把一个 3-SAT 布尔表达式转换成了图,且 k = 2n n 是布尔表达式的簇数。举一个例子,例如一个 3-SAT 布尔表达式为 :

C=(x+y+z) \cdot (\overline{x}+\overline{y}+\overline{z}) \cdot (x+\overline{y}+z) \cdot (\overline{x}+y+\overline{z})

则其按照上述规则,对 C_1 作出的图为:

现在,我们还是来证明两个问题:

(1)若已知一个 3-SAT 问题有解,则其转换后的图 G 在顶点覆盖问题上也有解。因为我们有一个 3-SAT 有解,即 C = 1 。那么对于这个 3-SAT 中每一个簇都至少有一个变量为真。我们取除这个变量外的另外两个变量为顶点覆盖问题中 V 的成员,最后一共可以得到 2n 个成员。由于对于每一簇而言,转换后在图中构成了一个三角形,所以从三角形的 3 个顶点中选出两个顶点必然会包含该三角形所有的边。另一方面,对于每一个变量,其都有与其矛盾的不在一个簇的相同变量相连了。所以只要 3-SAT 问题有解,则对于每一个变量,不管其取值如何,都必然与与其相矛盾的相同变量连接(例如不管 x 取真还是取假,都会与 \overline{x} 相连)。所以 G k = 2n 一定满足,只要对应的 3-SAT 问题满足。

(2)若已知一个顶点覆盖问题 % <![CDATA[ <G, k> %]]> ,其转换后的 3-SAT 也有解。 我们可以将 % <![CDATA[ <G,k> %]]> 通过上述规则逆向转换为布尔表达式,且将 G 中不属于 V 的顶点所对应的变量取真,则 3-SAT 问题为真。

综上所述,我们将 3-SAT 问题归约到了顶点覆盖问题。所以顶点覆盖问题是 NP 完全的。



发现存在错别字或者事实错误?请麻烦您点击 这里 汇报。谢谢您!