<p>This problem has been shown to be NP-complete in the following paper:</p>

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

CC BY-SA 4.0
2020-04-14T16:31:36.400Z
2020-04-14T16:31:36.400Z
Gamow
<p>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?</p>

CC BY-SA 4.0
2020-05-05T04:31:35.607Z
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
CC BY-SA 4.0
2020-05-06T18:24:18.090Z
I think this can tell if there is a cycle, but cannot return a cycle that passes two specific nodes.
Yuliang Li
<graph-theory><graph-algorithms><search-problem>
How to efficiently find a loop between two nodes in a directed graph?
Yuliang Li
# How to efficiently find a loop between two nodes in a directed graph?

(Asked by: username_0 on 2020-04-14)

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?

**Tags:** graph-theory, graph-algorithms, search-problem
> **Comments:**
> **username_1**: 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  
> **username_0**: I think this can tell if there is a cycle, but cannot return a cycle that passes two specific nodes.  

---

## 1 answers

### Answer by username_2 on 2020-04-14. Score: 9

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


---

