I want to show a polynomial reduction from TSP to Metric TSP. I know the rule is: $(G, k) \in TSP \iff (G', k') \in MTSP$ where $G$ is some graph, and $k$ is some bound. It seems like whatever I map $G$ to, the way I map $k$ to $k'$ should make it such that if $k$ is the length of the minimum path, $k'$ is also the length of the minimum path.

For example: Let's say $(G,11) \in TSP$ and 11 is the length of the minimum path. I have some method of changing my graph to $G'$ that involves shrinking a bunch of edges, but $k$ is kept the same. Now, the minimum path in $G'$ is 10. Then it would be the case that $(G, 10) \notin TSP$ but $(G', 10) \in MTSP$--so that wouldn't be an appropriate reduction. It would be the case similarly if I embiggened many edges in $G$ to $G'$, so that the minimum path was now larger.

Thoughts: it's simple if I just multiply every edge cost by a given number, to multiply $k$ by that much as well (this won't yield a metric graph, though). If I don't multiply every edge, then I have no idea how to change $k$ because I don't know whether edges I changed are in the Hamiltonian cycle. I thought about making every edge cost 1 (or 1's and 2's), but again I wouldn't know how to change $k$.

Any hints on what I should be doing to change the edge costs in such a way that I also know how to change $k$? (This is homework, so I don't want a complete solution, please.)


Your Answer

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

Browse other questions tagged or ask your own question.