Figure 10.10: Example of the Hamilton-circuit construction

10.4.5 Undirected Hamilton Circuits and the TSP

The proofs that the undirected Hamilton-circuit problem and the TVaveling Salesman problem are also NP-complete are relatively easy. We already saw in Section 10.1.4 that TSP is in AfP. HC is a special case of TSP, so it is also in MP. We must perform the reductions of DHC to HC and HC to TSP.

PROBLEM: Undirected Hamilton-Circuit Problem.

INPUT: An undirected graph G.

OUTPUT: Yes if and only if G has a Hamilton circuit. REDUCTION FROM: DHC.

Theorem 10.23 : HC is NP-complete.

PROOF: We reduce DHC to HC, as follows. Suppose we are given a directed graph С([, The undirected graph we construct will be called Gu- For every node v of Grf, there are three nodes v \ and v in G . The edges of G are;

1. For all nodes v of Gd, there are edges and (uf\u() in G .

2. If there is an arc и -> № in Grf, then there is an edge (иш ) in Gu-Figure 10.11 suggests the pattern of edges, including the edge for an arc v w.

Figure 10.11: Arcs in G arc replaced by edges in Gu that go from rank 2 to rank 0

Clearly the constniction of Gu from Gd can be performed in polynomial time. We must show that

Gu has a Hamilton circuit if and only if Gd has a directed Hamilton circuit.

10.4.6 Summary of NP-Complete Problems

Figure 10.12 indicates all the reductions we have made in this chapter. Notice that we have suggested reductions from all the specific problems, like TSP, to SAT. What happened was that we reduced the language of every polynomial-time, nondeterministic Turing machine to SAT in Theorem 10.9. Without mentioning it explicitly, these TMs included at least one that solves TSP, one that solves IS, and so on. Thus, all the NP-complete problems are polynomial-time reducible to one another, and are, in effect, difierent faces of the same problem.

(If) Suppose Vi,V2y ,Vn,V\ is a directed Hamilton circuit. Then surely

(0) Ji) .,(2) (0) -,(1) (2) (0) (0) (1) (2) (0)

is an undirected Hamilton circuit in Gu- That is, we go down each column, and then jump to the top of the next column to follow an arc of Grf.

{Only if) Observe that each node u of G has only two edges, and therefore must appear in a Hamilton circuit with one of v) and u its immediate predecessor, and the other its immediate successor. Thus, a Hamilton circuit in Gu must have superscripts on its nodes that vary in the pattern 0,1,2,0,1,2,... or its opposite, 2,1,0,2,1,0,.... Since these patterns correspond to traversing a cycle in the two different directions, we may as well assume the pattern is 0,1,2,0,1,2,.,.. Thus, if we look at the edges of the cycle that go from a node with superscript 2 to one with superscript 0, we know that these edges are arcs of Gd, and that each is followed in the direction in which the arc points. Thus, an undirected Hamilton circuit in Gu yields a directed Hamilton circuit in Grf. □

PROBLEM: Traveling Salesman Problem.

INPUT: An undirected graph G with integer weights on the edges, and a limit k.

OUTPUT: Yes if and only if there is a Hamilton circuit of G, such that the sum of the weights on the edges of the cycle is less than or equal to k.

REDUCTION PROM: HC.

Theorem 10.24: The Traveling Salesman Problem is NP-complete.

PROOF: The reduction from HC is as follows. Given a graph G, construct a weighted graph G whose nodes and edges are the same as the edges of G, with a weight of 1 on each edge, and a limit к that is equal to the number of nodes n of G. Then a Hamilton circuit of weight n exists in G if and only if there is a Hamilton circuit in G. □