15-451 Algorithms 11/07/12 recitation notes * Practice quiz * More NP-completeness examples ================================================================= PRACTICE QUIZ ============= -> see handout NP-COMPLETENESS OF 3-COLORING ============================= Here is a trickier reduction, to show that 3-coloring is NP-complete by reduction from 3SAT. Want to convert 3-CNF formula \phi to a graph G that is 3-colorable iff \phi was satisfiable. First, for each x_i, will have one node called "x_i" and one node called "not(x_i)". Let's call the three colors "red", "T" and "F", and add three special nodes in a triangle called "red", "T", and "F" that we can assume without loss of generality are given the corresponding colors. Now, let's have a triangle between red, x_i, and not(x_i) for each i. This forces the coloring to make a choice for each variable of whether it should be true or false. Now, we need to add in a "gadget" for each clause. For a clause "(x OR y or z)" we will have the gadget: x---O |\ | O---O |/ |\ y---O | T (this is the common "T" node) |/ z---------O This gadget has the property that it's not possible to color all three of x,y,z with color "F", but *any* other assignment of {T,F} to x,y,z is OK. [this is easiest to see looking at the triangle attached to x,y. If both x,y are F, then the tip of that triangle has to be F too, else it can be colored T.] So, if the formula was satisfiable then there is a legal 3-coloring, and any legal 3-coloring must give a satisfyting assignment to the formula.