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).
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).