<p>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$.</p>

<blockquote>
  <p>$stSWALK$ is equivalent to metric Traveling Salesman <strong>Path</strong> problem ($MTSPP$).</p>
</blockquote>

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

<p>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$.</p>

<p>Note that If $G$ is planar then $H$ is not necessarily a planar graph.</p>

CC BY-SA 3.0
2012-05-01T06:35:07.020Z
Thanks, your answer is insightful.Has this problem been studied earlier? What about its hardness for grid graphs?
rizwanhudda
CC BY-SA 3.0
2012-05-01T06:07:20.967Z
2012-05-01T06:07:20.967Z
Shiva Kintali
<p>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):</p>

<blockquote>
  <p><strong>Input</strong>: weighted undirected graph G = (V,E), $S \subseteq V$, $ s, t \in V$, $ w : E \mapsto R^+$</p>
  
  <p><strong>Output</strong>: A walk W = $(s,v_1, v_2,..,v_k, t)$ of minimum length such that:</p>
  
  <p>1) $I = \{v_i : i \ge 1 \wedge i \leq k\}$, $S \subseteq I$<br>
  2) $ (s, v_1), (v_k, t) \in E$<br>
  3) $ (v_{i-1}, v_i) \in E$  $\forall i \geq 2,i \leq k$<br>
  4) Length of walk is = $w(s,v_1) + w(v_k,t)$ + $\Sigma_{i=2}^k w(v_{i-1}, v_i)$<br></p>
</blockquote>

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

<p>Thanks,<br>
Rizwan.</p>

CC BY-SA 3.0
2012-05-01T12:43:42.817Z
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
CC BY-SA 3.0
2012-05-01T16:31:39.177Z
I haven't fixed the $v_i$'s. The only restriction is that $S \subseteq I$.
rizwanhudda
<ds.algorithms><graph-algorithms><optimization><time-complexity>
Minimum length walk from s to t covering a subset of vertices
rizwanhudda
# Minimum length walk from s to t covering a subset of vertices

(Asked by: username_0 on 2012-05-01)

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.

**Tags:** ds.algorithms, graph-algorithms, optimization, time-complexity
> **Comments:**
> **username_1**: 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?  
> **username_0**: I haven't fixed the $v_i$'s. The only restriction is that $S \subseteq I$.  

---

## 1 answers

### Answer by username_2 on 2012-05-01. Score: 9 | Accepted answer

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.

> **Comments:**
> **username_0**: Thanks, your answer is insightful.Has this problem been studied earlier? What about its hardness for grid graphs?  

---

