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.
$\begingroup$
$\endgroup$
1
-
3$\begingroup$ This question is duplicate of this one. It's already answered there. $\endgroup$– SaeedJun 30, 2014 at 10:02
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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$.
$\begingroup$
$\endgroup$
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.
