algorithm - 查找从源到目标的顶点不相交路径

Question

是否有确定性算法来检查图是否包含从源到目的地的顶点不相交路径，复杂度 O(nm^2)(n 是顶点数，m 是数边缘)还是 NP-Hard(如果是，为什么)？顶点不相交路径是指没有公共(public)内部顶点的路径。例如。

s -> a -> b -> c -> d  
s -> x -> y -> z -> d

顶点不相交但是

s -> a -> b -> c -> d
s -> x -> a -> z -> d
          ^

不是，因为 a 是公共(public)顶点。

---

完整的问题是:

Answer 1

问题(问题中提出的，在s和t之间找到“ONE”顶点不相交路径，这与图片的不同发布的问题)不是NP-hard，可以在多项式时间内解决O(V^2E)。此外，is there there there there k disjoint paths between s and t 的问题也是不NP-Complete。

上面提到的用于证明NP-completeness (http://www.shannarasite.org/kb/kbse48.html) 的文章有一个细微的区别....你不知道s 和t，这样问题就变难了。但是，一旦你修复了 s 和 t，它就是多项式的。

这是在多项式时间内找到a顶点不相交路径的算法---

将此问题转化为最大流问题并使用Dinic's算法在O(V^2E)中求解 http://en.wikipedia.org/wiki/Dinitz_blocking_flow_algorithm

这是转换:

选择源 s 和目标 t 顶点，您希望在它们之间找到不相交的路径。 对于每个顶点 v 添加两个新顶点到 G' (我们正在构建的图)，即对于每个 v\in G 添加 v_1 和 v_2 到 G'。

对于每条边 (a,b) 添加以下边 (a_1, a_2), (b_1, b_2), (a_2, b_1) 和 (b_2, a_1)(记住顶点已经变换，并注意边的方向)。

将S和T添加到G'和边(S,s_1), and (t_2, T)。

为所有边分配权重 1 并运行最大流算法(在 S 和 T 之间)。如果最大流量为 1，则该流量(或路径)对应于原始图中的顶点不相交路径。

现在输入 k 个不相交的路径:

为边 (S,s_1), (t_2, T) , (s1_, s_2) 分配权重 k , 和 (t_1, t_2).....和权重 1 剩余的边缘...再次运行 Dinic 的算法，如果有容量 k 的最大流量，为您提供不相交的路径。