math - verices=|V| の有向グラフのサイクルの最大数 エッジ =|E|

Question

拝啓、

私は、2 人用の正規形ゲーム (ゲーム理論) を表す特定のグラフィック構造を扱っています。Tarjans を介して O(V+E) の有向グラフのすべての強連結成分を計算できることは知っていますが、強連結成分のすべての単純なサイクルを計算することの複雑さはどのようなものでしょうか? そして、強連結成分を定義する頂点の数が与えられた場合、そのような単純なサイクルの数に既知の上限がある場合は?

これらの問題の両方に関連する文献/アルゴリズムを探しています。ありがとう！

Answer 1

あなたの場合、可能な単純な 2k サイクルの数は(n choose k) * (m choose k)です。n、m、k が小さくない場合、これは指数関数的に増加します。

サイクルを列挙することはできません。合理的な時間内に任意のグラフでそれらをカウントできるとは思えません。動的プログラミング手法を使用しても、これには指数関数的な時間と空間が必要です (ただし、これらの手法を使用しない場合よりも指数が低くなります)。