Поскольку проблема самого длинного ориентированного пути в ориентированном графе не может быть аппроксимирована за полиномиальное время с коэффициентом n^(1-epsilon) для любого epsilon > 0, мы можем быстро сделать вывод, что это также относится и к самому длинному циклу в ориентированном графе. если P = NP ( источник ).
Вы можете сделать сокращение следующим образом:
Выберите вершину v, продублируйте v в v1 и v2, продублируйте также все соответствующие дуги. Теперь найдите самый длинный направленный путь от v1 до v2.
Сделайте это для всех вершин графа. Это дает вам самый длинный направленный цикл на графике.
Вывод: alpha -приближение за полиномиальное время для задачи с самым длинным циклом в ориентированных графах отсутствует (если, конечно, P = NP).