Поиск максимального простого пути

Имеется неориентированный невзвешенный граф с циклами (вершин ~ 8000, ребер ~ 80000). Задача - найти максимальный простой путь между любыми двумя вершинами (т.е. вершины не должны повторяться).  Понятно, что NP-complete, вопрос как максимально эффективно осуществить перебор? Может быть можно быстро вычислить приблизительное значение? Пробовал dijkstra c весом -1 получил путь 6400 вершин, хочется лучше
Заранее спасибо!