如何证明最长的路径问题的NP硬度？

Question

我有一个问题：

Input: 
G(V, E) = an undirected graph, V={v1, v2, ..., vn} (V = set of nodes, E = set of edges)
where there is a path connecting from v1 to vn.

Question: 
What is the maximum number of nodes you can visit when starting from v1 and ending at vn. 
(including v1 and vn) 
Each node can only be visited at most once.

我想通过将其从已知的NP完整问题（例如无向的汉密尔顿路径或子集）中减少来证明这是NP-HARD。

但是，我不知道该怎么做，这就是我需要帮助的地方。

有人可以帮忙吗？

Answer 1

假设我理解您的定义，您的问题与最长路径的优化版本有关：

最长的路径
输入: ：图$ g =（v，e）$，整数$ k $。
问题: ：有没有$ g $至少有$ k $顶点的路径

这个问题是np complete，汉密尔顿路径有很明显的减少 - 只是设置$ k = n $，显然，如果我们得到了一组（有序的）顶点，我们可以轻松地检查至少是一条途径$ K $顶点。

请注意，我们可以假设$ g $已连接，从现在开始我们将这样做。

优化版本 最大限度- 最长的路径我们要求最大长度的路径为NP - hard（这两个问题的多项式时间等效性是一个简单的练习）。

那么 最大限度- 最长的路径和问题是，您有两个指定的顶点，这些顶点是路径的开始和结束。现在，我们需要从某些NP硬性问题减少到您的问题，但是我们已经有一个非常接近的问题了。

给定实例$ g $的 最大限度- 最长的路径您现在应该能够构建问题的实例$ g'$，以便如果$ p $是$ g $中最长的路径，那么这几乎是$ g'$中最长的路径。

如果您仍在大约2个小时的时间里，您仍将头靠在墙上，这是一个提示：

尝试服用$ g $，并添加两个新的顶点$ s $和$ t $，然后将它们连接起来，以便它们可以开始和结束这样的路径$ p $ - 请记住，尽管您不知道$ p $是什么。