Finding the hamiltonian path in a directed cyclic graph

Question

i want to know if there is an algorithm to find the longest cyclic path in a directed weighted graph (i think this i a problem of finding the largest Hamiltonian sub-graph).

I need to start from one vertex and return to the same vertex, whit the most possible nodes traversed.

Thanks

Answer 1

This problem is a special case of the optimal euler circuit problem where all edge weights are 1; the original problem is NP-complete. Moreover, this problem can be used to solve the Hamiltonian Graph problem (a Hamiltonian cycle exists if and only if the optimal circuit traverses all nodes), so it remains NP-complete even with the special case restriction. Any exact solution will (unless P = NP) require exponential time. You may find this paper helpful; it describes a polynomial-time approximation algorithm for this problem, as well as a polynomial-time algorithm for cases where the graph has at most degree 4:

Qiao, Yu. "Optimal Euler Circuit of Maximum Contiguous Cost." IEICE Trans. Fundamentals E90-A, no. 1 (2007): 274-280.