Graph coloring Mapmakers try to use as few colors as

Chapter 34, Problem 34-3

(choose chapter or problem)

Graph coloring Mapmakers try to use as few colors as possible when coloring countries on a map, as long as no two countries that share a border have the same color. We can model this problem with an undirected graph G D .V; E/ in which each vertex represents a country and vertices whose respective countries share a border are adjacent. Then, a k-coloring is a function c W V ! f1; 2; : : : ; kg such that c.u/ c./ for every edge .u; / 2 E. In other words, the numbers 1; 2; : : : ; k represent the k colors, and adjacent vertices must have different colors. The graph-coloring problem is to determine the minimum number of colors needed to color a given graph. a. Give an efficient algorithm to determine a 2-coloring of a graph, if one exists. b. Cast the graph-coloring problem as a decision problem. Show that your decision problem is solvable in polynomial time if and only if the graph-coloring problem is solvable in polynomial time. c. Let the language 3-COLOR be the set of graphs that can be 3-colored. Show that if 3-COLOR is NP-complete, then your decision problem from part (b) is NP-complete. To prove that 3-COLOR is NP-complete, we use a reduction from 3-CNF-SAT. Given a formula of m clauses on n variables x1, x2,..., xn, we construct a graph G D .V; E/ as follows. The set V consists of a vertex for each variable, a vertex for the negation of each variable, 5 vertices for each clause, and 3 special vertices: TRUE, FALSE, and RED. The edges of the graph are of two types: literal edges that are independent of the clauses and clause edges that depend on the clauses. The literal edges form a triangle on the special vertices and also form a triangle on xi, :xi, and RED for i D 1; 2; : : : ; n. d. Argue that in any 3-coloring c of a graph containing the literal edges, exactly one of a variable and its negation is colored c.TRUE/ and the other is colored c.FALSE/. Argue that for any truth assignment for , there exists a 3-coloring of the graph containing just the literal edges. The widget shown in Figure 34.20 helps to enforce the condition corresponding to a clause .x _ y _ /. Each clause requires a unique copy of the 5 vertices that are heavily shaded in the figure; they connect as shown to the literals of the clause and the special vertex TRUE. e. Argue that if each of x, y, and is colored c.TRUE/ or c.FALSE/, then the widget is 3-colorable if and only if at least one of x, y, or is colored c.TRUE/. f. Complete the proof that 3-COLOR is NP-complete. x y z TRUE Figure 34.20 The widget corresponding to a clause .x _ y _ /, used in 34-3.