NP硬度通过限制

Question

假设我在图表上有一个决策问题$ p $，我知道它是最高度$ D $的图表上的NP-HARD。这是否意味着它在$ d $ regarbular图表上是NP-HARD？尽管这似乎显然是正确的，但也许还可以证明$ p $很难，有些顶点的学位小于$ d $，也许是固有的。

Answer 1

不，总的来说不是真的。

NP-HARD的一个总体问题并不意味着专业是NP-HARD。相反，这是事实。

例如，最大切割是通用图的NP-固定，但是对于平面图类别，它在P中。

在您的情况下，$ d $的图表是最大学位$ d $的图形的特殊情况，因此最大学位$ d $的np-hardness并不是自动证明$ d $常规图的NP硬度。

实际上，以具体的例子，请看一下这个理论问题： 对于立方体图，是否有一个容易的问题，但对于最高度3的图形很难？ 以下 回答（戴维·埃普斯坦（David Eppstein））在肯定（为方便起见）中：

这是一个相当自然的：在输入$（g，k）$上，确定$ g $是否具有至少$ k $边缘的连接常规子图。对于3型图，这是微不足道的，但是如果最大程度为3，并且输入是连接的，而不是树，而不是规则的，那么最大的该子图是最长的循环，因此问题是NP完整的。