Polynomial-Time Reduction Basic strategies. Reduction by simple equivalence. Reduction from special case to general case. Reduction by encoding with gadgets. 6
16 Polynomial-Time Reduction Basic strategies. Reduction by simple equivalence. Reduction from special case to general case. Reduction by encoding with gadgets
4.2 Reductions via "Gadgets" Basic reduction strategies. Reduction by simple equivalence. Reduction from special case to general case. Reduction via "gadgets
4.2 Reductions via "Gadgets" Basic reduction strategies. Reduction by simple equivalence. Reduction from special case to general case. Reduction via "gadgets
Satisfiability Literal:A Boolean variable or its negation. Clause:A disjunction of literals. C=x1 V X2 V X3 Conjunctive normal form:A propositional Φ=C1ΛC2ΛC3ΛC4 formula that is the conjunction of clauses. SAT:Given CNF formula does it have a satisfying truth assignment? 3-SAT:SAT where each clause contains exactly 3 literals. each corresponds to a different variable Ex:(V五Vx3)A(V五Vx)A(2V3)A(五V) Yes:X1=true,x2=true x3=false. 18
18 Ex: Yes: x1 = true, x2 = true x3 = false. Literal: A Boolean variable or its negation. Clause: A disjunction of literals. Conjunctive normal form: A propositional formula that is the conjunction of clauses. SAT: Given CNF formula , does it have a satisfying truth assignment? 3-SAT: SAT where each clause contains exactly 3 literals. Satisfiability Cj x1 x2 x3 xi or xi C1 C2 C3 C4 x1 x2 x 3 x1 x2 x 3 x2 x 3 x1 x2 x 3 each corresponds to a different variable
3 Satisfiability Reduces to Independent Set Claim.3-SAT s p INDEPENDENT-SET. Pf.Given an instance of 3-SAT,we construct an instance(G,k)of INDEPENDENT-SET that has an independent set of size k iff is satisfiable. Construction. G contains 3 vertices for each clause,one for each literal. Connect 3 literals in a clause in a triangle. Connect literal to each of its negations. X2 G X3 X1 X3 X2 X4 k=3 Φ=(V为vx)Λ(VVx)Λ(xVV4) 19
19 3 Satisfiability Reduces to Independent Set Claim. 3-SAT P INDEPENDENT-SET. Pf. Given an instance of 3-SAT, we construct an instance (G, k) of INDEPENDENT-SET that has an independent set of size k iff is satisfiable. Construction. G contains 3 vertices for each clause, one for each literal. Connect 3 literals in a clause in a triangle. Connect literal to each of its negations. x2 x1 x2 x 3 x1 x2 x 3 x1 x2 x 4 x3 x1 x1 x2 x4 x 1 x2 x3 k = 3 G
3 Satisfiability Reduces to Independent Set Claim.G contains independent set of size k=iff is satisfiable. Pf.Let S be independent set of size k. S must contain exactly one vertex in each triangle. Set these literals to true.and any other variables in a consistent way Truth assignment is consistent and all clauses are satisfied. Pf Given satisfying assignment,select one true literal from each triangle.This is an independent set of size k. X X2 X1 G X2 x3 X1 X3 X2 X4 k=3 Φ=(V为vx)Λ(VVx)Λ(xV五V4) 20
20 3 Satisfiability Reduces to Independent Set Claim. G contains independent set of size k = || iff is satisfiable. Pf. Let S be independent set of size k. S must contain exactly one vertex in each triangle. Set these literals to true. Truth assignment is consistent and all clauses are satisfied. Pf Given satisfying assignment, select one true literal from each triangle. This is an independent set of size k. ▪ x2 x3 x1 x1 x2 x4 x 1 x2 x3 k = 3 G and any other variables in a consistent way x1 x2 x 3 x1 x2 x 3 x1 x2 x 4