約翰遜的算法如何不是多項式？

Question

我讀過多個答案，發現有向圖中的所有循環都是NP完全的，但約翰遜的算法在圖中找到所有簡單循環，運行在O（（V + E）（C + 1） ）時間（其中C是圖中強連通分量的數目），我認爲這是多項式，因爲E < = V^2和C變成O（V^3）的V，對嗎？

約翰遜的算法：http://www.cs.tufts.edu/comp/150GA/homeworks/hw1/Johnson%2075.PDF

Answer 1

根據您鏈接的PDF，該量C.這裏指的不是強連接組件的數量，而是在圖形簡單的週期數。換句話說，該算法列出了圖中每個c個簡單週期，在報告每個週期之前花費最多O（| V | + | E |）時間。由於圖中不同簡單週期的數量可能呈指數級增長，因此該算法將在最壞情況下以指數時間運行。