证明具有负边权重的最长路径是NP-Hard的

Question

我知道以前也有人问过类似的问题，网上有大量的资源，但我有一个略有不同的问题。我理解从HAM路径到最长路径的缩减。它依赖于两者都需要使用n-1个边。但是，如果在最长路径中给定的图的边权重为负值，会发生什么呢？那么最长的路径可以有n-2条边，但HAM仍然有n-1条边。

对于这个问题，有没有不同的简化方法？我是不是遗漏了什么？

Answer 1

这是一个类比。我想让你相信超人有不可思议的超人能力。为了做到这一点，我告诉你，他比飞驰的子弹还快。“比飞驰的子弹还快吗？”你说。“这真的很快！没有人能做到这一点--这真的很难！“

现在我告诉你更多--他不仅可以跑得比飞驰的子弹还快，他还可以一跳就跳过高楼。“哇！”你可能会说，“这也太难了！”但话又说回来，我已经知道超人可以做非常困难的事情，因为你告诉我他跑得比一颗飞驰的子弹还快。“从这个意义上说，通过说超人可以做一件困难的事情，我已经让你相信他是相当强大的。告诉你他还可以做其他困难的事情并不能改变这一点。

现在让我们来讨论一下最长路径。最长路径问题是NP-hard的原因是给定任何一个图，你都可以给那个图中的每条边分配一个长度为1的长度，然后检查这个新图是否有一个长度为n-1的简单路径。这是一件非常困难的事情，因为我们知道，检查一个图是否有哈密顿路径真的很难。(这就是“超人能跑得比飞驰的子弹还快”这句话。)

现在假设我们说“嘿，我不仅可以用正权重解决这个问题，而且如果允许权重也是负的，我也可以解决这个问题！”从您的角度来看，我并没有让寻找最长路径的问题变得更容易。我们仍然可以像以前一样使用相同的约化来寻找哈密顿路径。这也是我们可以做其他事情的情况。(这是“可以在一次跳跃中跳过高楼”的一点。)

通常，如果您从NP-hard问题开始，然后将其推广，则通常会留下一个NP-hard问题，因为该问题仍然具有以前的所有困难部分，以及它还需要处理的一堆新情况。