顶点覆盖问题

如果无向图 $G$ 的一组顶点能覆盖所有 $G$ 的边，则称它是一个顶点覆盖。

定义顶点覆盖问题为：

$$V E R T E X-C O V E R=\{\langle G, k\rangle \mid G \text{ is an undirected graph that has a k-node vertex cover}\}$$

它是 NP 完全复杂度类的。