algorithm - 查找出现在至少一条 s-t 路径上的所有边

Question

我正在寻找一种算法来解决以下问题:

• 输入:有向图G，节点s和t
• 输出:属于简单 st 路径的所有边的集合

如果没有节点被访问两次，则路径是简单的。

有人知道如何做到这一点吗？

DAG 上的问题很简单，因为所有路径都很简单。但是，输入图不是 DAG。我相信通过使用强连通分量算法，可以将问题简化为 G 是强连通的情况。不幸的是，我不知道如何进一步进行。我什至不确定这个问题是否可以多项式求解。

Answer 1

我已经设法为无向 情况找出多项式时间算法。对于定向案例，我没有完整的答案，但由于我将在下面概述的原因，我有一种微弱的预感，即问题是 NP-hard。

我使用的主要见解如下。假设你有一对节点 s 和 t，你想确定边 {u, v} 是否出现在从 s 到 v 的一些简单路径上。这相当于询问是否存在路径 P_su 和 P_vt，其中 P_su 从 s 到 u，P_vt 从 v 到 t，P_su 和 P_vt 没有共同的节点。

这是称为2-distinct path problem 问题的特例。在该问题中，您将获得一对节点 (w, x) 和 (y, z)，并被询问是否存在从 w 到 x 和从 y 到 z 的节点不相交路径。这个问题从 1970 年代就开始研究了，我们知道

• 在无向情况下存在针对该问题的多项式时间算法，但是
• 问题的定向版本是 NP-hard。

这意味着，在无向情况下，我们可以按如下方式解决您的原始问题。给定节点 s 和 t，对于每条边 {u, v}，查看从 s 到 u 和从 v 到 t 的 2-distinct 路径问题是否有解。如果是，记录有一条简单的路径通过 {u, v}。最后，报告您以这种方式找到的所有边缘。使用Tholey's algorithm作为 2-distinct 路径问题的黑盒求解器，总运行时间为 O(mn + m² α(m, n))，其中 α(m, n) 是反阿克曼函数.

这种方法也可以用于有向的情况，除了 2-distinct 路径问题对于有向图是 NP 难的，即使其中一个终端节点具有到另一个起始节点的直接边。这本身并不能证明你原来的问题是 NP-hard 因为解决你的问题似乎并没有立即给出一种方法来确定是否有两条从 s 到 t 的不相交路径。然而，确定一条边是否在某个 s-t 路径上如此困难这一事实是一个弱启发式证据，表明这是一个难题。