6
$\begingroup$

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:

  1. Verification that this problem is not NP-Complete.
  2. 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).
$\endgroup$
  • 2
    $\begingroup$ Technical nag: Your problem is not a decision problem, so it would at best be NP-hard. However, you can do DFS from each vertex to find all cycles in which that vertex is contained. This sounds like polynomial time to me, and if you can prove that the problem is not NP-hard, then you would have shown P$\ne$NP. $\endgroup$ – Jesko Hüttenhain Feb 27 '15 at 22:26
  • $\begingroup$ I think I actually used a BFS variant - this was a sub-problem of the actual issue, and I was stopping as soon as I found any odd cycle. But yeah, it seemed very trivial which is why I expect the answer to be a resounding "No". $\endgroup$ – Dan Smolinske Feb 27 '15 at 22:35
  • $\begingroup$ What I ment to say is: I expect the answer to be a resounding "we still don't know", all we know that it is in P. $\endgroup$ – Jesko Hüttenhain Feb 27 '15 at 23:06
  • $\begingroup$ It is not so obvious to me that you could find a cycle in polynomial time. I found a reference (sciencedirect.com/science/article/pii/0166218X88901254#) for a "related" problem: counting odd chordless cycles, which is NP-complete. Your problem is related to the problem of removing vertices from a graph to make it bipartite. Maybe you can look in that literature. $\endgroup$ – megas Feb 27 '15 at 23:53
  • $\begingroup$ @JeskoHüttenhain: Ok, I see what you mean there. FYI I think the original wording might have been a decision problem involving the existence of an odd dicycle, instead of finding one specifically. $\endgroup$ – Dan Smolinske Feb 28 '15 at 0:47
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

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.