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.