顶点覆盖 NP 完全性

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

从 3-SAT 的经典构造中，每个变量建一条连接 $x_i$ 与 $\mathrm{\neg }{x}_i$ 的边，预算迫使二者选一；每个三文字子句建三角形，预算允许其中选两个，剩下未选顶点必须通过对应文字的已选变量顶点覆盖外连边。总预算为 $n+2m$。从满足赋值构造覆盖时，在每个变量边选择为真的文字顶点，并在每个子句中选一个为真的文字出现，把它对应的三角形顶点留在覆盖外，另两个顶点都选入；这两个被选顶点的文字可以真也可以假。满足子句可能有两到三个真文字，不能假设它恰有两个假文字。反向读取时，每条变量边至少需要一个顶点、每个互不相交的子句三角形至少需要两个；总预算 $n+2m$ 因而迫使这些下界全部取等号。把每条变量边上选中的文字设为真，每个三角形未选顶点的外连边又迫使同名变量顶点被选，故每个子句都得到一个真文字。构造有 $2n+3m$ 个顶点及 $n+6m$ 条边，编号和阈值均可在多项式时间写出；重复文字仍对应不同的子句顶点，不破坏这份计数。

优化版“求最小顶点覆盖”是 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 困难边界。