顶点覆盖 NP 完全性

顶点覆盖的局部条件是每条边至少选一个端点，但“用至多 $k$ 个顶点同时覆盖所有边”会让选择在全图耦合。NP 成员性很直接：给出顶点集即可逐边检查。困难性构造中的大小预算迫使每个变量边恰选一个端点、每个子句三角形恰选两个顶点；子句中唯一可不选的顶点必须由一个被选中的同名真文字端点覆盖，从而让变量部件的二选一与子句部件的真文字要求一致。也可通过独立集与 clique 的互补关系从其他完全问题转移。

从 3-SAT 的经典构造中，每个变量建一条连接 $x_i$ 与 $\mathrm{\neg }{x}_i$ 的边，预算迫使二者选一；每个三文字子句建三角形，预算允许其中选两个，剩下未选顶点必须通过对应文字的已选变量顶点覆盖外连边。总预算为 $n+2m$。从满足赋值构造覆盖时，在每个变量边选择为真的文字顶点，并在每个子句三角形选择对应两个假文字的顶点；至少一个真文字可留在三角形外。反向读取时，预算紧性保证结构不能额外浪费顶点。

优化版“求最小顶点覆盖”是 NP-hard；但二分图最小顶点覆盖可由最大匹配多项式求解，不能把一般图结论无条件推广。

仅给出一个很难求最小覆盖的例子不能证明完全性；必须证明构造双向正确且规模多项式。无权顶点覆盖有简单 $2$-近似，这与精确判定 NP 完全并不矛盾。

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

该证明连接 3-SAT公理库3-SAT3-SAT · Three-satisfiability每个子句恰含三个文字的合取范式可满足性问题。、顶点覆盖公理库顶点覆盖Vertex cover与图中每条边至少一个端点相交、从而覆盖全部边的顶点子集。与 NP 完全性公理库NP 完全性NP-completeness同时属于 NP 且为 NP-hard 的性质。。覆盖与最大独立集公理库团与独立集Clique · Independent set · 团 · 独立集顶点集内部的边关系分别达到两两全有与两两全无时形成的两类结构。的补集关系把两个优化问题互相转换；二分图上又可借匹配得到多项式算法，说明图类限制可以跨越一般 NP 困难边界。