形式陈述

顶点覆盖判定问题输入有限无向图 $G=(V,E)$$G=(V,E)$ 与整数 $k$$k$，询问是否存在 $C\subseteq V$$C\subseteq V$、$|C|\le k$$|C|\le k$，使每条边至少有一个端点属于 $C$$C$。它属于 NP，因为 $C$$C$ 可在线性时间验证。由 3-SAT 归约：每个变量建立连接 $x_i,\neg x_i$$x_i,\mathrm{\neg }{x}_i$ 的边；每个三文字子句建立一个三角形，并把三个子句顶点分别连到同名变量文字顶点；令 $k=n+2m$$k=n+2m$。公式可满足当且仅当所得图有大小至多 $k$$k$ 的顶点覆盖，因此该问题 NP 完全。

直觉

大小预算迫使每个变量边恰选一个端点、每个子句三角形恰选两个顶点；子句中唯一可不选的顶点必须由一个被选中的同名真文字端点覆盖。

例子与边界

从满足赋值构造覆盖时，在每个变量边选择为真的文字顶点，并在每个子句三角形选择对应两个假文字的顶点；至少一个真文字可留在三角形外。反向读取时，预算紧性保证结构不能额外浪费顶点。优化版“求最小顶点覆盖”是 NP-hard；但二分图最小顶点覆盖可由最大匹配多项式求解，不能把一般图结论无条件推广。

推论与应用

顶点覆盖是 Karp 的经典完全问题，也是近似算法和参数化算法的基准：一般图有简单 2-近似，参数 $k$$k$ 下可通过分支或核化获得 FPT 算法。它还与独立集满足 $C$$C$ 为覆盖当且仅当 $V\setminus C$$V\setminus C$ 为独立集。

参考资料

• Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009，Ch. 2, NP-completeness reductions including Vertex Cover。
• Richard M. Karp, “Reducibility Among Combinatorial Problems,” in Complexity of Computer Computations, 1972, pp. 85–103，Full chapter, NODE COVER among the complete combinatorial problems。