Как алгоритм Джонсона не многочлен?

Question

Я читал в нескольких ответах, что все циклы в ориентированном графе NP-полны, но алгоритм Джонсона, который находит все простые циклы в графе, пробегает 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 здесь относится не к числу сильно связанных компонентов, а к числу простых циклов в графе. Другими словами, алгоритм перечисляет каждый из простых циклов на графике, проводя не более O (| V | + | E |) раз, перед тем как сообщить об этом. Поскольку число различных простых циклов в графе может быть экспоненциально большим, этот алгоритм будет работать в экспоненциальном времени в худшем случае.