I want to find the current literature for the following problem (I have searchedon 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 tobelong and any results for planar graphs, grid graphs.Thanks,Rizwan.
Minimum length walk from s to t covering a subset of vertices
ds.algorithms;graph algorithms;optimization;time complexity
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.