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.

  • $\begingroup$ So this reduces this problem to the traveling salesman problem. But I need to reduce the traveling salesman problem to this one, and not the other way around right? $\endgroup$ May 27 '21 at 14:16
  • 1
    $\begingroup$ 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$. $\endgroup$
    – nir shahar
    May 27 '21 at 14:17
  • 1
    $\begingroup$ Oh I see... I misunderstood the definition then. Yes, it is confusing. Let me think about this for a moment. Thanks! $\endgroup$ May 27 '21 at 14:22
  • $\begingroup$ Can you point out where can I find a definition of "reduction" in this sense? I am using the book "Combinatorial optimization" by Korte and Vygen, I am not able to decipher this sense of reduction from there. Thanks!! $\endgroup$ May 27 '21 at 14:33
  • $\begingroup$ Taken from cs.stackexchange.com/a/1249/126979: " To reduce problem X (the one you know is NP-hard) to problem Y (the one you're trying to prove is NP-hard, you need to describe an algorithm that transforms an arbitrary instance of X into a legal instance of Y. " is it that the "into a legal instance of Y" means "any legal instance of Y"? $\endgroup$ May 27 '21 at 14:48

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.