要证明一个问题是NPC，通常是归约到一个相似且已知是NPC的问题上。卡普的二十一个NP-完全问题罗列了21个NPC问题，推进了NP，NPC问题以及P是否等于NP的研究。
往期文章：
例子
Feedback Vertex Set
问题：给定图$G$，正整数$k$，我们是否可以从图$G$移除不超过$k$个点，使得$G$中不存在回路。
证明：可以从顶点覆盖问题归约。对于某一个图$G$，对于每一条边，我们可以将该条边替换成一个三角形，那么图$G$就转化成了一个包含了很多回路的图$G’$。那么找到一个覆盖$G’$所有回路的点集，就可以找到原图的一个顶点覆盖。
解释：该问题需要注意的是，当把图$G$转化成图$G’$，其实就是给每条边$e$外面增加一个点$v_e$，并将$v_e$和$e$的首尾端点连接在一起形成一个三角形。那么我们在选择覆盖所有回路的顶点时，我们不会选择$v_e$，因为我们总可以选择$e$的端点来覆盖更多的回路。One-Sided Dominating Set
问题：给定一个二分图$G=(X,Y;E)$与正整数k，是否存在$X$的子集$X’$支配所有$Y$集合内的点，$|X’|\leq k$。（支配的意思是对于$Y$中任意的点，都在$X’$中有相邻的点）
证明：可以从顶点覆盖问题归约。给定一个$G=(V,E)$，可以转化成二分图$G=(X,Y;E’)$，其中我们令$X=V$，$Y=E$，并且如果$x$是图$G$中的某个边$y$的端点，那么$(x,y)\in E’$。Multicut
问题：给定图$G$，正整数$k$以及一个集合点对$C$，是否存在$k$条边$E’$，使得移除$E’$，使得C中的任何一个点对都不连通。
证明：可以从顶点覆盖问题归约。对于顶点覆盖$(G,k)$问题，可以转化成$(T,C,k)$问题，其中$T$是一个star的图，我们另$T$的中心点$x$，对于$G$中的每个点$v$，我们将其放置在$T$的叶节点上，对于每一条边$(u,v)\in E$，我们将其添加到$C$中，那么顶点覆盖可以转化成$Multicut$得到解。