约翰逊的算法如何不是多项式？

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 |）时间。由于图中不同简单周期的数量可能呈指数级增长，因此该算法将在最坏情况下以指数时间运行。