<p>Yes, a polynomial time algorithm was first given in:</p>

<p>Neil Robertson, P. D. Seymour, Robin Thomas. "Permanents, Pfaffian orientations, and even directed circuits." Annals of Mathematics 150.3 (1999): 929-975. <a href="http://arxiv.org/abs/math.CO/9911268">arXiv</a></p>

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

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

CC BY-SA 3.0
2013-11-07T14:33:31.867Z
Thanks for the quick answer. Nice topological characterization.
Mohammad Al-Turkistany
CC BY-SA 3.0
2013-11-07T14:19:05.133Z
2013-11-07T14:30:18.103Z
2013-11-07T14:30:18.103Z
Colin McQuillan
<p>Given a directed graph, we want to decide whether it contains a directed cycle of even length. This 1997 paper by <a href="http://perso.ens-lyon.fr/eric.thierry/Graphes2010/yz97.pdf">YUSTER and ZWICK</a> states that the problem is not known to be in $P$ nor is it known to be $NP$-complete.</p>

<blockquote>
  <p>Is there any recent result that resolves the complexity of the even cycle problem in directed graphs?</p>
</blockquote>

<cc.complexity-theory><reference-request><graph-theory>
Finding even cycle in directed graphs
Mohammad Al-Turkistany
# Finding even cycle in directed graphs

(Asked by: username_0 on 2013-11-07)

Given a directed graph, we want to decide whether it contains a directed cycle of even length. This 1997 paper by [YUSTER and ZWICK](http://perso.ens-lyon.fr/eric.thierry/Graphes2010/yz97.pdf) 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?

**Tags:** cc.complexity-theory, reference-request, graph-theory

---

## 1 answers

### Answer by username_1 on 2013-11-07. Score: 19 | Accepted answer

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](http://arxiv.org/abs/math.CO/9911268)

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>

> **Comments:**
> **username_0**: Thanks for the quick answer. Nice topological characterization.  

---

