# Is this variation of the traveling salesman problem NP-hard

Consider the following setting. You have $$n$$ cities, and there is a cost to travel from a city $$i$$ to a city $$j$$ given by $$c_{ij}>0$$ where $$c_{ij}\neq c_{ji}$$. Moreover, if you are traveling to city $$i$$, you are allowed to stay exactly $$d_i>0$$ days. The problem is:

Find a travel schedule, this is: a number $$m$$ and a sequence of different cities $$i_1,\dots,i_m\in\{1,\dots,n\}$$, such that the cost $$\sum_{k=1}^{m-1} c_{i_k,i_{k+1}}$$ is minimal and that the whole trip lasts at least $$L$$, this is $$\sum_{k=1}^m d_{i_k}\geq L$$.

There are many similarities between this problem and the traveling salesman one. The key differences are the non symmetric costs $$c_{ij}\neq c_{ji}$$ and that instead of having to travel to all cities once, one just needs to travel to enough cities to make the trip last enough.

I understand that to show that this problem is NP-hard, I need to show that another NP-hard problem can be reduced to this one in polynomial time. I suspect that the original traveling salesman problem may work to do so through some clever trick I haven't found yet. Moreover, since there is plenty of literature on the traveling salesman problem, I suspect a similar problem to this may already be shown to be NP-hard.

My question is: Do you see how to show this problem to be NP-hard? Or, do you recognize this problem to be something standard in some piece of literature you can point me out?

I think if you choose all $$d$$'s to be exactly $$1$$ and choose $$L$$ to be exactly $$n$$ (number of cities), any solution must visit all cities, so the reduction will work out.
• The reduction is from the traveling salesman to this problem. I know its sometimes confusing how reductions work :) Take an instance of traveling salesman, and create the instance of this problem with $d=1$ and $L=n$. May 27 '21 at 14:17