查找不包含负环的强连通子图

Question

查找不包含负环的强连通子图

algorithmcomplexity-theorygraph-theorycomputation-theoryoperations-research

5

是否存在一种算法可以解决以下决策问题：

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

G的强连通生成子图是与G具有相同顶点的强连通子图。您可以参考这篇论文中关于强连通生成子图的定义。在这篇论文中，他们提出了最小强连通子图问题的近似解。

对于这个问题的一种简单方法是使用 Ford-Bellman 或 Floyd-Warshall 算法找到图的负环，删除这个环上的一条边，而后不断重复，直到该图仍然是强连通图为止。但是这个简单方法时间复杂度较高，因为我们可能会多次运行 Ford-Bellman 算法并检查其强连通性 - 而且我无法证明这个算法在所有情况下都是正确的。

我希望在这里找到专家，告诉我这个决策问题是否可以在多项式时间内解决，以及使用什么算法来解决。非常感谢。

- hola

2

你是不是想说最大子图？最小子图可能只有两个节点和两条边 ;) - Yonlif

1

@karmakaze 这个问题确实是“是否有...”，我已经编辑过了。 - hola

1

@karmakaze，您在此提出的程序回答了一个问题：“图中是否存在负环？”正如我所提到的，这是一个“容易”回答的问题，我们有很好的算法来解决，如Ford-Bellman或Tortoise-Hard算法。但主要问题是存在一个不包含任何负环的子图。 - hola

2

你没有回复@Yonlif的评论。*G:{A->B, B->A}*是一个强连通图。这样的子图在这个问题中是否可接受？ - jrook

2

通常最好将所有定义和标准添加到问题主体中。至少将这些基本定义（以及必要的链接）添加到问题主体，以便将来遇到相同问题的其他人可以跟进。 - jrook

显示剩余9条评论

2个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- btilly · Answer 1

这里有一个天真的解决方案，具有在多项式时间内找到没有负循环的强连通生成子图的合理机会。但是并不保证一定能找到。

将所有权重取负。现在使用Ford-Bellman或Floyd-Warshall算法来查找负循环。这实际上是原始图中的正循环。

现在我们选择循环中的一个顶点，并将其他顶点收缩到它上面。连接到/从移除顶点的边被替换为表示沿着该边和绕过循环到我们保留的那个顶点旅行的边。如果你最终在两个顶点之间有多条边，只保留最好的一条。

在新的、较小的图上重复这个过程。

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

然而，如果它无法做到这一点，就不能保证没有这样的循环存在。你只是没有找到它。

（我怀疑保证的算法将是NP完全问题。）

- hola · Answer 2

一般情况下，这个问题是NP难的，可以通过将哈密顿回路归约到它来证明。