I want to know that is there any efficient algorithm to find the length of the longest cycle in a graph?

The graph is an undirected graph.

The algorithm doesn't have to tell what vertex is in the cycle, just only the length.

1 Answers

3
m.raynal On Best Solutions

The problem of finding the longest cycle in a graph is NP-hard, because solving this problem allows to answer the question "Is this graph hamiltonian ?" (does it possess an hamiltonian cycle), which is itself a NP-complete problem.
So, indeed, no efficient algorithm can do that.
There are methods based on matrix multiplication to find a cycle of length k in a graph. You can find explanations about finding cycles using matrix multiplication in this quesion. But beware, the matrix multiplication methods allows to detect walks of a given length between 2 vertices, and the repetition of vertices is allowed in a walk.