求无向图中两个顶点之间所有简单路径上的所有顶点

Question

枚举任意图中两个顶点之间的所有简单路径通常需要指数时间，因为顶点之间可能存在指数数量的简单路径。但是如果我们只对两个endpoint顶点之间至少一条简单路径上的顶点感兴趣呢？

也就是说：给定一个无向图和两个不同的顶点，是否有多项式时间算法可以找到两个顶点之间至少一条简单路径上的每个顶点？这与连通性不同；不包括死胡同和死胡同。然而，分支和连接路径是允许的。

我发现编写一个看起来可以解决这个问题的算法非常容易，但在某些情况下要么失败，要么在病理情况下需要指数级的运行时间。

更一般地说：给定图中两个不相交的顶点集，是否有多项式时间算法可以找到所有位于从一组顶点到另一组顶点的简单路径上的顶点？

（如果有一个非常明显的解决方案，请原谅我。我当然觉得应该有。）

Answer 1

你介意概率解吗？也就是说，它不能保证找到所有的顶点，但它通常会先尝试，并且极有可能在尝试2到3次之后？

如果可以，请随机为每条边指定一个电阻，如果将源电压设置为1，将汇电压设置为0，则求解每个节点的电压。连接它的两个节点处于不同电压的任何边都明显位于一条简单的路径上（路径很容易构建，只需从一端通过电压上升，从另一端通过电压下降）。连接它的两个节点处于相同电压的边缘极不可能位于简单路径上，尽管理论上可能发生这种情况。

重复几组随机分配的电阻，你很可能已经找到了简单路径上的所有边。（你还没有证明这个答案，但出错的几率非常小。）

当然，一旦知道了简单路径上的所有边，就可以轻松获得简单路径上的所有顶点。

使现代化

我相信以下是正确的，但没有证据。假设我们取一组电阻并计算出电压。对于处于简单路径中的每条边，都有另一条边（可能相同），因此仅改变该边的电阻将导致第一条边上的电压发生变化。如果是这样，就有可能在多项式时间内识别简单路径中的每条边。

直觉上，这对我来说很有意义，但我不知道如何证明这一点。

Answer 2

这是一个线性时间确定性解决方案。在你的两个endpoint之间插入一条边（让我们称它们为a和b），如果这样的边不存在，那么你的问题就变成了寻找一个最大的顶点集v的问题，该顶点集位于通过a和b的任何简单循环上。你可以说服自己，这样的集合对应于包含a和b的最大子图，这些子图不能通过删除其任何节点（也称为双连接组件）来断开连接。本页描述了Hopcroft和Tarjan的概念和经典的线性时间（基于DFS）算法来识别所有双连接组件（你只需要包含a和b的组件）。

你的第二个问题关于两个集合之间的简单路径（让我们称它们为A和B）可以通过创建一个新的顶点a和一个顶点b来简化到第一个问题，然后解决你的第一个问题a和b。