在图中找到一对边不相交的路径，使得每条路径的长度小于给定的常数

Question

我知道如何找到一对长度总和最小的不相交路径（Surballe 算法）。 我还有一个 ILP 公式可以解决以下问题，它概括了我的问题： 给定图 G 中的两个顶点 u 和 v，在 G 中连接 u 和 v 的所有不相交路径对中，找到其中较长路径的最小长度的一对。 （当然，这个问题可以针对多于两条不相交路径的组重新表述）。

有谁知道解决任何这些问题的有效（多项式？）算法（标题中的问题或广义问题？）

谢谢！

Answer 1

我认为这是一个 NP 问题，因为我可以将背包问题简化为这个问题，并且根据 这篇文章 knapsack问题是 NP 完全的。确实，背包问题在背包大小的值中有一个伪多项式时间算法，但是它在输入大小方面没有多项式时间算法。

将背包问题简化为您指定的问题：

- 我的背包问题的说明：

1- 假设您有两个背包，尺寸均为 c。

2- 您有 n 个项目，卷为 v1、v2、.. vn。

3-你想把这n件物品全部放进你的背包里。

- 将背包问题简化为您的问题：

1- 制作一个具有 (n + 1) 个顶点的图。

2- 顶点 i 使用两条边连接到顶点 (i + 1)。成本为 vi（体积
第 i 个项目）和一个成本为零的项目。

3-您想要找到从顶点 1 到顶点 (n + 1) 的两条边不相交路径，其上限等于背包大小。

所以如果你能用多项式解决你的问题，那么背包问题就可以用多项式解决，并且你已经证明了 P=NP。 :D

当然，根据上面的描述，您可以在图的边权重中以多项式时间解决您的问题，但它是一种伪多项式时间算法，而不是像 Surballe 算法那样真正的算法。
抱歉英语不好。