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?

  • $\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$ Commented May 5, 2020 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
    Commented May 6, 2020 at 18:24

1 Answer 1


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.