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.

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.

Thanks for your answers. As master foo pointed, the second problem: Given a directed graph and three distinct vertices S and T and I, deciding if there exist a simple path from S to T going through I, is indeed NP complete.

From the paper from Steven Fortune and John E. Hopcroft and James Wyllie, it is clear that the pattern graph S->I->T is one for which the fixed directed subgraph homeomorphism problem is NP complete since it is a tree of depth 2.

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 1 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."

"Given a directed graph and four distinct vertices S1, T1, S2, T2, decide if there exist two paiwise node disjoints simple paths from S1 to T2 and from S2 to T2".

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->I->T problem. In order to do that we need to add one extra node I and the two extra edges T1->I and I->S2.

If there was a polynomial algorithm to solve the S->I->T problem, we could use it to solve the two disjoint paths problem in polynomial time with the simple transformation above and by solving the S1->I->T2 problem.

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.

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.