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.