查找出现在至少一条 s-t 路径上的所有边
Finding all edges that appear on at least one s-t path
我正在寻找解决以下问题的算法：
- 输入：有向图G，节点s和t
- 输出：属于简单 st 路径的所有边的集合
如果没有节点被访问两次，则路径是简单的。
有人知道怎么做吗？
DAG 上的问题很简单，因为所有路径都很简单。但是，输入图不是 DAG。我相信通过使用强连通分量算法，可以将问题简化为 G 是强连通的情况。不幸的是，我不知道如何进一步进行。我什至不确定这个问题是否可以多项式求解。
我已经设法为 无向 情况找出 polynomial-time 算法。对于 directed 的情况，我没有完整的答案，但由于我将在下面概述的原因，我有一个微弱的预感问题是 NP-hard.
我使用的主要见解如下。假设你有一对节点 s 和 t，你想确定边 {u, v} 是否出现在从 s 到 v 的某条简单路径上。这相当于询问是否存在路径 Psu 和 Pvt 其中 Psu 从 s 到 u，Pvt 从v 到 t，并且 Psu 和 Pvt 没有共同的节点。
这是一个称为 2-distinct 路径问题 的问题的特例。在那个问题中，你得到了一对节点 (w, x) 和 (y, z)，并被问到是否有 node-disjoint 从 w 到 x 和从 y 到 z 的路径。这个问题从 20 世纪 70 年代就开始研究了，我们知道
- 在无向情况下存在针对该问题的 polynomial-time 算法，但是
- 问题的定向版本是 NP-hard。
这意味着，在无向的情况下，我们可以按如下方式解决你原来的问题。给定节点 s 和 t，对于每条边 {u, v}，查看从 s 到 u 和从 v 到 t 的 2-distinct 路径问题是否有解。如果是，记录有一条简单的路径通过 {u, v}。最后，报告您以这种方式找到的所有边缘。使用 Tholey's algorithm 作为 2-distinct 路径问题的黑盒求解器给出 O(mn + m2 α(m, n)) 的总运行时间，其中 α( m, n) 是反阿克曼函数。
这种方法也可以用于有向的情况，除了 2-distinct 路径问题对于有向图是 NP-hard，即使其中一个终端节点具有到另一个起点的直接边节点。这本身并不能证明您的原始问题是 NP-hard，因为解决您的问题似乎并不能立即提供一种方法来确定任何 s-t 路径上的边。然而，确定一条边是否在某些 s-t 路径上如此困难这一事实是一个弱启发式证据，表明这是一个难题。
我正在寻找解决以下问题的算法：
- 输入：有向图G，节点s和t
- 输出：属于简单 st 路径的所有边的集合
如果没有节点被访问两次，则路径是简单的。
有人知道怎么做吗？
DAG 上的问题很简单，因为所有路径都很简单。但是，输入图不是 DAG。我相信通过使用强连通分量算法，可以将问题简化为 G 是强连通的情况。不幸的是，我不知道如何进一步进行。我什至不确定这个问题是否可以多项式求解。
我已经设法为 无向 情况找出 polynomial-time 算法。对于 directed 的情况，我没有完整的答案，但由于我将在下面概述的原因，我有一个微弱的预感问题是 NP-hard.
我使用的主要见解如下。假设你有一对节点 s 和 t，你想确定边 {u, v} 是否出现在从 s 到 v 的某条简单路径上。这相当于询问是否存在路径 Psu 和 Pvt 其中 Psu 从 s 到 u，Pvt 从v 到 t，并且 Psu 和 Pvt 没有共同的节点。
这是一个称为 2-distinct 路径问题 的问题的特例。在那个问题中，你得到了一对节点 (w, x) 和 (y, z)，并被问到是否有 node-disjoint 从 w 到 x 和从 y 到 z 的路径。这个问题从 20 世纪 70 年代就开始研究了，我们知道
- 在无向情况下存在针对该问题的 polynomial-time 算法，但是
- 问题的定向版本是 NP-hard。
这意味着，在无向的情况下，我们可以按如下方式解决你原来的问题。给定节点 s 和 t，对于每条边 {u, v}，查看从 s 到 u 和从 v 到 t 的 2-distinct 路径问题是否有解。如果是，记录有一条简单的路径通过 {u, v}。最后，报告您以这种方式找到的所有边缘。使用 Tholey's algorithm 作为 2-distinct 路径问题的黑盒求解器给出 O(mn + m2 α(m, n)) 的总运行时间，其中 α( m, n) 是反阿克曼函数。
这种方法也可以用于有向的情况，除了 2-distinct 路径问题对于有向图是 NP-hard，即使其中一个终端节点具有到另一个起点的直接边节点。这本身并不能证明您的原始问题是 NP-hard，因为解决您的问题似乎并不能立即提供一种方法来确定任何 s-t 路径上的边。然而，确定一条边是否在某些 s-t 路径上如此困难这一事实是一个弱启发式证据，表明这是一个难题。