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

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 是公共顶点。

完整的问题是：

在此处输入图像描述

score 8 · Accepted Answer

问题（在问题中提出，找到与发布问题的图片不同的“ ONE ”顶点不相交路径）不是并且可以在多项式时间内解决。而且，问题也不是。st NP-hardO(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顶点不相交路径的算法---

将此问题转换为最大流问题并在http://en.wikipedia.org/wiki/Dinitz_blocking_flow_algorithmDinic's中使用算法来解决它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 的权重并运行最大流算法（介于S和之间T）。如果您的最大流量为 1，则该流量（或路径）对应于原始图中的顶点不相交路径。

现在对k不相交的路径进行排序：

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

score 2 · Accepted Answer

问题是NP-Hard。这可以通过减少 3-SAT 来证明。这是一个证明的草图。

分配“n”个源/目标对（对于每个变量）。用两条路径连接每一对，每条路径都有“m”个内部节点（对于“m”子句）。一种路径是针对变量为“真”的情况，另一种是“假”。

还分配“m”源/目标对（对于每个子句）。将每对与 3 条路径连接起来，每条路径 - 通过“变量”路径的相应内部节点，如果该变量在子句中是否被否定，则选择“真”或“假”路径。

然后找到 'm+n' 个顶点不相交的路径来解决 3-SAT。

2 回答 2