Consider the \"taxi rip-off\' problem (TRO), a decision problem stated as follow

Question

Consider the "taxi rip-off' problem (TRO), a decision problem stated as follows: Given a directed graph G with positive costs along each edge, is there a path from vertex S to vertex D, visiting each vertex exactly once, with a total cost >= C? In other words, we're looking for higher fares so that the customer pays more, not less. Prove that TRO is NP-Complete. Prove by reduction using HAMPATH there are 2 steps to showing that a problem is NP-Complete. First show the problem is in NP by describing a polynomial time verifier. Then use proof by reduction with an existing NP-Complete problem. I recommend using the approach shown in class, where you use one solution to implement the other in modern pseudo-code.

Explanation / Answer

1st Step: Polynomial time verifier

We have such a path from vertex S to vertex D.

We need to check in polynomial time if this path visits each vertex exactly once and has a total cost >=C.

To ensure that each node is visited exactly once we use a visited array to store if a node has already been visited.We also a maintain a variable to store the total cost of the path. We then traverse along the path and for each node check if the node is already vsited. If its already visited then the path given to us is not correct and we stop. Otherwise if the node has not yet been viisited we mark it as visited and add the cost of the edge connecting the current and the previous vertex in path to the total cost variable.

Finally when we have traversed the path we check if the totalcost of the path. If it is greater than C we return true otherwise we conclude that this path is not correct.

We can easily verify that this verifier is polynomial as we only traverse the path in the graph which taken O(L) where L-the length of the path which is V in the worst case.

Second Step:

Reduction to HamPath

Given a graph G, construct a new graph G' (E,V) such that the edge (u,v) in G' is -1 if the edge exists in G and is 0 otherwise. We also add two additional nodes s and t which have an edge of weight -n+1, to all nodes in G.

We solve the TRO problem for the above graph. We foind out a path from s to t such that it has total cost>= -n. If we can find such a path we can solve the HAMPATH problem. As such a path would exist only if a Hamiltonian Path exists in the graph. But since we know HAMPATH is NP-complete. So TRO must also be NP-Complete.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.