snippetMinor
How to find the vertices on simple path between two given vertices in a directed graph
Viewed 0 times
pathsimplethehowgraphgivendirectedtwobetweenfind
Problem
Given a directed graph and two distinct vertices S and T, is there a polynomial-time algorithm which finds every vertex which is on at least one simple path from S to T?
It is not difficult to find all vertices that are both successors of S and predecessors of T but this is only a superset of the set above. For example, consider the following graph:
S -> a; a -> b; b -> c; b-> T; c -> a
While a, b and c are all successors of S and predecessors of T, there is no simple path from S to T going through c (because every path from S to T going through c contains twice a and b).
A closely related problem is the following:
Given a directed graph and three distinct vertices S and T and I, is there a polynomial-time algorithm to decide if there exist a simple path from S to T going through I.
A polynomial-time algorithm to this latter problem can be use to build a polynomial algorithm to the former since we can apply it succesively by replacing I by every node in the graph (or more efficiently to every node that is both a succesor of S and a predecessor of T).
It is not difficult to find all vertices that are both successors of S and predecessors of T but this is only a superset of the set above. For example, consider the following graph:
S -> a; a -> b; b -> c; b-> T; c -> a
While a, b and c are all successors of S and predecessors of T, there is no simple path from S to T going through c (because every path from S to T going through c contains twice a and b).
A closely related problem is the following:
Given a directed graph and three distinct vertices S and T and I, is there a polynomial-time algorithm to decide if there exist a simple path from S to T going through I.
A polynomial-time algorithm to this latter problem can be use to build a polynomial algorithm to the former since we can apply it succesively by replacing I by every node in the graph (or more efficiently to every node that is both a succesor of S and a predecessor of T).
Solution
Thanks for your answers.
As master foo pointed out, the second problem -- given a directed graph and three distinct vertices $s, t$ and $i$, decide if there exist a simple path from $s$ to $t$ going through $i$ -- is indeed NP-complete.
From the paper The Directed Subgraph Homeomorphism Problem by Steven Fortune, John E. Hopcroft and James Wyllie, it is clear that the pattern graph $s \to i \to t$ is one for which the fixed directed subgraph homeomorphism problem is NP-complete since it is a tree of depth two.
Here are few definitions from this paper:
The subgraph homeomorphism problem is to determine: if a pattern graph p is
homeomorphic to a subgraph of an input graph G. The homeomorphism maps nodes
of P to nodes of G and arcs of P to simple paths in G. The graphs P and G are either both directed or both undirected. The paths in G corresponding to arcs in P must be pairwise node-disjoint. The mapping of nodes in P to nodes in G may be specified or left arbitrary. This problem can be viewed as a generalized path-finding problem. For example, if the pattern graph consists of two disjoint arcs and the node mapping is given, then the problem is equivalent to finding a disjoint pair of paths between specified vertices in
the input graph.
Basically, only the pattern graphs that are trees of depth one and their reverse graphs (with possibly loops arcs on the root) can be solved in polynomial time.
Let C be the collection of all directed graphs with a distinguished node called the root possessing the property that either the root is the head of every arc or the root is the tail of every arc. Note that the root may be both the head and tail of some arcs and thus loops at the root are allowed. Equivalently, a graph is in C if, when all loops at the root are deleted and multiple arcs between pairs of nodes are merged into single arcs, the resulting graph is a tree of height at most one.
[...]
Next we show that for each pattern P not in C the fixed subgraph homeomorphism
problem with pattern P is NP-complete.
I have not read the proof yet so I'll stop here.
There is also a close connection from the problem I have just mentionned and the two disjoint paths problem as pointed out by one of my collegue. The two dijsoint paths problem is:
Given a directed graph and four distinct vertices $s_1, t_1, s_2, t_2$, decide if there exist two pairwise node disjoints simple paths from $s_1$ to $t_2$ and from $s_2$ to $t_2$.
This problem for directed graphs is well known to be NP-complete.
However, there is a simple transformation from the two disjoint paths problem to the $s \to i \to t$ problem. In order to do that, we need to add one extra node $i$ and the two extra edges $t_1 \to i$ and $i \to s_2$.
If there was a polynomial algorithm to solve the $s \to i \to t$ problem, we could use it to solve the two disjoint paths problem in polynomial time with the simple transformation above and thereby solving the $s \to i \to t$ problem.
As master foo pointed out, the second problem -- given a directed graph and three distinct vertices $s, t$ and $i$, decide if there exist a simple path from $s$ to $t$ going through $i$ -- is indeed NP-complete.
From the paper The Directed Subgraph Homeomorphism Problem by Steven Fortune, John E. Hopcroft and James Wyllie, it is clear that the pattern graph $s \to i \to t$ is one for which the fixed directed subgraph homeomorphism problem is NP-complete since it is a tree of depth two.
Here are few definitions from this paper:
The subgraph homeomorphism problem is to determine: if a pattern graph p is
homeomorphic to a subgraph of an input graph G. The homeomorphism maps nodes
of P to nodes of G and arcs of P to simple paths in G. The graphs P and G are either both directed or both undirected. The paths in G corresponding to arcs in P must be pairwise node-disjoint. The mapping of nodes in P to nodes in G may be specified or left arbitrary. This problem can be viewed as a generalized path-finding problem. For example, if the pattern graph consists of two disjoint arcs and the node mapping is given, then the problem is equivalent to finding a disjoint pair of paths between specified vertices in
the input graph.
Basically, only the pattern graphs that are trees of depth one and their reverse graphs (with possibly loops arcs on the root) can be solved in polynomial time.
Let C be the collection of all directed graphs with a distinguished node called the root possessing the property that either the root is the head of every arc or the root is the tail of every arc. Note that the root may be both the head and tail of some arcs and thus loops at the root are allowed. Equivalently, a graph is in C if, when all loops at the root are deleted and multiple arcs between pairs of nodes are merged into single arcs, the resulting graph is a tree of height at most one.
[...]
Next we show that for each pattern P not in C the fixed subgraph homeomorphism
problem with pattern P is NP-complete.
I have not read the proof yet so I'll stop here.
There is also a close connection from the problem I have just mentionned and the two disjoint paths problem as pointed out by one of my collegue. The two dijsoint paths problem is:
Given a directed graph and four distinct vertices $s_1, t_1, s_2, t_2$, decide if there exist two pairwise node disjoints simple paths from $s_1$ to $t_2$ and from $s_2$ to $t_2$.
This problem for directed graphs is well known to be NP-complete.
However, there is a simple transformation from the two disjoint paths problem to the $s \to i \to t$ problem. In order to do that, we need to add one extra node $i$ and the two extra edges $t_1 \to i$ and $i \to s_2$.
If there was a polynomial algorithm to solve the $s \to i \to t$ problem, we could use it to solve the two disjoint paths problem in polynomial time with the simple transformation above and thereby solving the $s \to i \to t$ problem.
Context
StackExchange Computer Science Q#4771, answer score: 3
Revisions (0)
No revisions yet.