判断指定完全无向带权图路径问题是否存在多项式时间算法

该问题不存在多项式时间算法（除非 P=NP），我们可以通过从经典NP难问题最长简单路径问题归约来完成证明。 #

归约过程 #

最长简单路径问题的定义为：输入任意无向图 $G'$，求解 $G'$ 中包含顶点数最多的简单路径，该问题已被证明为NP难，不存在多项式时间解法。我们可以在多项式时间内将该问题转化为你描述的问题的输入，以此证明你的问题同样不存在多项式时间解法：

1. 设待求解的最长简单路径问题输入图 $G'$ 的顶点总数为 $n$，我们构造边权非负的完全无向图 $G$，$G$ 与 $G'$ 的顶点集完全一致
2. $G$ 的边权设置规则：若该边在原图 $G'$ 中存在，则边权设为 $0$；若该边是 $G'$ 中不存在的额外边，则边权设为 $1$
3. 设定权值阈值 $W=1$，作为你提出的问题的第二个输入参数

等价性验证 #

你提出的问题要求解总权值小于W的简单路径中顶点数最多的解：

• 因为所有边权都是非负整数，总权值小于1等价于路径总权值为0，也就是说路径中所有边的权值都是0，对应恰好是原图 $G'$ 中存在的边
• 此时求得的顶点数最多的简单路径，正好就是原图 $G'$ 的最长简单路径

如果存在多项式时间算法可以求解你提出的问题，我们就可以通过上述多项式时间的转换步骤，多项式时间求解NP难的最长简单路径问题，和已有结论矛盾。 #

内容的提问来源于stack exchange，提问作者Irazza