World's most popular travel blog for travel bloggers.

[Solved]: A Proof for NP-completeness

, , No Comments
Problem Detail: 

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.

Asked By : yi416

Answered By : David Richerby

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.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback