November 26 * Reduction Here is a famous reduction graph SATISFIABILITY | | | v 3SAT / \ / \ / \ v v 3DM CLIQUE | /\ | / \ | / \ v v v PARTITION HC VC | | | v TSP * HC is polynomial-time reducible <=P to TSP Given graph G = (V,E) Transformation f outputs complete graph with vertices V. Weights of edges = 1 if e in E |v| + 1 if e not in E Function also outputs number |v|. There exists a TSP tour in this complete graph of size <= |v| iff there exists HC in original graph. The function f is clearly implementable in polynomial time. * Cook's Theorem Cook's theorem states and proves that any NP problem can be polynomial-time reduced to a SAT problem. This SAT is NP-Complete SAT is in NP All problems in NP can be polynomial-time reduced to SAT * Proving that problems are in NP-Complete Because we know that there are some problems to which all problems in NP can be reduced in polynomial time, we do not have to show this for each new problem we want to show is NP-Complete. Procedure for problem Q: 1) Show Q is in NP 2) Select known NPC problem Q' 3) Construct a function f:Q'->Q 4) Show f is polynomial For example, we know every problem in NP <=P SAT. If we show SAT <=P 3SAT, then by transitivity of <=P, every problem in NP <=P 3SAT There are many known NP-complete problems. See Garey and Johnson. Until proven, many people have been frustrated trying to design algorithms to solve these problems. * Examples - CLIQUE is NP-Complete Given graph G = (V,E), find largest subset V' <= V s.t. forall u,v in V', (u,v) in E CLIQUE = {: G is a graph with a clique of size k} Show sample page 188 1) To show CLIQUE in NP, we use set V' of vertices as a certificate. Verifying is polynomial time, check whether for every pair u,v in V', the edge is in E (|V'|^2 pairs). 2) 3SAT <=P CLIQUE Start with instance of 3SAT. Let f = C1 & C2 & ... & Ck be 3CNF with k clauses. For r = 1,2,...,k, each clauses has three distinct literals l1^r, l2^r, l3^r. Construct a graph G s.t. f is satisfiable iff G has a clique of size k. For each Cr in f, put triple of vertices v1^r, v2^r, v3^r in V. Add edge (vi^r vj^s) if (1) vi^r and rj^s are in different triples (r neq s), and (2) their corresponding literals are consistent (li^r is not the negation of lj^s). This graph is constructed in polynomial time. If f = (x1 v -x2 v -x3) ^ (-x1 v x2 v x3) ^ (x1 v x2 v x3) then graph G is show picture page 948 of CLR. Is this a reduction? Suppose f has a satisfying assignment. Then each clause Cr contains at least on eliteral li^r that is assigned 1, and each such literals cooresponds to a vertex vi^r. Picking one such "true" literal from each clause yields a set V' of k vertices. Is V' a clique? For any two vertices vi^r, vj^s, r neq s, the corresponding literals are mapped to 1 by the satisfying assignment and thus the literals cannot be complements. By the construct of G, the edge (vi^r vj^s) belongs in E. Proving the other direction, if G has a clique V' of size k, no edges in G connect vertices in the same tripe, so V' contains exactly one vertex per triple. Assign to each literal li^r s.t. vi^r in V' without fear of assignment 1 to a literal and its complement. Each clause is satisfied, and f is satisfied. - VERTEX COVER is NP-Complete VC: Given graph G = (V,E), find the smallest subset V' <= V s.t. each edge used in G is incident to some vertex in V'. VC = { , k}: G = (V,E) is a graph, and there exists a subset V' <= V s.t. |V'| <= k and forall e in E, e contains some element of V' as one of its endpoints.} Show picture on page 186. 1) Given graph G = (V,E) and an integer k, witness is vertex cover V'. Verify that |V'| = k (1 step) and then check for each edge (u,v) in E, whether u in V' or v in V' (linear in number of edges). 2) CLIQUE <=P VC. Given G = (V,E), define "complement" of G as G com = (V, E com), where E com = {(u,v): (u,v) not in E). The reduction algorithm computes complement of G in polynomial time. The output is the instance of VC. G has a clique of size k iff G com has a vertex cover of size |V| - k. If G has clique V' <= V, |V'| = k, let (u,v) be any edge in E com. Then (u,v) not in E, so at least one of u or v does not belong to V'. Equivalently, at least one of u or v is in V - V', which means (u,v) is covered by V - V'. Every edge of E com is thus covered by a vertex in V - V', so V - V' is a vertex cover for G com. Proving the other direction, suppose that G com has VC V' <= V, |V'| = |V|-k. Forall u,v in V, if (u,v) in E com, then u in V' or v in V' or both. Thus forall u,v in V, if u not in V' and v not in V', then (u,v) in E. Thus V - V' is a clique and has size |V| - |V'| = k. - PARTITION is NP-complete Skip proof for now. Given a finite set A and a "size" s(a) in N+ for each a in A, find a subset A' <= A s.t. sum over a in A' of s(a) = sum over a in A-A' of s(a) PARTITION = { , s(a)): there exists subset A' of A such that the sum of the two subsets is equal} For example, if A = {a=1,b=2,c=3,d=4,e=5,f=7,g=8}, then one possible subset is A' = {a,b,c,d,e} and A - A' = {f,g}. - KNAPSACK is NP-Complete Given a finite set U, a "size" s(u) in N+ and a "value" v(u) in N+ for each u in U, a size constraint B in N+, and a value goal K in Z+, is there a subset U' <= U s.t. sum of sizes in U' is <=B and sum of values in U' is >=K? This can be seen as a knapsack, which has a size limit for the objects. The goal is to pick a collection of objects that will fit in the knapsack and whose total value is at least K (K is input). KNAPSACK = {(U,s,v,B,K): there exists subset U' of U s.t. the sum of s values is at most B, and the sum of v values is at least K} 1) KNAPSACK in NP Given a subset, in linear time compute sum of sizes and in linear time compute sum of value. In constant time see if sums fit limits. 2) PARTITION <=P KNAPSACK This is a different and value approach. We restrict KNAPSACK in a way that makes it polynomial-time reducible (in fact equal) to PARTITION. We are still showing KNAPSACK is at least as hard as PARTITION, which is our goal. We can restrict KNAPSACK to equal PARTITION by only allowing instances in which s(u) = v(u) for all u in U and B = K = 1/2*(sum over u in U of s(u)).