Source code online books for professionals by professionals

v and v’, keeping all in-edges pointing to v and all out-edges starting at v’. If the original graph had a Hamilton cycle, the 
transformed one will have a Hamilton path starting at v’ and ending at v (we’ve basically just snipped the cycle at v, 
making a path). Conversely, if the new graph has a Hamilton path, it must start at v’ (because it has no in-edges), and, 
similarly, it must end at v. By merging these nodes back together, we get a valid Hamilton cycle in the original graph.
Note
 
■
   the “Conversely …” part of the previous paragraph ensures we have implication in both directions. this is 
important, so that both “yes” and “no” answers are correct when using the reduction. this does not, however, mean that  
I have reduced in both directions.
Now, perhaps you’re starting to see the problem with the longest path problem, which I’ve mentioned a couple 
of times. The thing is, finding the longest path between two nodes will let you check for the presence of a Hamilton 
path! You might have to use every pair of nodes as end points in your search, but that’s just a quadratic factor—the 
reduction is still polynomial. As we’ve seen, whether the graph is directed or not doesn’t matter, and adding weights 
simply generalizes the problem. (See Exercise 11-11 for the acyclic case.)
What about the shortest path? In the general case, finding the shortest path is exactly equivalent to finding the 
longest path. You just need to negate all the edge weights. However, when we disallow negative cycles in the shortest 
path problem, that’s like disallowing positive cycles in the longest path problem. In both cases, our reductions break 
down (Exercise 11-12), and we no longer know whether these problems are NP-hard. (In fact, we strongly believe 
they’re not because we can solve them in polynomial time.)
Note
 
■
   When I say we disallow negative cycles, I mean in the graph. there’s no specific ban on negative cycles in the 
paths themselves because they are assumed to be simple paths and therefore cannot contain any cycles at all, negative 
or otherwise.
Now, finally, I’m getting to the great (or, by now, perhaps not so great) mystery of why it was so hard to find an 
optimal tour of Sweden. As mentioned, we’re dealing with the traveling salesman problem, or TSP. There are a few 
variations of this problem (most of which are also NP-hard), but I’ll start with the most straightforward one, where you 
have a weighted undirected graph, and you want to find a route through all the nodes, so that the weight sum of the 
route is as small as possible. In effect, what we’re trying to do is finding the cheapest Hamilton cycle—and if we’re able 
to find that, we’ve also determined that there is a Hamilton cycle. In other words, TSP is just as hard.

---

Chapter 11 
■
 hard problems and (lImIted) sloppIness
244