# How to efficiently find a loop between two nodes in a directed graph?

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?

• 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 – kodecharlie May 5 '20 at 4:31
• I think this can tell if there is a cycle, but cannot return a cycle that passes two specific nodes. – Yuliang Li May 6 '20 at 18:24

## 1 Answer

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