11
$\begingroup$

Given a directed graph, we want to decide whether it contains a directed cycle of even length. This 1997 paper by YUSTER and ZWICK states that the problem is not known to be in $P$ nor is it known to be $NP$-complete.

Is there any recent result that resolves the complexity of the even cycle problem in directed graphs?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
18
$\begingroup$

Yes, a polynomial time algorithm was first given in:

Neil Robertson, P. D. Seymour, Robin Thomas. "Permanents, Pfaffian orientations, and even directed circuits." Annals of Mathematics 150.3 (1999): 929-975. arXiv

edit: Actually, according to the acknowledgements section of the above paper, the result was first obtained by McCuaig who later published it as:

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

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Thanks for the quick answer. Nice topological characterization. $\endgroup$
    – Mohammad Al-Turkistany
    Nov 7, 2013 at 14:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.