Minimum length walk from s to t covering a subset of vertices

Question

I want to find the current literature for the following problem (I have searched on google/asked friends/some Profs didn't get much useful results yet):

Input: weighted undirected graph G = (V,E), $S \subseteq V$, $ s, t \in V$, $ w : E \mapsto R^+$

Output: A walk W = $(s,v_1, v_2,..,v_k, t)$ of minimum length such that:

1) $I = \{v_i : i \ge 1 \wedge i \leq k\}$, $S \subseteq I$
2) $ (s, v_1), (v_k, t) \in E$
3) $ (v_{i-1}, v_i) \in E$ $\forall i \geq 2,i \leq k$
4) Length of walk is = $w(s,v_1) + w(v_k,t)$ + $\Sigma_{i=2}^k w(v_{i-1}, v_i)$

I know this is somewhat related to TSP/Hamiltonian paths but I think that it is significantly different.
I came to investigate this problem because I am thinking about solving this problem in a special
geometric setting. So, It would be helpful If I could get to know the complexity class to which it is known to
belong and any results for planar graphs, grid graphs.

Thanks,
Rizwan.

Answer 1

So you are given a weighted undirected graph $G$. You want to find a shortest walk from $s$ to $t$ such that you visit all the vertices of the set $S$. You may choose to visit vertices in $V \setminus S$. You may visit vertices multiple times. You may use the edges multiple times. Let's call this problem $stSWALK$.

$stSWALK$ is equivalent to metric Traveling Salesman Path problem ($MTSPP$).

It is easy to see that, when $S = V$ then $stSWALK$ is same as $MTSPP$.

You can convert an instance of $stSWALK$ into an instance of $MTSPP$ by simply computing the shortest paths between every pair of vertices in $S$ (and adding the corresponding "new" edges with the weights equal to the lengths of these shortest paths) and then solving $MTSPP$ on the graph induced by $S \cup \{s,t\}$ (lets call this graph $H$). To get a solution to $stSWALK$, we simply expand these newly added edges into their corresponding shortest paths in $G$.

Note that If $G$ is planar then $H$ is not necessarily a planar graph.