Find all nodes on simple paths between two nodes in cyclic directed graph

Question

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.

Answer 1

This problem is NP-hard. It is actually NP-Hard to prove if a vertex $w$ lays on a simple path from $u$ to $v$. Here is a prove of hardness through a reduction from the two disjoint paths problem.

Given a directed graph $G = (V, E)$ and two pairs of vertices $(s_1, t_1)$ and $(s_2, t_2)$, we build the new graph $G'$ by adding a new vertex $w$ to $G$ and add an edge from $t_1$ to $w$ and an edge from $w$ to $s_2$. The new graph admits an $s_1, t_2$ simple path passing through $w$ if and only if the original graph admits two disjoint paths one from $s_1$ to $t_1$ and the other from $s_2$ to $t_2$. Try to prove this claim as an exercise!

Answer 2

EDIT: The answer below is not correct. It finds all vertices that are on some path from $U$ to $V$, not on some simple path from $U$ to $V$. It seems we need a directed analog of biconnected components for this to work.

---

Add an edge from $V$ to $U$, then find all vertices in the strongly connected component containing $U$ and $V$. (They will be in two different SCCs if and only if there is no path from $U$ to $V$ in the original graph.)

This works because two vertices are in the same SCC if and only if there is a simple cycle containing both vertices.

Credit to bennos on Stack Overflow for providing me the answer when I asked the analogous question for undirected graphs back in 2012. For undirected graphs, you use biconnected components instead of strongly connected components.