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?

  • $\begingroup$ What do you mean by a tour? A path that visits all vertices? Is the target to find a tour with minimum distance? $\endgroup$ – 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.

Thus, there is a trivial reduction (namely the identity) from Metric-TSP to your variant. As Metric-TSP is NP-complete and your variant is in NP, your variant is also NP-Complete.


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.