# Shortest directed path connecting given subset of vertices

Given

• weighted directed graph $G = (V,E,w)$, where $w : E \to \mathbb R^+$
• source vertex $v \in V$
• vertex subset $U \subset V$

how to find a shortest directed path from $v$ containing all vertices from $U$? Note that such path may contain vertices that are not in $U$.

1. Does such problem have a name?
2. How to find a solution?

## 1 Answer

This problem is NP-complete, by reduction from Hamiltonian path. Given an instance $G=(V,E)$ of Hamiltonian path, add a new vertex $s$ connected to all original vertices; this edges are directed from $s$, and all the original graph edges are bidirectional. Give all edges unit weight. There is a path from $s$ visiting all of $V$ of weight $|V|$ if and only if $G$ has a Hamiltonian path.

• The question asks not for complexity of the problem, but for known names. – Raphael Apr 14 '14 at 18:16
• @Raphael I'm actually interested both in an algorithm and in the name. I made it more clear in the question. – Jakub Stejskal Apr 14 '14 at 18:29