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.
0
votes
The longest possible cycle in a graph would be a Hamiltonian cycle. To quote the article: "Determining whether such [...] cycles exist in graphs [...] is NP-complete."
- user3386109
so there is no algorithm that works in polynomial time.
- Autoratch
That would be my answer, but we'll see if someone says otherwise. OTOH, if there are constraints on the graph, those constraints could make the problem easier.
- user3386109
1 Answers
3
votes
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.
