Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
This question is duplicate of this one. It's already answered there. – Saeed Jun 30 '14 at 10:02

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.
share|cite|improve this answer

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.

For undirected graphs, you can solve the weighted version of the problem, deterministically, in $O(|E|^2 \log|E|)$ using minimum cost flow.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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