algorithm - 有向グラフのすべてのサイクルを見つける

Question

Tarjan の強連結成分アルゴリズムは、グラフ内にある基本的なサイクルまたはすべてのサイクルのみを見つけることができますか?

Answer 1

O(V + E) (多項式時間) で実行される限り、すべてのサイクルを見つけることはできません。それができれば、多項式時間でハミルトニアン サイクル問題を解くことができますが、この問題は NP 困難です。