Biorąc pod uwagę ukierunkowany wykres, chcemy zdecydować, czy zawiera on ukierunkowany cykl o równej długości. W tym artykule YUSTER i ZWICK z 1997 r. Stwierdzono, że nie wiadomo, że problem występuje w ani że nie ma w nim zakończenia.
Czy jest jakiś wynik, który rozwiązuje złożoność problemu z równomiernym cyklem w grafach ukierunkowanych?
Odpowiedzi:
Tak, po raz pierwszy podano algorytm wielomianowy w:
Neil Robertson, PD Seymour, Robin Thomas. „Stałe, orientacje Pfaffowskie, a nawet obwody ukierunkowane”. Annals of Mathematics 150.3 (1999): 929-975. arXiv
edytuj: Właściwie, zgodnie z sekcją potwierdzeń powyższej pracy, wynik został po raz pierwszy uzyskany przez McCuaiga, który później opublikował go jako:
William McCuaig. „Stały problem Pólyi”. Electr. J. Comb. 11 (1) (2004) http://www.combinatorics.org/ojs/index.php/eljc/article/view/v11i1r79