# K-fold Traveling salesman problem - A variant of TSP

Consider a weighted graph $K_n$ and where the weights between vertices $i,j$ is $w_{ij}$. Consider a path, $\sigma$, passing through each vertex only once. Here $\sigma_i$ is the vertex in the $(i\%n)^{th}$ step of the path. (For example, $\sigma_{n+1} = \sigma_1$)

Traveling salesman problem (TSP) minimizes the following objective : $$\sum_{i=1}^{n}w_{\sigma_i,\sigma_{i+1}}$$

A variant of TSP, 2-Fold TSP, will additionally consider the weights between the 1-skipped vertices on the path. The objective of a 2-Fold TSP is to minimize

$$\sum_{i=1}^{n}w_{\sigma_i,\sigma_{i+1}}+w_{\sigma_i,\sigma_{i+2}}$$

and similarly the objective of K-fold TSP is to minimize

$$\sum_{i=1}^{n}w_{\sigma_i,\sigma_{i+1}}+w_{\sigma_i,\sigma_{i+2}}+\cdots+w_{\sigma_i,\sigma_{i+k}}$$

Question

1. Can this be reduced to the original TSP?
2. Is there any reference which deals with k-fold TSP? What is the name of this problem in the literature?
3. Any heuristics/approximation algorithms?

There was a paper on the arxive last month, dealing with this generalization of the TSP:

The multi-stripe travelling salesman problem
Eranda Cela, Vladimir Deineko, Gerhard J. Woeginger
(Submitted on 20 Sep 2016)
https://arxiv.org/abs/1609.09796

The problem does not seem to have a particular name in the literature.