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