Encontrar ciclo uniforme em gráficos direcionados

10

Dado um gráfico direcionado, queremos decidir se ele contém um ciclo direcionado de comprimento uniforme. Este artigo de 1997 de YUSTER e ZWICK afirma que não se sabe que o problema está em nem se sabe que ele está completo como .PNP

Existe algum resultado recente que resolva a complexidade do problema do ciclo par em gráficos direcionados?

Mohammad Al-Turkistany
fonte

Respostas:

17

Sim, um algoritmo de tempo polinomial foi fornecido pela primeira vez em:

Neil Robertson, PD Seymour, Robin Thomas. "Permanentes, orientações pfaffianas e até circuitos direcionados". Annals of Mathematics 150.3 (1999): 929-975. arXiv

edit: Na verdade, de acordo com a seção de agradecimentos do artigo acima, o resultado foi obtido pela primeira vez por McCuaig, que posteriormente o publicou como:

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

Colin McQuillan
fonte
11
Obrigado pela resposta rápida. Caracterização topológica agradável.
Mohammad Al-Turkistany