hol*_*ola 5 algorithm complexity-theory graph-theory computation-theory operations-research
是否有一种算法可以解决以下决策问题：
给定一个G由其转移矩阵定义的强连通加权有向图，是否存在一个G没有负循环的强连通生成子图？
的强连通生成子图G是与G共享相同顶点的强连通子图G。您可以查看本文以了解强连接生成子图的定义。在本文中，他们提出了最小强连通子图问题的近似。
解决这个问题的一个简单方法是使用 Ford-Bellman 或 Floyd-Warshall 算法找到图的负循环，从这个循环中删除一条边，并在图仍然强连通时重复。但是这种简单的方法时间复杂度很低，因为我们可能会运行福特贝尔曼算法并多次检查强连通性——而且我无法证明这个算法是否在所有情况下都是正确的。
我希望在这里找到专家，他们可以告诉我这个决策问题是否可以在多项式时间内解决，以及什么算法可以解决这个问题。提前谢谢了。
这是一个简单的解决方案，它有合理的机会找到在多项式时间内没有负循环的强连接跨越子图。但显然不能保证一定能找到。
将所有权重转为负数。现在使用 Ford-Bellman 或 Floyd-Warshall 来查找负循环。这实际上是原图中的一个正循环。
现在我们在循环中选择一个顶点，并将其他顶点收缩到它。连接到/从删除的顶点连接的边将被代表沿着该边并围绕循环移动到我们保留的顶点的边所替换。如果两个顶点之间有多个边，则只保留最好的一条。
在新的、较小的图表上重复该练习。
该算法在保证的多项式时间内运行（每次迭代在多项式时间内运行并删除至少一个顶点）。如果它设法将你的图缩小到一个点，那么你只需向后走这个过程，就会发现你实际上已经找到了一个没有负循环的强连通生成图。
然而，如果它不这样做，就不能保证不存在这样的情况。只是你没找到而已。
（我怀疑有保证的算法将是 NP 完全的。）