2
$\begingroup$

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.)

$\endgroup$

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.