Given two nodes U
and V
in a cyclic directed graph, how can I find the set of nodes that are part of a simple path from U
to V
?
Attempt 1
I've tried using a DFS from U
that stores the set of visited nodes when V
is reached, and backtracks when a cycle is detected. But this algorithm must traverse all paths, and can hence be very slow for large graphs.
I cannot stop the DFS early when a node that has already been deemed to be part of a simple path is reached:
If the DFS goes U -> A -> B -> C -> D -> E -> V
, those nodes are deemed to be part of a simple path. After backtracking to E
and traversing to F
and A
, a cycle is found. After backtracking to U
and traversing to C
, a node that is already part of a simple path is found, but the DFS cannot stop, since further traversal is necessary to figure out that F
is also part of a simple path: U -> C -> D -> E -> F -> A -> V
.
The same argument shows that I can't stop the DFS early when a node that has already been deemed to be part of a cycle is reached.
Attempt 2
Another idea I've tried is to store on the edges sets of potential cycle root nodes that must be traversed in order to reach V
from the edge's sink. For instance for the edge E -> F
, A
must be traversed in order to reach V
. Hence the DFS does not have to traverse this edge if A
has already been visited.
It is not straight-forward to decide which nodes are potential cycle roots, and on which edges they need to be stored. My implementation attempts have unfortunately been too slow for large and complex graphs. After the potential cycle roots have been calculated, however, performing the DFS has been fast.
Question
Are there any efficient algorithms for finding the set of nodes that are part of a simple path between two nodes?
Examples
Just to make things really clear, these are the outputs I am looking for for a few different graphs:
Example 1
Nodes that are part of simple paths: U
, A
and V
.
Example 2
Nodes that are part of simple paths: U
, A
, B
, C
, D
, E
and V
.
Example 3
Nodes that are part of simple paths: U
, A
, C
, D
, E
, F
and V
.
Example 4
Nodes that are part of simple paths: U
, A
, B
, C
, D
, E
, F
and V
.