3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Carlos Linares López May 1 '12 at 12:43
  • $\begingroup$ I haven't fixed the $v_i$'s. The only restriction is that $S \subseteq I$. $\endgroup$ – rizwanhudda May 1 '12 at 16:31
9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks, your answer is insightful.Has this problem been studied earlier? What about its hardness for grid graphs? $\endgroup$ – rizwanhudda May 1 '12 at 6:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.