I have a problem in which I need to find the longest path. Given an unveighted undirected graph. Starting from a given vertex I need to visit as many vertices as possible and finish in the same one without visiting each of them more then once.
Most of the algorithms I found were for a special case (acyclic, directed etc.). An idea can be to find Hamiltonian cycle for every subset of the vertices (the subset can be generated with backtrack). But I guess there must be a far better algorithm.
As you've discovered, finding the largest cycle involves finding the Hamiltonian cycles of its subgraphs, and thus is NP-complete - unless you're working on some special class of graphs, any solution is going to be exponential in complexity.
A smart brute force approach (e.g. bitmask) is the best efficiency one can get for this type of problem.