<p>I just found a reduction from the two disjoint paths problem. Given a directed graph <span class="math-container">$G = (V, E)$</span> and two pairs <span class="math-container">$(s_1, t_1)$</span> and <span class="math-container">$(s_2, t_2)$</span>, we can add a new vertex <span class="math-container">$w$</span> to the graph and an edge from <span class="math-container">$t_1$</span> to <span class="math-container">$w$</span> and from <span class="math-container">$w$</span> to <span class="math-container">$s_2$</span>.</p>

<p>The new graph admits a simple path from <span class="math-container">$s_1$</span> to <span class="math-container">$t_2$</span> through <span class="math-container">$w$</span> if and only if the original graph admits two disjoint paths one from <span class="math-container">$s_1$</span> to <span class="math-container">$t_1$</span> and the other from <span class="math-container">$s_2$</span> to <span class="math-container">$t_2$</span>.</p>

CC BY-SA 4.0
2019-12-19T06:37:04.143Z
2019-12-19T12:15:17.187Z
2019-12-19T12:15:17.187Z
Narek Bojikian
<p>Given a <strong>directed</strong> graph <span class="math-container">$G = (V, E)$</span> and three vertices <span class="math-container">$u, v, w \in V$</span>. Is it NP-Hard to find whether there is a simple path from <span class="math-container">$u$</span> to <span class="math-container">$v$</span> passing through <span class="math-container">$w$</span>?</p>

<p>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</p>

<ul>
<li>two disjoint directed paths,</li>
<li>and directed simple cycle passing through two vertices.</li>
</ul>

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

CC BY-SA 4.0
2019-12-19T02:36:43.663Z
Yes it is NP-Complete.
Chandra Chekuri
CC BY-SA 4.0
2019-12-19T05:01:07.627Z
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
CC BY-SA 4.0
2019-12-19T15:05:09.573Z
This particular case is explained in case (ii) of Theorem 2 in the Fortune, Hopcroft and Wyllie paper.
Kristoffer Arnsfelt Hansen
<graph-theory><graph-algorithms><np-hardness><disjoint-paths>
Hardness of finding if a vertex lies on a simple directed path between two vertices
Narek Bojikian
# Hardness of finding if a vertex lies on a simple directed path between two vertices

(Asked by: username_0 on 2019-12-19)

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.

**Tags:** graph-theory, graph-algorithms, np-hardness, disjoint-paths

> **Comments:**
> **username_1**: Yes it is NP-Complete.  
> **username_0**: can you provide some more resources please? the official name of the problem or a paper mentioning the problem would be very appreciated :)  
> **username_2**: This particular case is explained in case (ii) of Theorem 2 in the Fortune, Hopcroft and Wyllie paper.  

---

## 1 answers

### Answer by username_0 on 2019-12-19. Score: 6 | Accepted answer

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


---

