algorithm - 查找无向图中两个顶点之间所有简单路径上的所有*顶点*

Question

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

即:给定一个无向图和两个不同的顶点，是否有一个多项式时间算法可以找到至少在两个顶点之间的一条简单路径上的每个顶点？这不是与连通性相同；死胡同和死胡同被排除在外。但是，分支和连接路径是允许的。

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

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

(如果有一个非常明显的解决方案，请原谅我。感觉确实应该有。)

Answer 1

这是一个线性时间确定性解决方案。在您的两个端点之间插入一条边(我们称它们为 a 和 b)，如果这样的边尚不存在，则会将您的问题转化为找到位于通过 a 和 b 的任何简单循环上的最大顶点集 v 的问题。您可以说服自己这样的集合对应于包含 a 和 b 的最大子图，并且不能通过移除其任何节点(也称为双连通分量)来断开连接。 This page描述了 Hopcroft 和 Tarjan 的概念和经典线性时间(基于 DFS)算法来识别所有双连通组件(您只需要包含 a 和 b 的组件)。

关于两个集合(让我们称它们为 A 和 B)之间的简单路径的第二个问题可以简化为第一个问题，方法是创建一个新的顶点 a，边到 A 中的所有顶点，以及一个顶点 b，边到所有顶点的边B，然后解决你的第一个问题 a 和 b。