算法设计与分析笔记——顶点覆盖问题VC的NP完全性证明
之前在算法设计与分析笔记——NP完全性中总结了证明NPC的思路，本文总结由三元可满足性（3SAT）到顶点覆盖（VC）的NP完全性证明。
定义
3SAT：合取范式中每个简单析取式恰好有3个文字，则称之为3元合取范式。给一个3元合区范式F，问F是可满足的吗？
顶点覆盖：任给一个无向图G=<V, E>，再给一个非负整数K<=|V|，问G中有顶点数不超过K的顶点覆盖吗？
思路
1、显然VC∈NP，因为可以在O(n ^ 2)（n是顶点数）的多项式时间内检查所有的边，看是否包含了所有顶点。
2、把3SAT当成已知的NPC问题，接下来尝试把3SAT规约到VC，若VC比3SAT还难，那必然也是NPC。
证明
取3SAT的一个实例F，向着VC问题变换。
使用构件设计法，构造两组连接：
第一组，把每个文字与它的非连起来，称为变元构件，这组边集记为E1：
第二组，把每个括号中的三个文字如（xi, xj, xk）连起来，称为简单析取构件，这组边集记为E2：
最后把这两组中相同的文字连起来，这组边集记为E3。
例如由F = (x1 V x1 V x2) ∩ (!x1 V !x2 V !x2) ∩ (!x1 V x2 V x2) 构造出下面的图G：
先说结论：设语句有n个文字，m个语句（括号），F是可满足的当且仅当图中有顶点数不超过K = n + 2m 的顶点覆盖。
F中哪个顶点值为1，就表示选取哪个顶点，这样就建立了G到F的联系。
先证由3-SAT为真对应K = n + 2m的顶点覆盖：
-
xi和!xi中，必有一个为1，上面的变元构件组成的边集E1总能被覆盖掉，此时选了n个顶点了。
-
为了覆盖下面三角形的三条边（边集E2），最少得选两个顶点。上一步中，上面选到的点连到三角形中的某个顶点，该顶点就不再考虑了，选剩下的两个点，这样能保证边集E3也能同时完成覆盖。这样又选了2m个点，一共是n + 2m个完成了覆盖。
比如F的一个满足赋值：x1 = 0， x2 = 1，对应的覆盖如下图所示：
再证由存在K = n + 2m的顶点覆盖集Vc对应3-SAT为真的取值：
- 上面每对xi和!xi中必有一个属于Vc，下面三角形中必有两个顶点属于Vc；
- 三角形中有一个未被取到的顶点，为了覆盖掉它与上面顶点的连线，上面与之相连的顶点必被选中，也就表示这个点的值必为1。三角形中有一个为1则代表这个语句为真，所有语句都为真则代表F为真。
二者等价关系得证，即F是可满足的当且仅当图中有顶点数不超过K = n + 2m 的顶点覆盖。
最后，由3SAT到图G共需要构造 2n + 3m 个顶点，n + 6m条边，很容易在多项式时间内搞定。（别忘记证明规约能在多项式时间完成）
所以，3SAT <=p VC，VC∈NPC。