# A Proof for NP-completeness

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.

• 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. – D.W. Jan 6 '15 at 0:21

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.