Finding the Shortest Path that connects k nodes in a graph

Question

I was wondering if there are algorithms for finding the shortest path that contains some selected $k$ nodes in a weighted graph. More specifically, the path that we are looking for needs to pass through all the $k$ nodes, but can contain other nodes from the graph and can visit those $k$ nodes in any order. In addition, any node can be traversed more than once. Also, the path has to start and end with two distinct nodes from the given set of $k$ nodes. For example, if $k=2$, we have two nodes, $u_1$ and $u_2$, and are looking for the shortest path from $u_1$ to $u_2$. We can use UCS or $A^*$ to solve this. If $k=3$, there will be three nodes: $u_1$, $u_2$, and $u_3$. The path can start in $u_1$, pass through $u_2$, and finish in $u_3$, or start in $u_2$, pass through $u_1$, and end in $u_3$, etc. $k$ can take any value from $2$ to $n$, $n$ being the total number of nodes in the graph.

To me, this somewhat looks like a problem of finding the minimal tree whose leaves are those $k$ nodes. A path passing through the leaves could then be obtained by traversing the tree in an appropriate order.

Answer 1

The state of a traversal at any point will be (a) the node you're currently at, and (b) the subset of the $k$ selected nodes you've already passed through. Thus, you can solve this problem by constructing a new graph $G'$ that is $2^k$ times as large as the original graph $G$, and then finding the shortest path in $G'$.

In particular, each vertex of $G'$ has the form $(v,S)$ where $v \in V$ and $S$ is a subset of the $k$ selected nodes; for each edge $v \to w$ in the original graph, $G$' has the edge $(v,S) \to (w,S)$ (if $w$ is not one of the selected $k$) or $(v,S) \to (w,S\cup \{w\})$ (if $w$ is one of the selected $k$).

Unfortunately the running time of this algorithm is exponential in $k$. I don't expect there to be a polynomial-time solution; David Richerby explains why not.

Answer 2

A tree which includes all the vertices in your set of "interesting" vertices is a Steiner tree. Finding minimum-weight Steiner trees is NP-hard.

Note that any tree necessarily has at least two leaves, and every leaf is necessarily an "interesting vertex", since any leaf that isn't interesting doesn't help to connect the interesting vertices, so can be deleted to make a lower-weight tree that still connects the things that need to be connected. This means that you can definitely find a traversal of the tree that starts and ends at leaves and visits every vertex. However, there may be "interesting" vertices in the interior of the tree. For example, if the original graph is a tree and every vertex is interesting, the minimum-weight Steiner tree is, of course, the whole graph.

However, the minimum-weight walk that visits every interesting vertex is not necessarily a traversal of a Steiner tree. Suppose, for example, that you have vertices 1-4 and edges 12, 13, 14 of weight 1 and 23 of weight 1.5. The minimum-weight walk is 4123, with weight 3.5, but the minimum Steiner tree is the weight-1 edges and any traversal of that (e.g., 41213) has weight 4.