Znalezienie nawet cyklu na ukierunkowanych wykresach

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.$P$$NP$

Czy jest jakiś wynik, który rozwiązuje złożoność problemu z równomiernym cyklem w grafach ukierunkowanych?

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