Нахождение четного цикла в ориентированных графах

10

Учитывая направленный граф, мы хотим решить, содержит ли он направленный цикл четной длины. В этой статье 1997 года, написанной YUSTER и ZWICK, утверждается, что проблема не в том, что она находится в а также в том, что она не является N P -полной.пNп

Есть ли какой-либо недавний результат, который разрешает сложность проблемы четного цикла в ориентированных графах?

Мухаммед Аль-Туркистани
источник

Ответы:

17

Да, алгоритм полиномиального времени был впервые дан в:

Нил Робертсон, П.Д. Сеймур, Робин Томас. «Перманенты, пфаффовы ориентации и даже направленные контуры». Анналы математики 150,3 (1999): 929-975. Arxiv

редактировать: На самом деле, в соответствии с разделом благодарностей вышеупомянутого документа, результат был впервые получен Маккуейгом, который позже опубликовал его как:

Уильям Маккуэйг. «Постоянная проблема Полиа». Электр. J. Comb. 11 (1) (2004) http://www.combinatorics.org/ojs/index.php/eljc/article/view/v11i1r79

Колин Маккуиллан
источник
1
Спасибо за быстрый ответ. Хорошая топологическая характеристика.
Мухаммед Аль-Туркистани