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.