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

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.

• Do you know the order in which the subset of vertices have to be visited? (from your description it seems so since it $v_{i-1}$ seems to be visited before $v_i$) Besides, is it possible in your problems to devise a heuristic to guide the search? – Carlos Linares López May 1 '12 at 12:43
• I haven't fixed the $v_i$'s. The only restriction is that $S \subseteq I$. – rizwanhudda May 1 '12 at 16:31

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.