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

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

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!

StackExchange Computer Science Q#118664, answer score: 3