# CSE 6311 Spring 2009 ADVANCED COMPUTATIONAL MODELS AND CSE 6311 Spring 2009 ADVANCED COMPUTATIONAL MODELS AND ALGORITHMS Lecture Notes Feb. 3, 2009 Instructor: Dr. Gautam Das notes by Walter Wilson Some NP-Complete problems: SAT, 3SAT, CLIQUE, VERTEX COVER, MAX INDEP SET SAT - Satisfiability:

Inputs: a) n Boolean variables: v1,..,vn b) Boolean formula variables & operators (and &, or |, not ~) Example: (v1 | ~v2) & (~v1 | v2 | v3) Output: Is there a satisfying assignment to the variables? For our example yes: v1=1, v2=0, v3=1 Cook's Theorem (or Cook-Levin Thm) "The complexity of theorem proving

procedures" (1971) SAT is NP-complete: var asmt can be verified in polynomial time Boolean expr satisfied iff nondeterministic Turing machine accepts NP problem Karp - reduction "Reducibility Among Combinatorial Problems" (1972) Proved 21 NP-complete problems 3SAT Inputs:

a) n Boolean variables: v1,..,vn b) 3-CNF (Conjunctive Normal Form) Boolean formula: Conjunction of clauses, each clause a disjunction of 3 literals, each literal a variable or its negation (if clause length = 2, problem is P) (3 is smallest length that is NP) CLIQUE largest complete subgraph Decision problem: Given graph G (n vertices, m edges) and k>0, is there a clique of size >=k? Naive algorithm look at all 2^n vertex subsets

Problem in NP verification of clique is in P Reduce NP-complete problem 3SAT to CLIQUE: Create vertex for each literal of each clause Make edges between vertices of different clauses except for opposite literals Clique of size C exists iff 3SAT formula is satisfiable where C is number of clauses Thus CLIQUE is NP-complete VERTEX COVER Smallest vertex subset that touches all edges

Decision problem: Given graph G (n vertices, m edges) and k>0, is there a cover of size <=k? Reduce CLIQUE to VERTEX COVER: Given Clique inputs G,k compute VC inputs: G' = complement of G (edge (vi,vj) in G' iff not in G) k' = n - k Clique of size k in G iff VC of size k' in G' Example graph: a

c b d g e f Vertex Cover: {a, g, e} MAX INDEP SET Independent Set: vertex subset with no edges within the set

Decision problem: Given graph G and k, is there an independent set of size >=k? Is in NP: easy to verify subset as independent Reduce VERTEX COVER to MAX INDEP SET Given VC inputs G,k compute Max Indep. Set inputs: G' = G k' = n - k VC of size k iff Independent Set of size k' Max Indep Set = {b, c, d, f} for example graph