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?
2
-
$\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$– kodecharlieMay 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 LiMay 6, 2020 at 18:24
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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
