<p>It is NP-complete for directed graphs. Even deciding if there exist a path from $s$ to $t$ using vertex $u$ is NP-complete.</p>

<p>The 2-node disjoint path problem is NP-hard for directed graphs$^1$. </p>

<blockquote>
  <p>Given a directed graph $G$ and vertex pairs $(s_1,t_1)$ and
  $(s_2,t_2)$, does there exist two node disjoint paths that goes from
  $s_1$ to $t_1$ and $s_2$ to $t_2$?</p>
</blockquote>

<p>We can reduce this problem to your problem:
Split each vertex of $G$, so each vertex $v$ in $G$ become $v^-$ and $v^+$, and edge $uv$ become $u^+v^-$, also there are edges $v^-v^+$. Add one new vertex $u$, and edges $t_1^+u$ and $us_2^-$. Let this graph be $G'$.</p>

<p>There exist a path from $s_1^-$ to $t_2^+$ in $G'$ that uses $u$ if and only if there exist a node disjoint path between $(s_1,t_1)$ and $(s_2,t_2)$ in $G$.</p>

<ol>
<li><a href="http://www.sciencedirect.com/science/article/pii/0304397580900092#">The directed subgraph homeomorphism problem, Steven Fortune, John Hopcroft, James Wyllie.</a></li>
</ol>

CC BY-SA 3.0
2014-06-30T03:42:29.297Z
2014-06-30T06:39:36.877Z
2014-06-30T06:39:36.877Z
Chao Xu
<p>As Chao mentioned, the directed case is known to be NP-hard even for unweighted graphs.
That said, the problem is <a href="https://cstheory.stackexchange.com/questions/20137/subgraph-containing-all-nodes-and-edges-that-are-part-of-length-limited-simple-s/21861#21861">fixed parameter tractable with respect to the path length</a>.</p>

<p>For undirected graphs, you can solve the weighted version of the problem, deterministically, in $O(|E|^2 \log|E|)$ using <a href="https://cstheory.stackexchange.com/questions/20185/subgraph-containing-all-nodes-and-edges-that-are-part-of-length-limited-simple-s/21809#21809">minimum cost flow</a>.</p>

CC BY-SA 3.0
2014-06-30T05:37:19.050Z
2014-06-30T10:06:07.500Z
2017-04-13T12:32:28.117Z
R B
<p>I believe this problem to be NP-Complete, but I'm unable to find any references on possible reductions. Given a weighted graph (either undirected or directed, I cannot find results for either but am interested in both), and vertices s, t, u, find the shortest path from s to t which includes u. To clarify, the path should NOT repeat edges. Hence simply combining the shortest s-u and u-t paths is not valid.</p>

CC BY-SA 3.0
2014-06-30T10:02:39.197Z
This question is duplicate of [this](http://cstheory.stackexchange.com/questions/20185/subgraph-containing-all-nodes-and-edges-that-are-part-of-length-limited-simple-s/21809#21809) one. It's already answered there.
Saeed
<graph-algorithms><shortest-path>
Shortest path hitting a given vertex
Matthew G Dippel
# Shortest path hitting a given vertex

(Asked by: username_0 on 2014-06-30)

I believe this problem to be NP-Complete, but I'm unable to find any references on possible reductions. Given a weighted graph (either undirected or directed, I cannot find results for either but am interested in both), and vertices s, t, u, find the shortest path from s to t which includes u. To clarify, the path should NOT repeat edges. Hence simply combining the shortest s-u and u-t paths is not valid.

**Tags:** graph-algorithms, shortest-path
> **Comments:**
> **username_1**: This question is duplicate of [this](http://cstheory.stackexchange.com/questions/20185/subgraph-containing-all-nodes-and-edges-that-are-part-of-length-limited-simple-s/21809#21809) one. It's already answered there.  

---

## 2 answers

### Answer by username_2 on 2014-06-30. Score: 12

It is NP-complete for directed graphs. Even deciding if there exist a path from $s$ to $t$ using vertex $u$ is NP-complete.

The 2-node disjoint path problem is NP-hard for directed graphs$^1$.

> Given a directed graph $G$ and vertex pairs $(s\_1,t\_1)$ and
> $(s\_2,t\_2)$, does there exist two node disjoint paths that goes from
> $s\_1$ to $t\_1$ and $s\_2$ to $t\_2$?

We can reduce this problem to your problem:
Split each vertex of $G$, so each vertex $v$ in $G$ become $v^-$ and $v^+$, and edge $uv$ become $u^+v^-$, also there are edges $v^-v^+$. Add one new vertex $u$, and edges $t\_1^+u$ and $us\_2^-$. Let this graph be $G'$.

There exist a path from $s\_1^-$ to $t\_2^+$ in $G'$ that uses $u$ if and only if there exist a node disjoint path between $(s\_1,t\_1)$ and $(s\_2,t\_2)$ in $G$.

1. [The directed subgraph homeomorphism problem, Steven Fortune, John Hopcroft, James Wyllie.](http://www.sciencedirect.com/science/article/pii/0304397580900092#)


---

### Answer by username_3 on 2014-06-30. Score: 9

As Chao mentioned, the directed case is known to be NP-hard even for unweighted graphs.
That said, the problem is [fixed parameter tractable with respect to the path length](https://cstheory.stackexchange.com/questions/20137/subgraph-containing-all-nodes-and-edges-that-are-part-of-length-limited-simple-s/21861#21861).

For undirected graphs, you can solve the weighted version of the problem, deterministically, in $O(|E|^2 \log|E|)$ using [minimum cost flow](https://cstheory.stackexchange.com/questions/20185/subgraph-containing-all-nodes-and-edges-that-are-part-of-length-limited-simple-s/21809#21809).


---

