寻找不含负圈的强连通子图

Question

是否有解决以下决策问题的算法：

给定一个由其转移矩阵定义的强连通加权有向图G，是否存在G的一个没有负圈的强连通生成子图？

G的强连通生成子图是G的一个强连通子图，它与G具有相同的顶点。您可以在此paper中查找强连通生成子图的定义。本文给出了最小强连通子图问题的一个近似解。

解决这个问题的一种天真的方法是使用福特-贝尔曼或弗洛伊德-沃肖尔算法找到图的负圈，从这个圈中删除一条边，并在图仍然是强连通的情况下重复。但这种幼稚的方法时间复杂度很低，因为我们可能会运行福特-贝尔曼算法，并多次检查强连通性--此外，我无法证明该算法是否在所有情况下都是正确的。

我希望在这里能找到专家，他们能告诉我这个决策问题是否可以在多项式时间内解决，以及什么算法可以做到。在此之前，非常感谢您。

Answer 1

这里有一个朴素的解决方案，它有一个合理的机会找到一个在多项式时间内没有负圈的强连接生成子图。但肯定不能保证能找到一个。

将所有权重转换为负值。现在使用福特-贝尔曼或弗洛伊德-沃肖尔找到一个负循环。这实际上是原始图形中的一个正循环。

现在，我们拾取循环中的一个顶点，并将其他顶点收缩到该顶点。连接到/来自已移除顶点的边被替换为表示沿该边行进的边，并绕过我们保留的那个循环。如果两个顶点之间有多条边，则只保留最好的那条边。

在新的、较小的图形上重复该练习。

该算法在保证的多项式时间内运行(每次迭代都在多项式时间内运行，并删除至少一个顶点)。如果它设法将你的图减少到一个点，那么你只需要向后走这个过程，就会发现你实际上已经找到了一个没有负环的强连接生成图。

然而，如果它不能做到这一点，就不能保证没有一个。你只是没有找到它。

(我怀疑一个有保证的算法将是NP完全的。)

Answer 2

这个问题通常是NP难的，这可以通过减少哈密顿循环来证明。