枚举任意图中两个顶点之间的所有简单路径通常需要指数时间，因为顶点之间可能存在指数数量的简单路径。但是，如果我们只对两个端点之间至少一条简单路径上的顶点感兴趣呢？
那就是：给定一个无向图和两个不同的顶点，是否有一种多项式时间算法可以找到两个顶点之间至少一条简单路径上的每个顶点？这与连接性不同；死胡同和死胡同被排除在外。但是，允许分支和连接路径。
我发现编写一个看起来可以解决这个问题的算法非常容易，但在某些情况下会失败，或者在病态情况下需要指数级的运行时间。
更一般地说：给定图中的两组不相交的顶点，是否有一种多项式时间算法可以找到位于从一组顶点到另一组顶点的简单路径上的所有顶点？
（如果有一个非常明显的解决方案，请原谅我。当然感觉应该有。）
这是一个线性时间确定性解决方案。在两个末端顶点之间插入一条边（我们称它们为 a 和 b），如果这样的边不存在，则将您的问题变成找到位于通过 a 和的任何简单循环的最大顶点集 v 的问题湾。您可以说服自己这样的集合对应于包含 a 和 b 的最大子图，不能通过删除其任何节点（也称为双连接组件）来断开连接。本页介绍了 Hopcroft 和 Tarjan 的概念和经典的线性时间（基于 DFS）算法，用于识别所有双连通分量（您只需要包含 a 和 b 的那个）。
关于两个集合之间的简单路径（我们称它们为 A 和 B）的第二个问题可以通过创建一个新顶点 a 与 A 中的所有顶点的边和一个顶点 b 与 B 中的所有顶点的边来简化为第一个问题，并且然后为 a 和 b 解决你的第一个问题。
你介意概率解决方案吗？也就是说，它不能保证找到所有的顶点，但它通常会首先尝试，并且极有可能在 2 或 3 次尝试之后？
如果您对此感到满意，请随机为每个边缘分配一个电阻，并求解每个节点的电压，如果您将源置于 1 电压，将接收器置于 0 电压。两个节点连接它的任何边缘在不同的电压下显然是在一条简单的路径上（路径很容易构建，只需从一端通过上升电压，从另一端下降）。连接它的两个节点处于相同电压的边缘极不可能位于简单路径上，尽管理论上可能会发生这种情况。
重复几组随机分配的阻力，你很可能已经找到了简单路径上的所有边。（你还没有证明这个答案，但错误的可能性非常小。）
当然，一旦您知道简单路径上的所有边，获取简单路径上的所有顶点就很简单了。
更新
我相信以下是真实的，但没有证据。假设我们采用一组电阻并计算出电压。对于简单路径中的每个边缘，都有另一个边缘（可能相同），因此仅改变该边缘的电阻将导致第一个边缘上的电压发生变化。如果是这样，则可以在多项式时间内识别简单路径中的每条边。
直觉上这对我来说是有道理的，但我不知道我将如何证明它。