<p>This problem is PSPACE-complete even in the case in which the edge weights obey the triangle inequality. See</p>

<ul>
<li>Hsi-Ming Ho, Joel Ouaknine, <em><a href="http://arxiv.org/abs/1411.2874" rel="nofollow">The Cyclic-Routing UAV Problem is PSPACE-Complete</a></em>, FoSSaCS 2015</li>
</ul>

CC BY-SA 3.0
2015-04-13T12:51:31.473Z
2015-04-13T12:51:31.473Z
Radu GRIGore
<p>Can you please suggest possible approaches for the following problem: </p>

<p>Find a path through graph vertices so that the distance (sum of edges weights) between two vertex $i$ occurrences would be no more than $D_i$. It is obviously infinite, so I want to have a generator for this path. </p>

<p>Thanks in advance.</p>

CC BY-SA 3.0
2012-08-05T18:52:28.063Z
We have studied an online version of the problem (in a geometric setting): http://www.cs.helsinki.fi/u/josuomel/publications/algosensors-2008-backlog-paper.html
Jukka Suomela
CC BY-SA 3.0
2016-08-14T18:36:18.430Z
@Jukka, the page is not accessible.
Saeed
CC BY-SA 3.0
2016-08-14T19:41:50.730Z
Here is a new link that should work: https://users.ics.aalto.fi/suomela/minimum-backlog/
Jukka Suomela
<ds.algorithms><graph-theory><tsp>
TSP with multiple visits
Goldwin_es
# TSP with multiple visits

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

Can you please suggest possible approaches for the following problem:

Find a path through graph vertices so that the distance (sum of edges weights) between two vertex $i$ occurrences would be no more than $D\_i$. It is obviously infinite, so I want to have a generator for this path.

Thanks in advance.

**Tags:** ds.algorithms, graph-theory, tsp

> **Comments:**
> **username_1**: We have studied an online version of the problem (in a geometric setting): http://www.cs.helsinki.fi/u/josuomel/publications/algosensors-2008-backlog-paper.html  
> **username_2**: @Jukka, the page is not accessible.  
> **username_1**: Here is a new link that should work: https://users.ics.aalto.fi/suomela/minimum-backlog/  

---

## 1 answers

### Answer by username_3 on 2015-04-13. Score: 2

This problem is PSPACE-complete even in the case in which the edge weights obey the triangle inequality. See

* Hsi-Ming Ho, Joel Ouaknine, *[The Cyclic-Routing UAV Problem is PSPACE-Complete](http://arxiv.org/abs/1411.2874)*, FoSSaCS 2015


---

