Is this graph theory problem NP-Complete? Back in college I was in an introductory Graph Theory (undergrad) class.  For one assignment I was creating an algorithm to solve the following problem:

Find an odd-length cycle in a directed Graph N

While googling the problem, I found a reference that this problem was NP-Complete.  I dismissed that because I already thought I had a good algorithm, so obviously it couldn't be NP-Complete, and also because the problem doesn't seem as intuitively difficult as the other NP-Complete problems I'm familiar with.  Unfortunately I haven't been able to find this reference since, so I'm not able to link to it here.
However every once in a while I think back on this, and since I don't know that it's not NP-Complete, I always wonder "what if"?
So to put my mind to rest, what I'm looking for is:


*

*Verification that this problem is not NP-Complete.

*Are there any known similar problems that are in NP-Complete?  Something like, "Find the shortest odd-length cycle in a directed Graph N"?  (I have looked through lists online but didn't spot anything).

 A: I'm quite sure that this is polynomial. Here's my idea:
There is an odd cycle in a DAG iff there is an odd closed egde progression. To see "$\Leftarrow$": given an odd edge progression, look for a cycle in it. If it's not already odd, remove it from the edge progression. The resulting edge progression is still odd and closed.
To find an odd edge progression, a variant of the Moore-Bellman-Ford algorithm can be used to test for every vertex if it lies on an odd closed edge progression. Given a vertex $s$, mark $s$ as even and every other vertex as unreachable. Now for every edge $(v, w)$, if $v$ is marked even, mark $w$ as odd (or vice versa); a vertex may be marked as both even and odd. If after $|V|$ iterations $s$ is marked as odd it lies on an odd closed edge progression (one can be found by tracing back how it was marked).
A: As for your second question, a very close variant is NP-complete:
Input: Given a directed graph $G(V, E)$ and an edge $u \in E$, 
Question: Is there a directed odd cycle through edge $u$? 
