15-451 Algorithms 10/31/12 recitation notes * one more example of coding up a problem as an LP. * NP-completeness recap * one more NP-completeness reduction ================================================================= Another example of coding up a problem as an LP =============================================== Let's see if we can code up the shortest-path problem as an LP. Input: directed graph G with lengths on the edges, start s, dest t. Let's have a variable x_e for each edge e, all in [0,1]. (think of x_e=1 meaning we use that edge, and x_e=0 meaning we don't, but of course the LP might assign fractional values) Goal is to minimize sum_e length(e)*x_e, subject to: Sum of x_e out of s equals 1. Sum of x_e into t equals 1. For any vertex v, flow in equals flow out. But what if the LP solver returns fractional values? The claim is that in that case, all paths from s to t that you get by following non-zero x_e's are shortest paths (otherwise you could get a better LP solution by rerouting that flow on the shortest path). OK, so we really coded this problem up as a min-cost flow, but it is interesting to think of it as an LP. We got lucky here that the fractional values didn't hurt us. For other problems (e.g., like the ones we will see in the next lectures like 3SAT and vertex-cover) you can't necessarily convert a fractional solution into an integer one. NP-completeness =============== Problem Q is NP-complete if: (1) Q is in NP, and (2) Q' \leq_p Q for any other Q' in NP. If Q just satisfies (2) then it's called NP-hard. And remember the def of NP: decision problems where at least the YES-instances have short proofs (that can be checked in polynomial-time) that the answer is YES. Formally, we did this in terms of proof-verifiers: Q is in NP if there is a verifier V(I,X) such that: If "I" is a YES-instance, then there exists X such that V(I,X) = YES. If "I" is a NO-instance, then for all X, V(I,X) = NO. and furthermore the length of X and the running time of V are poly in |I|. In the next lecture, we will prove that the 3-SAT problem is NP-complete. For this recitation, let's use that fact to prove that another problem is NP-complete. To do this, we just need to show that (1) the new problem is in NP, and (2) that we can reduce 3SAT to the new problem. I.e., we want to show 3SAT \leq_P New-problem. In particular, we want a way to convert an instance of 3SAT into an instance of the new problem such that the resulting instance is a YES-instance of the new problem iff the original instance was a YES-instance of 3SAT (so if we had an alg for the new problem, it would give us an alg for 3SAT). Specifically, let's look at the following problem. SET-SPLITTING: Given a collection of sets over n points {1,2,...,n}, is it possible to color the points red or blue so that each set gets at least one point of each color? [Can everyone see why this is in NP?] [Also recap the 3SAT problem if needed] OK, let's do the reduction: Given a 3-SAT formula F, create a SET-SPLITTING instance as follows: - one point for each variable x_i and one point for each "not(x_i)". - for each i, make the set {x_i, not(x_i)}. This will force them to be different colors. (One color will represent "true" and the other will represent "false". - one additional point "f" whose color we will interpret as "false". - then, for each clause c in the given 3-SAT formula, we create a set of size 4 containing the literals in c plus the point f. Claim 1: if the 3-SAT formula was satisfiable then the set-splitting instance is solvable too. Proof: use the two colors "true" and "false". Color each literal according to the setting of some satisfying assignment, and color "f" false. Each set has at least one true and at least one false (namely f) so it's a yes-instance too. Claim 2: vice-versa. Just interpret the color of f as false and the other color as true and read off the colors as the assignment. Each clause must have at least one literal set to true, and we never set literals inconsistently because of the sets {x_i, not(x_i)}