AllofSS-

Figure 10.12: Reductions among NP-complete problems

10.4.7 Exercises for Section 10.4

* Exercise 10.4.1: A k-digue in a graph G is a set of к nodes of G such that there is an edge between every two nodes in the clique. Thus, a 2-clique is just a pair of nodes connected by an edge, and a 3-clique is a triangle. The problem CLIQUE is: given a graph G and a constant k, does G have a fc-clique?

a) What is the largest к for which the graph G of Fig. 10.1 satisfies CLIQUE?

b) How many edges does a fc-clique have, as a function of A?

c) Prove that CLIQUE is NP-complete by reducing the node-cover problem to CLIQUE.

*! Exercise 10,4.2: The coloring problem is: given a graph G and an integer k, is G A:-colorable j that is, can we assign one of к colors to each node of G in such a way that no edge has both of its ends colored with the same color. For

example, the graph of Fig. 10.1 is 3-colorable, .since we can assign nodes 1 and 4 the color red, 2 green, and 3 blue. In general, if a graph has a fc-clique, then it can be no less than fc-colorable, although it might require many more than fc colors.

Figure 10.13: Part of the construction showing the coloring problem to be NP-complete

In this exercise, we shall give part of a construction to show that the coloring problem is NP-complete; you must fill in the rest. The reduction is from 3SAT. Suppose that we have a 3-CNF expression with n variables. The reduction converts this expression into a graph, part of which is shown in Fig. 10.13. There are, as seen on the left, n + l nodes co, ci .., c that form an {n+ 1)-clique. Thus, each of these nodes must be colored with a different color. We should think of the color assigned to Cj as the color Cj.

Also, for each variable Xj, there are two nodes, which we may think of as Xi and ж7. These two are connected by an edge, so they cannot get the same color. Moreover, each of the nodes for Xj are connected to cj for all j other than 0 and i. As a result, one of Xi and Щ must be colored co, and the other is colored c;. Think of the one colored co as true and the other as false. Thus, the coloring chosen corresponds to a truth assignment.

To complete the construction, you need to design a portion of the graph for each clause of the expression. It should be possible to complete the coloring of the graph using only the colors cg through c if and only if eacli clause is made true by the truth assignment corresponding to the choice of colors. Thus, the constructed graph is (n -b l)-colorable if and only if the given expression is satisfiable.

Figure 10.14: A graph

Exercise 10.4.3: A graph does not have to be too large before NP-complete questions about it become very hard to solve by hand. Consider the graph of Fig. 10.14.

* a) Does this graph have a Hamilton circuit?

b) What is the largest independent set?

c) What is the smallest node cover?

d) What is the smallest edge cover (see Exercise 10.4.4(c))?

e) Is the graph 2-colorable?

Exercise 10.4,4: Show the following problems to be NP-complete:

a) The subgraph-isomorphism problem: given graphs Gi and G2, does Gi contain a copy of G2 as a subgraph? That is, can we find a subset of the nodes of Gi that, together with the edges among them in Gi, forms an exact copy of G2 when we choose the correspondence between nodes of G2 and nodes of the subgraph of Gi properly? Hint: Consider a reduction from the clique problem of Exercise 10.4.1.