诱导子图;两个节点之间的路径存在

Question

对不起，我的文本墙尽可能简洁！

我从G内部得到了一个非常大的有向图G和顶点子集S，我想要做的是找到由S引发的G的子图，并附加考虑如果某些路径存在于G中的顶点p和顶点q之间，在感应子图中这两个顶点之间存在边。这是关键;它比一般的诱发子图问题更复杂一些（我认为）。

我能想到的解决问题的最基本的方法如下（我知道它可能不是最有效的，让我知道，如果你有没有其他建议太复杂来实现）：对于S中的每一对顶点都测试G中它们之间存在的路径。如果存在这样一条路径，则在p和q之间插入一条边在感应子图中。对我而言，n^2的时间不是那不好。

所以，我想我有两个问题： 1）什么是确定两个顶点之间是否存在路径的最快方法？我不需要知道路径，只是它是否存在。此外，如果我可以对整个图进行一些预处理以加快计算速度，那么可能会是什么情况，因为我必须在每对顶点之间执行此计算？

2）有没有比我建议找到我描述的诱导子图的类型更快的方法？

非常感谢您的帮助！

Answer 1

发现两个顶点之间是否存在路径的问题称为传递闭包问题，在一般情况下它与矩阵乘法一样困难。我首先在你的图上运行强连通组件算法，将周期压缩成单个节点并形成有向图。如果你幸运的话，你会有一些大的周期，这会使后续的传递性问题变得容易。然后我会运行Floyd Warshall，在该图上配对最短路径算法来计算传递闭包，因为它的代码非常简单。也许基于o（n^3）矩阵乘法的算法之一会更快，但我怀疑它会更快，因为常数是如此之低Floyd Warhsall。

以下是strongly connected components的快速算法。

这包含matrix multiplication and transitive closure.

等价我不知道的证明，如果有什么好的办法来解决计算传递闭包为您解决原来的问题。我怀疑不是，但另一方面，有时候聪明的人会想出很棒的东西。