0
$\begingroup$

I think the following question is a mix of the Traveling Salesman Problem and the Subset-sum Problem, which makes it really hard (for me) to solve... .

The problem is stated as follows:

There are a total of $n$ cities.

The salesman must start his journey at a certain city, and return to that specific city at the end of his tour.

Whenever the salesman reaches a city he hasn't been to, he can earn $r_i$ dollars there. $r$ is a positive real number, and $i$ denotes the city number.

The salesman can visit the same city more than once, but he cannot earn extra cash there.

The salesman does not have to visit every city.

By traveling from city $i$ to city $j$, a cost of $f_{ij}$ is incurred everytime. $f_{ij}$ is a positive real number. (This is like a negative weighted edge.)

The problem asks whether there exists a route for the salesman to earn a net revenue of at least $k$ dollars.

This problem is clearly in NP, but how should I prove that it is NP-complete?

Since the salesman can wonder around the same cities, can I still map this question to the 3-SAT problem (like the subset-sum case) and prove that it is NPC?

Many thanks.

$\endgroup$
  • $\begingroup$ What have you tried? Where did you get stuck? What other NP-complete problems have you tried reducing from? We expect you to make a serious effort on your own, and show us in the question what you tried and where you got stuck. $\endgroup$ – D.W. Jan 6 '15 at 0:21
2
$\begingroup$

Hint. Reduce Hamiltonian path to this problem. Use the rewards $r_i$ to say that you have to visit each city, use the costs $f_{i,j}$ to say that you can't use more than one edge per city and set the target $k$ to an appropriate value.

$\endgroup$
  • $\begingroup$ Sorry to bother you again, but I don't really get how such a reduction works... . The solution to my problem may not be a cycle at all, it can be a line of cities, with the last city having extremely large revenue, all other non-taken paths having extremely large costs, and all cities not reached having very little revenues. How can a Hamiltonian cycle map to such a solution? $\endgroup$ – user23245 Jan 5 '15 at 14:42
  • 1
    $\begingroup$ The idea is to show that your problem is NP-complete by reducing Hamiltonian path to it (I originally said Hamiltonian cycle, which might be incorrect). That is, you need to show that if you could solve this problem efficiently, you could solve Hamiltonian path efficiently. You need to convert instances of Hamiltonian path into instances of your problem. Thus, you control what the costs and rewards are and can set them to whatever you want to get the job done. $\endgroup$ – David Richerby Jan 5 '15 at 15:21
  • $\begingroup$ So, set the reward high enough that you must visit every city to meet the target. Have the costs low but non-zero so that, even if you do visit every city, using more edges than a path means you can't meet the target. Therefore, any solution corresponds to a Hamiltonian path. $\endgroup$ – David Richerby Jan 5 '15 at 15:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy