7
$\begingroup$

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:

enter image description here

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

enter image description here

Nodes that are part of simple paths: U, A and V.

Example 2

enter image description here

Nodes that are part of simple paths: U, A, B, C, D, E and V.

Example 3

enter image description here

Nodes that are part of simple paths: U, A, C, D, E, F and V.

Example 4

enter image description here

Nodes that are part of simple paths: U, A, B, C, D, E, F and V.

$\endgroup$
1
  • $\begingroup$ I suspect the problem is NP-hard for its similarity to the two disjoint paths problem on directed graphs which is also NP-hard but I can not find a proof. Note that the problem of finding whether a vertex x lies on a simple path from a to b is similar to finding two vertex-disjoint paths one from a to x and one from x to b. $\endgroup$ Dec 19, 2019 at 0:26

2 Answers 2

3
$\begingroup$

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!

$\endgroup$
2
  • 1
    $\begingroup$ Do you mean "admits an $s_1,t_2$ simple path"? $\endgroup$ Dec 19, 2019 at 21:36
  • $\begingroup$ Yes you're right :) $\endgroup$ Dec 19, 2019 at 22:21
-1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Good idea, but I don't think this will work. If I add an edge from V to U in the example graphs I provided, all nodes would be in the same SCC for all the examples. $\endgroup$ Dec 18, 2019 at 14:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.