Re: TSP Path: NOT Tour

yangshengwen@xxxxxxxxx wrote: 
It's easy to understand that Traveling Salesman Tour Problem is NPC (By
reduction from Hamiltonian Cycle). But how to understand that a
Traveling Salesman Path Problem is also NPC? Here, Tour means that the
salesman must return to the staring city, Path means that the salesman
will not return to the staring city, but just visiting each city once
and only once.

It sounds like a homework problem so i will only sketch out the basics of it.

Essentially you can reduce an instance of traveling salesman tour problem down to an instance of traveling salesman path easily. Think about what modifications you could make to a graph to enforce a TSP and then think how if you were looking for a tour how many such subgraphs you'd have to explore to find a path that be converted into a tour by adding an edge.
.