# Is finding all cycles in a graph using some version of Johnson's algorithm (code provided) really polynomial (benchmark provided)?

This is the algorithm I'm using: https://stackoverflow.com/questions/12367801/finding-all-cycles-in-undirected-graphs/14115627#14115627

Worst case time complexity should be O(|V|^{2}\log |V|+|V||E|)} https://en.wikipedia.org/wiki/Johnson%27s_algorithm

My findings running benchmarks using the first algorithm linked:

[polygons (each 3 vertices and 3 edges): milliseconds]

• 10: 332 ms (~30 vertices, 30 edges)
• 11: 789 ms
• 12: 2344 ms
• 13: 7524 ms
• 14: 16788 ms
• 15: 54182 ms (~45 vertices, 45 edges)

That's exponential growth!

My only question: Is this a polynomial time algorithm that I'm using to find all cycles in a graph or not?

Thanks :)

• I'm not sure what you're trying to do. Johnson's algorithm finds shortest paths, not cycles. And, since a graph may have exponentially many cycles in it, you couldn't possibly hope to list all cycles in time polynomial in the size of the input. – David Richerby Jun 6 '16 at 18:38
• You are clearly not using the algorithm (it has description of the usage attached, but someones code to do something not intended). – Evil Jun 6 '16 at 18:59