Soptq

Soptq

Probably a full-stack, mainly focusing on Distributed System / Consensus / Privacy-preserving Tech etc. Decentralization is a trend, privacy must be protected.
twitter
github
bilibili

顶点覆盖问题 NP-Complete 证明

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

点集

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

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

{C=C1C2CnCi=xaixbixci\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. 将不同簇中不一致的相同变量相连。 不一致的意思是,存在两个不同簇的相同变量 xaix_a^ixajx_a^j,若 xaix_a^i 为真,则 xajx_a^j 为假;若 xaix_a^i 为假,则 xajx_a^j 为真。

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

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

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

3-SAT 实例

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

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

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

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

加载中...
此文章数据所有权由区块链加密技术和智能合约保障仅归创作者所有。