PROOF: Evidently, NC is in MP. Guess a set of к nodes, and check that each edge of G has at least one end in the set.

To complete the proof, we shall reduce IS to NC. The idea, which is suggested by Fig. 10.8, is that the complement of an independent set is a node cover. For instance, the set of nodes that do not have boldface outlines in Fig. 10.8 form a node cover. Since the boldface nodes are in fact a maximal independent set, the other nodes form a minimal node cover.

The reduction is as follows. Let G with lower limit к be an instance of the independent-set problem. If G has n nodes, let G with upper limit n - it be the instance of the node-cover problem we construct. Evidently this transformation can be accomplished in linear time. We claim that

G has an independent set of size fc if and only if G has a node cover of size n - k.

(If) Let N be the set of nodes of G, and let С be the node cover of size n - k. We claim that iV - G is an independent set. Suppose not; that is, there is a pair of nodes v and w in N - С that has an edge between them in G. Then since neither v nor w is in C, the edge (v, w) in G is not covered by the alleged node cover C. We have proved by contradiction that iV - G is an independent set. Evidently, this set has к nodes, so this direction of the proof is complete.

(Only-if) Suppose / is an independent set of к nodes. We claim that N ~ I is a node cover with n - к nodes. Again, we proceed by contradiction. If there is some edge (w, w) not covered by N - I, then both v and w are in 7, yet are connected by an edge, which contradicts the definition of an independent set. □

10.4.4 The Directed Hamilton-Circuit Problem

We would like to show NP-complete the Traveling Salesman Problem (TSP), because this problem is one of great interest in combinatorics. The best known proof of its NP-completeness is actually a proof that a simpler problem, called the Hamilton-Circuit Problem (HC) is NP-complete. The Hamilton-Circuit Problem can be described as follows:

PROBLEM: Hamilton-Circuit Problem.

INPUT: An undirected graph G.

OUTPUT: Yes if and only if G has a Hamilton circuit, that is, a cycle that passes through each node of G exactly once.

Notice that the HC problem is a special case of the TSP, in which all the weights on the edges are 1. Thus, a polynomial-time reduction of HC to TSP is very simple: just add a weight of 1 to the specification of each edge in the graph.

The proof of NP-completeness for HC is very hard. Our approach is to introduce a more constrained version of HC, in which the edges have directions

(i.e., they are directed edges, or arcs), and the Hamilton circuit is required to follow arcs in the proper direction. We reduce 3SAT to this directed version of the HC problem, then reduce it to the standard, or undirected, version of HC. Formally;

PROBLEM: The Directed Hamilton-Chcuit Problem (DHC). INPUT: A directed Graph G.

OUTPUT: Yes if and only if there is a directed cycle in G that passes through each node exactly once.

REDUCTION FROM: 3SAT.

Theorem 10.21: The Directed Hamilton-Circuit Problem is NP-complete.

PROOF: The proof that DHC is in AfP is easy; guess a cycle and check that all the arcs It needs are present in the graph. We must reduce 3SAT to DHC, and this reduction requires the construction of a complicated graph, with gadgets, or specialized subgraphs, representing each variable and each clause of the 3SAT instance.

To begin the construction of a DHC instance ftrom a 3-CNF boolean expression, let the expression be E - e-i A A A ej., where each is a clause, the sum of three literals, say e,- = {ац + aj2 + otis)- Let xi,X2,. ,Xn be the variables of E. For each clause and for each variable, we construct a gadget, suggested in Fig. 10.9.

For each variable Xi we construct a subgraph Lfj with the structure shown in Fig. 10.9(a). Here, mi is the larger of the number of occurrences of Xi and the number of occurrences of xJ in E. In the two columns of nodes, the bs and the es, there are arcs between bj and Cij in both directions. Also, each of the bs has an arc to the с below it; i.e., bij has an arc to cj+i, as long as j < m;. Likewise, dj has an arc to for j < т. Finally, there is a head node

with arcs to both 6 о and cjo, and a foot node di, with arcs from bimt and Cjm;-

Figure 10.9(b) outlines the structure of the entire graph. Each hexagon represents one of the gadgets for a V8iriable, with the structure of Fig. 10.9(a). The foot node of one gadget has an arc to the head node of the next gadget, in a cycle.

Suppose we had a directed Hamilton circuit for the graph of Fig. 10.9(b). We may as well suppose the cycle starts at ai. If it next goes to Ью, we claim it must then go to do, for if not, then сю could never appear on the cycle. In proof, note that if the cycle goes from ai to Ью to сц, then as both predecessors of cio (that is, ao aud Ью) are already on the cycle, the cycle can never include

Thus, if the cycle begins ai,bio, then it must continue down the ladder, alternating between the sides, as

ai,blo,Cjo,bn,Cii,...,£ imi,Cimi,rfl

Figure 10.9: Constructions used in the proof that the Hamilton-circuit problem is NP-complete