Longest cycle in a directed or undirected graph

general
,
1

May someone provide me with an efficient algorithm for finding longest cycle in a directed or undirected graph?

2

I think the problem is NP complete. It can be solved by Bitmask DP. I think this(see problem 3) and this (see question 4) can prove that there is no polynomial time solution to this problem. Once you are sure that this problem does not have a polynomial time solution, do a smart bruteforce on all subsets.

Refer to this for a very detailed analysis of use of Bitmask in dealing with cycles in a graph.

1 Like
3

Brother you may get your answer on websites like Stackoverflow & GeeksforGeeks, still you may refer as under:-

http://repository.upenn.edu/cgi/viewcontent.cgi?article=1202&context=cis_papers

http://www.scielo.oces.mctes.pt/pdf/tek/n12/n12a04

4

I visited some of the above mentioned sites and found that jhonson’s algorithm is the most efficient algorithm to find out longest cycle.But I am not able to understand how to use Jhonson’s algorithm to find out longest cycle in the given graph

5

Brother you may visit:-

& read the ‘related’ section given on right side of the page while you scroll down.