NPC 证明（二）

往期文章：

1. NPC简介

2. NP-hard问题证明

3. NPC 证明（一）

本文在前文的基础上进一步罗列了几个NPC问题的归约。大部分例子来自CSCI5320的课程材料或者作业题。

例子

1. Odd cycle transversal(OCT)问题^[2]

   原问题：给定一个图，是否能移除不超过$k$个点，使得原图成为一个二分图。
   转化：Yannakakis^[1]证明了一个图是二分图当且仅当图中没有奇回路(奇回路指的是拥有奇数个点的回路)，并且在文中证明了该问题是FPT(Fixed-parameter Tractable)的。
   本质问题：给定一个图，是否能移除不超过$k$个点，使得原图没有奇回路。
   NPC证明：我们从支配集问题进行归约。假设OCT问题是多项式可解，那么给定一个图$G$，我们要找到一个支配集合，可以对于每一条边$e=(u,v)$，我们增加一个点$v_e$，同时增加两条边$(v_e,u)$和$(v,v_e)$，从而得到一个新的图$G’$。那么上述三个点$(u,v_e,v)$构成一个奇回路，从而图$G’$中包含了一组奇回路。进而，如果能在$G’$找到一组点覆盖所有奇回路，那么对于$(u,v_e,v)$最少有一个点是在解当中，当$v_e$在解当中时，我们总能用$u$或者$v$来替换。那么就可以得到$G$的一个支配集。那么支配集问题就变成了多项式可解。所以OCT是NPC问题。
   另外一个证明可以参考文章Node-and edge-deletion NP-complete problems^[1]。

2. $clique$衍生问题

   问题：给定图$G$，给定正整数$k$和$l$，是否存在$k$个点，使得任意的两点之间的距离不超过$l$。
   NP-hard证明：令$l=1$，那么原问题转化成$G$中是否存在$k$个点，使得任意两点之间的距离不超过$l=1$，此时原问题转化成$clique$问题，该问题是NPC，所以原问题是NP-hard。

3. 哈密尔顿回路衍生问题(1)

   问题：给定一个点集$S$和一个图$G$，是否存在最短的walk，经过所有$S$当中的点。
   NP-hard证明：当点集$S$等于图$G$的点集$V$时，如果能在多项式时间内找到最短的walk，那么则可以在多项式时间内找到哈密尔顿路径。
   解释：当最短的walk经过所有顶点有且仅有一次时，则该路径为哈密尔顿回路。否则可以判断原图不存在哈密尔顿回路。那么哈密尔顿回路变成多项式时间可解的问题。

4. 哈密尔顿回路衍生问题(2)

   问题：对于赋权图$G$，给定$s$和$t$两个点，寻找两点之间的最短路径。
   NP-hard证明：先转化成最长路径问题，再转化成哈密尔顿回路问题。
   解释：给定图$G$，首先对所有的边权值取相反数得到图$G’$。假设原问题存在多项式时间的算法，那么可以在图$G’$中可以找到等价的最长路径。但是最长路径问题是NPC，所以原问题是NPC。（最长路径是NPC的证明可以归约到哈密尔顿回路问题上。）