在图中证明2个独立路径的NP完全性

Question

所以这是一个问题：

给定有向和加权图G及其顶点a和b中的两个，我们希望找到从a到b的两个与顶点无关的路径，其权重之和小于给定数n。

我需要证明这个是NP完全的。我已经考虑了一段时间，但没有真正设法解决它。

Answer 1

首先要了解NP中的问题意味着什么可能会有所帮助。基本上，问题在于NP，这是给定证书时的整个决策问题，可以在多项式时间内完全验证是答案。将这个问题分解成不同的部分可能会证明这个示例问题是NP完全的。

1. 将问题重新定义为决策陈述：基本上将问题转化为是/否问题。示例：给定N个人和S个集合中有一个数字k，表示每个集合S中需要的最小人数，以便每个集合都完整。
2. 提供证书：对给定的决策问题进行一般性的“有根据的猜测”。示例：一组大小为k
3. 在多项式时间内对证书进行验证：想一想可以在多项式时间（O（n ^ 2），O（n）等）中验证问题答案的方法。示例：遍历每个集合S并在符合“某些条件”的情况下添加到数组中，如果它确实添加到集合，则继续添加所有N.完成后查找创建的集合大小。此验证需要多项式时间。

对于您提到的问题，尝试将问题分解为这些步骤，并且可能使用流行算法进行验证以尝试找到可能的答案。此外，在步骤3中添加某种类型的存在验证检查也很重要。检查G实际上是否是具有顶点V和边缘E的图形将有利于此证明。