algorithm - 枚举有向图的所有最小有向环

Question

我有一个有向图，我的问题是枚举该图的所有最小(不能构造为其他循环的并集的循环)有向循环。这与 Tarjan 算法的输出不同。例如，对于 this wikipedia page 处的有向图, 我想得到 c <-> d 和 d <-> h 作为两个独立的有向循环。

我不知道这个问题是否是多项式的。我翻阅了一篇论文“Enumerating Minimal Dicuts and Strongly Connected Subgraphs”，似乎得出的结论是这个问题是增量多项式(我不知道它是什么意思)，但我无法为这篇文章提取算法。我也不确定最小强连通分量是否等同于我定义的最小循环。

有人知道这个问题的答案吗？

提前致谢!!!

Answer 1

如果我们正在寻找最短路径循环，这似乎很容易。

• 就做一个breadth first search在所有节点上搜索从节点到自身的最短路径。
• 如果没有找到路径，可以删除这个不在循环中的节点
• 如果您找到一条路径，则您已经找到了您的最小循环之一(因为我们正在寻找最短路径，所以我们可以确保此循环不会是两个较短循环的并集)。
  • 将其中的所有节点折叠成一个大的新节点，并根据需要调整边。

• 继续下去，直到不再有节点。

• 当您处理完所有节点(顶点)后，您就拥有了您正在寻找的最小循环......但是有一个技巧。

如果循环仅使用初始集合中的节点表示，您可以“按原样”保留它。但是你必须将“大节点”转换为路径(循环之间的公共(public)边缘)并且每个大节点都可以被几个这样的路径替换(对于级别 1 的大节点至少有 2 个，即不包含大节点本身).找到的循环以这样一种方式构建，您可以选择任何路径并仍然获得最小循环集(没有循环可以完成其他两个的并集)，但是有几个可能的这样的集合。您可以添加约束以在大节点中选择路径时始终采用最短路径，但仍然可以存在相同长度的路径。所以这个问题的解决方案显然不够独特。

使用这种简单的方法，复杂度为 O(V.(E+V))，其中 V 是顶点数，E 是边数。 O(E+V) 来自广度优先，最坏的情况是你必须执行 BFS V 次。因此它绝对是更好的多项式。我相信我所描述的在一般情况下确实是 O(log(V).(E+V))，但我还没有证明它(如果它是真的)。​​