Совершенно очевидно, что это NP-complete задача, ибо если бы за полиномиальное время можно было бы найти максимальный простой цикл, то мы бы автоматически решили бы и TSP (задачу коммивояжера). Просто путем проверки, гамильтонов ли цикл.
Так что про точный алгоритм можно забыть (если конечно P != NP). Лучшее что придумало человечество на сегодняшний день - H.N. Gabow. Finding Paths and Cycles of Superpolylogarithmic Length, In Proceedings of the 36th ACM Symposium on the Theory of Computing (STOC), 2004, 407-416
Но и там циклы далеки от максимальных. Правда время полиномиально

Совершенно очевидно, что это NP-complete задача,

по опредилению вроде.

гамильтонов цикл всегда минимален для данного графа.

Я, конечно, не спорю, что гамильтонов цикл здесь не при чем, но есть небольшая поправка - гамильтонов цикл всегда минимален для данного графа.

Гамильтонов цикл - это цикл, который проходит через все вершины графа, но не обязательно, что этот цикл максимальный.

А при чём здесь гамильтонов цикл? Гамильтонов цикл - это цикл, который проходит через все вершины графа, но не обязательно, что этот цикл максимальный.

Просто путем проверки, гамильтонов ли цикл.

Расшифровывая сказанное выше: перебор, перебор и только полный перебор всех циклов. Приведенная ссылка позволяет оптимизировать перебор, но ценой того, что находятся не самые длинные циклы, а просто "немного длинные"