10
$\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?

$\endgroup$
17
$\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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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