Johnson의 알고리즘은 다항식이 아닌 방법은 무엇입니까?

Question

나는 여러 그래프를 통해 지시 그래프에서 모든 사이클을 찾는 것이 NP 완전하다고 읽었지만 그래프의 모든 간단한 사이클을 찾는 Johnson의 알고리즘은 O ((V + E) (C + 1)) 시간 (여기서 C는 그래프에서 강하게 연결된 구성 요소의 수입니다.) E < = V^2이고 C는 < = V가 O (V^3)가되므로 다항식이라고 생각합니다.

존슨의 알고리즘 : http://www.cs.tufts.edu/comp/150GA/homeworks/hw1/Johnson%2075.PDF

Answer 1

은 링크 된 PDF에 따르면, 양 C는 여기에 강력하게 연결된 구성 요소의 수를하지 의미가 아니라 그래프의 간단한 사이클의 수. 다시 말해, 알고리즘은 그래프의 각 c 간단한 사이클을 나열하고, 각각을보고하기 전에 최대 O (| V | + | E |) 시간을 소비합니다. 그래프의 서로 다른 단순 사이클의 수는 기하 급수적으로 커질 수 있기 때문에이 알고리즘은 최악의 경우 기하 급수적으로 실행됩니다.