Menemukan siklus rata dalam grafik langsung

Diberikan grafik terarah, kami ingin memutuskan apakah itu berisi siklus terarah dengan panjang genap. Makalah tahun 1997 oleh YUSTER dan ZWICK ini menyatakan bahwa masalahnya tidak diketahui dalam dan juga tidak diketahui lengkap.$P$$NP$

Apakah ada hasil terbaru yang menyelesaikan kompleksitas masalah siklus genap dalam grafik yang diarahkan?

Ya, algoritma waktu polinomial pertama kali diberikan dalam:

Neil Robertson, PD Seymour, Robin Thomas. "Permanen, orientasi Pfaff, dan bahkan sirkuit terarah." Annals of Mathematics 150.3 (1999): 929-975. arXiv

sunting: Sebenarnya, menurut bagian ucapan terima kasih dari makalah di atas, hasilnya pertama kali diperoleh oleh McCuaig yang kemudian menerbitkannya sebagai:

William McCuaig. "Masalah Permanen Pólya." Electr. J. Comb. 11 (1) (2004) http://www.combinatorics.org/ojs/index.php/eljc/article/view/v11i1r79