15-451 Algorithms 11/06/13
recitation notes
* Go over practice quiz
* NP-completeness of integer programming
* NP-completeness of 3-coloring
=================================================================
* Go over practice quiz.
1(a)(b): max-flow value is 8.
2(a): correct approach is #1.
(b): this is incorrect because it just shows that one way of
solving instances of B is to convert them to instances of A
but maybe there is an easier way of solving B.
(c): Noooooo. This would allow for f that maps everything to the
same YES-instance I' of B. An algorithm that correctly says
that f(I) is a YES-instance of B doesn't tell us anything about
whether or not I is a YES-instance of A.
3(a): True. If the given instance is a YES-instance of set-cover,
then there exist k sets S_i_1,...,S_i_k that cover all the points.
Setting x_i_j=1 for j=1,2,...,k and setting x_i=0 for every other i
will satisfy the constraints of the LP and have score k. So, the
OPTIMAL LP score cannot be any larger.
(b): False. Consider 6 points 1,2,3,4,5,6 and 6 sets: {1,2},
{2,3}, {1,3}, {4,5}, {5,6}, {4,6}, and consider k=3. By
setting each x_i = 1/2 we get a solution to the LP of score 3.
(This is a legal solution because every point is
double-covered by sets of value 1/2). But you need 4 sets to
cover all the points, so this is a NO-instance of Set-Cover.
(c): False. Consider 4 points 1,2,3,4 and four sets {1,2,3},
{1,2,4}, {1,3,4}, {2,3,4}. One LP solution (which in fact is
optimal) is to set each x_i = 1/3. In this case, taking all
sets i such that x_i >= 1/2 doesn't cover any points.
NP-COMPLETENESS OF INTEGER PROGRAMMING
--------------------------------------
Integer linear programming (ILP) is like linear programming, with the
additional constraint that all variables must take on integral values.
The decision version of integer programming asks whether or not there
exists a point satisfying all the constraints (for the decision
version there is no objective function).
Claim: ILP is NP-complete.
Proof:
(1) ILP is in NP.
(2) We can reduce 3SAT to ILP:
Let the variables in the 3SAT formula be x_1, x_2, ..., x_n. We will
have corresponding variables z_1, z_2, ..., z_n in our integer linear
program. First, restrict each variable to be 0 or 1:
0 <= z_i <= 1 for all i
Assigning z_i=1 in the integer program represents setting x_i=true in
the formula, and assigning z_i=0 represents setting x_i=false.
For each clause like (x_1 OR not(x_2) OR x_3), have a constraint like:
z_1 + (1-z_2) + z_3 >= 1.
To satisfy this inequality we must either set z_1=1 or z_2=0 or z_3=1,
which means we either set x_1=true or x_2=false or x_3=true in the
corresponding truth assignment. More generally, for each clause
in the 3SAT instance, we create the constraint that the sum of literals,
using z_i to represent x_i and (1-z_i) to represent NOT(x_i), is
at least 1.
If the given instance I was a YES-instance of 3SAT then f(I) is
a YES-instance for ILP: just take a satisfying assignment A to the
variables x_i and set each z_i to 0 or 1 accordingly. Since A
satisfied at least one literal in each clause, this means the associated
sum is >= 1. In the other direction, any solution to the ILP must set
at least one of the associated literals to 1, since each is an
integer 0 or 1.
NP-COMPLETENESS OF 3-COLORING
=============================
Let's prove that 3-Coloring is NP-complete using the fact that 3-SAT
is NP-complete.
This reduction is a little trickier. 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.