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

Question

是否存在确定性算法来检查图形是否包含从源到目的地的顶点不相交路径,具有复杂性O(nm^2)(n是顶点数,m是边数)或者是NP-Hard(如果是,为什么)？顶点不相交路径表示没有共同内部顶点的路径.例如.

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

顶点不相交但是

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

不是因为a是常见的顶点.

---

完整的问题是:

Answer 1

问题(在问题中询问,找到" ONE"顶点不相交路径s和t哪个不同于所发布问题的图片)不是 NP-hard并且可以在多项式时间内求解O(V^2E).此外,问题is there are 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算法在http://en.wikipedia.org/wiki/Dinitz_blocking_flow_algorithm中解决它O(V^2E)

这是转换:

选择要在其中找到不相交路径的源顶点s和目标t顶点.对于每个顶点v增加两个新的顶点G'(上图我们正在建设),即每个v \in G添加 v_1 and 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),和(t_2, T).

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

现在是一种k不相干的道路:

分配权重k的边缘(S,s_1),(t_2, T),(s1_, s_2),和(t_1, t_2).....和重量1为剩余的边缘......再次运行迪尼奇的算法中,如果有能力的最大流量k,这给你不相交路径.