3
$\begingroup$

Given two nodes in a directed graph, how can I find a loop (if exists) that pass these two nodes? The loop cannot pass a node more than once. And if there isn't such a loop, how to efficiently determines it?

$\endgroup$
  • $\begingroup$ Look up topological sort. Here's the rough sketch of what I've seen. I believe it has linear overhead: 0. Declare an empty set called Z. 1. Put all nodes into the same pool of nodes. Call this set W. 2. Call the node in W with the largest number of dependents (ie, children) LN. If LN has a child in Z, then there is a cycle and we quit. Otherwise, we put LN into Z. 3. Goto step (2) and continue until either a cycle is discovered or W is empty. I may be missing something. But the key point is that by just looking at $\endgroup$ – kodecharlie May 5 at 4:31
  • $\begingroup$ I think this can tell if there is a cycle, but cannot return a cycle that passes two specific nodes. $\endgroup$ – Yuliang Li May 6 at 18:24
10
$\begingroup$

This problem has been shown to be NP-complete in the following paper:

S. Fortune, J. Hopcroft, J. Wyllie:
"The directed subgraph homeomorphism problem"
Theoretical Computer Science 10 (1980), pp. 111-121

| cite | improve this answer | |
$\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.