# Variant of TSP: allow each vertex to be visited at most twice

We are given a finite set $$V$$ and a set of distance $$d : V\times V \rightarrow R\ge 0$$ and we wish to compute a tour. Suppose we allow each vertex to be visited at most twice in the tour. How can we prove this is NP complete?

• What do you mean by a tour? A path that visits all vertices? Is the target to find a tour with minimum distance? – xskxzr Aug 27 '19 at 7:27

Let $$T = (V,d,k)$$ be an instance of Metric-TSP, where $$V$$ is a vertex set, $$d: V\times V \rightarrow \mathbb{R}_{\geq 0}$$ is a distance with triangle inequality, and $$k\in \mathbb{R}_{\geq 0}$$.
Suppose that $$T$$ is a positive instance of Metric-TSP (i.e. there exists a tour with total length $$\leq k$$. Then $$T$$ is also a positive instance for your variant (just take the same tour).
Suppose $$T$$ is a positive instance of your variant, and let $$t = (v_1, v_2,\ldots,v_r)$$ denote a "tour" with total length $$\leq k$$. Whenever there is a vertex $$v$$ which appears twice in $$t$$ one can safely delete one of the two appearances as every vertex will still be visited and by the triangle inequality the total length of $$t$$ can only decrease. Once you have deleted all the duplicates, you are thus left with a tour of length $$\leq k$$, which shows that $$T$$ is also a positive instance of Metric-TSP.