math - verices=|V| 的有向图中的最大循环数 和边 =|E|

Question

尊敬的先生，

我正在使用代表 2 人正常形式游戏（博弈论）的特定图形结构。我知道我可以通过 Tarjans 在 O(V+E) 中计算有向图的所有强连通分量，但是想知道计算强连通分量的所有简单循环的复杂性是多少？并且，在给定定义强连通分量的顶点数的情况下，是否存在已知的此类简单循环数的上限？

我正在寻找与这两个问题相关的任何文献/算法。谢谢你！

Answer 1

在您的情况下，可能的简单 2k 周期数为(n choose k) * (m choose k). 如果 n、m 和 k 不小，则它呈指数增长。

枚举周期是不可行的。我怀疑是否有可能在合理的时间内为任意图形计算它们。即使使用动态编程技术，这也需要指数级的时间和空间（但指数比没有这些技术时要低）。