Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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|improve this question
3  
This question is duplicate of this one. It's already answered there. –  Saeed Jun 30 at 10:02
add comment

2 Answers 2

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|improve this answer
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.