Оптимизация для решения проблемы самого длинного пути в циклическом графе

Какие оптимизации существуют для попытки найти самый длинный путь в циклическом графе?

Известно, что самый длинный путь в циклических графах является NP-полным. Какие оптимизации или эвристика могут сделать поиск самого длинного пути быстрее, чем DFS-анализ всего графа? Есть ли вероятностные подходы?

У меня есть график с определенными качествами, но я ищу ответ на этот вопрос в общем случае. Ссылки на документы были бы фантастическими. Вот частичный ответ:

1. Подтвердите, что это циклично. Самый длинный путь в ациклических графах легко вычисляется с помощью динамического программирования.

2. Выясните, является ли граф плоским (какой алгоритм лучше?). Если это так, вы можете проверить, является ли это блочным графом, птолемеевым графом или кактусовым графом, и применить методы, найденные в этой статье .

3. Узнайте, сколько простых циклов существует, используя алгоритм Дональда Б. Джонсона ( реализация Java ). Вы можете превратить любой циклический граф в ациклический, удалив ребро в простом цикле. Затем вы можете запустить решение динамического программирования, которое можно найти на странице Википедии . Для полноты картины вам придется делать это N раз для каждого цикла, где N - длина цикла. Таким образом, для всего графа количество запусков DP-решения равно произведению длин всех циклов.

4. Если вам нужно выполнить DFS для всего графа, вы можете сократить некоторые пути, вычислив «достижимость» каждого узла заранее. Эта достижимость, которая в основном применима к ориентированным графам, представляет собой количество узлов, которые каждый узел может достичь без повторений. Это максимально возможный самый длинный путь от этого узла. С этой информацией, если ваш текущий путь плюс достижимость дочернего узла меньше, чем самый длинный, который вы уже нашли, нет смысла брать эту ветвь, поскольку невозможно найти более длинный путь.