8
$\begingroup$

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).

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Yes it's 2 disjoint path problem, so it's NP-hard in general digraphs, but you can solve it in DAGs, Planar Digraphs, ..., finally your answer is correct why you wont make it as accepted answer. $\endgroup$ – user742 Jan 10 '13 at 15:50
-1
$\begingroup$

This is an NP-hard problem.

@article{DBLP:journals/tcs/FortuneHW80,
  author    = {Steven Fortune and
               John E. Hopcroft and
               James Wyllie},
  title     = {The Directed Subgraph Homeomorphism Problem},
  journal   = {Theor. Comput. Sci.},
  volume    = {10},
  year      = {1980},
  pages     = {111-121},
  ee        = {http://dx.doi.org/10.1016/0304-3975(80)90009-2},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
$\endgroup$
  • 2
    $\begingroup$ It is not at all obvious from looking at the abstract and introductory section of this article how it relates to this question. Could you please elaborate? $\endgroup$ – Niel de Beaudrap Sep 28 '12 at 14:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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