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)}