# Hardness of finding if a vertex lies on a simple directed path between two vertices

Given a directed graph $$G = (V, E)$$ and three vertices $$u, v, w \in V$$. Is it NP-Hard to find whether there is a simple path from $$u$$ to $$v$$ passing through $$w$$?

I found a couple of hardness statements of similar problems referring all to the same paper [The directed subgraph homeomorphism problem, Fortune, Hopcroft and Wyllie, 1980]. The papers include

• two disjoint directed paths,
• and directed simple cycle passing through two vertices.

However, it is not very clear to me, if this case reduces directly to the paper as in the case of these to problems.

• Yes it is NP-Complete. – Chandra Chekuri Dec 19 '19 at 2:36
• can you provide some more resources please? the official name of the problem or a paper mentioning the problem would be very appreciated :) – narek Bojikian Dec 19 '19 at 5:01
• This particular case is explained in case (ii) of Theorem 2 in the Fortune, Hopcroft and Wyllie paper. – Kristoffer Arnsfelt Hansen Dec 19 '19 at 15:05

I just found a reduction from the two disjoint paths problem. Given a directed graph $$G = (V, E)$$ and two pairs $$(s_1, t_1)$$ and $$(s_2, t_2)$$, we can add a new vertex $$w$$ to the graph and an edge from $$t_1$$ to $$w$$ and from $$w$$ to $$s_2$$.
The new graph admits a simple path from $$s_1$$ to $$t_2$$ 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$$.