Unformatted text preview:

11/21/2008 A. Smith; based on slides by S. Raskhodnikova and K. Wayne Adam Smith Algorithm Design and Analysis LECTURE 30 Computational Intractability •Polynomial Time ReductionsPolynomial-Time Reduction Purpose. Classify problems according to relative difficulty. Design algorithms. If X  P Y and Y can be solved in polynomial-time, then X can also be solved in polynomial time. Establish intractability. If X  P Y and X cannot be solved in polynomial-time, then Y cannot be solved in polynomial time. Establish equivalence. If X  P Y and Y  P X, we use notation X  P Y. up to cost of reductionSimplifying Assumption: Decision Problems Search problem. Find some structure. Example. Find a minimum cut. Decision problem.  X is a set of strings.  Instance: string s.  If x X, x is a YES instance; if x X is a NO instance.  Algorithm A solves problem X: A(s) = yes iff s  X. Example. Does there exist a cut of size  k? Self-reducibility. Search problem  P, Cook decision version.  Applies to all (NP-complete) problems in this chapter.  Justifies our focus on decision problems.Polynomial Transformation Def. Problem X polynomial reduces (Cook) to problem Y if arbitrary instances of problem X can be solved using:  Polynomial number of standard computational steps, plus  Polynomial number of calls to oracle that solves problem Y. Def. Problem X polynomial transforms (Karp) to problem Y if given any input x to X, we can construct an input y such that x is a yes instance of X iff y is a yes instance of Y. Note. Polynomial transformation is polynomial reduction with just one call to oracle for Y, exactly at the end of the algorithm for X. Open question. Are these two concepts the same? we require |y| to be of size polynomial in |x| Caution: KT abuses notation  p and blurs distinctionReduction By Simple Equivalence Basic reduction strategies.  Reduction by simple equivalence.  Reduction from special case to general case.  Reduction by encoding with gadgets.Independent Set INDEPENDENT SET: Given a graph G = (V, E) and an integer k, is there a subset of vertices S  V such that |S|  k, and for each edge at most one of its endpoints is in S? Ex. Is there an independent set of size  6? Yes. Ex. Is there an independent set of size  7? No. independent setVertex Cover VERTEX COVER: Given a graph G = (V, E) and an integer k, is there a subset of vertices S  V such that |S|  k, and for each edge, at least one of its endpoints is in S? Ex. Is there a vertex cover of size  4? Yes. Ex. Is there a vertex cover of size  3? No. vertex coverVertex Cover and Independent Set Claim. VERTEX-COVER P INDEPENDENT-SET. Pf. We show S is an independent set iff V - S is a vertex cover. vertex cover independent setVertex Cover and Independent Set Claim. VERTEX-COVER P INDEPENDENT-SET. Pf. We show S is an independent set iff V - S is a vertex cover.   Let S be any independent set.  Consider an arbitrary edge (u, v).  S independent  u  S or v  S  u  V - S or v  V - S.  Thus, V - S covers (u, v).  Let V - S be any vertex cover.  Consider two nodes u  S and v  S.  Observe that (u, v)  E since V - S is a vertex cover.  Thus, no two nodes in S are joined by an edge  S independent set. Reduction from Special Case to General Case Basic reduction strategies.  Reduction by simple equivalence.  Reduction from special case to general case.  Reduction by encoding with gadgets.Set Cover SET COVER: Given a set U of n elements, a collection S1, S2, . . . , Sm of subsets of U, and an integer k, does there exist a collection of  k of these sets whose union is equal to U? Sample application.  m available pieces of software.  Set U of n capabilities that we would like our system to have.  The ith piece of software provides the set Si  U of capabilities.  Goal: achieve all n capabilities using fewest pieces of software. Ex: U = { 1, 2, 3, 4, 5, 6, 7 } k = 2 S1 = {3, 7} S4 = {2, 4} S2 = {3, 4, 5, 6} S5 = {5} S3 = {1} S6 = {1, 2, 6, 7}SET COVER U = { 1, 2, 3, 4, 5, 6, 7 } k = 2 Sa = {3, 7} Sb = {2, 4} Sc = {3, 4, 5, 6} Sd = {5} Se = {1} Sf= {1, 2, 6, 7} Vertex Cover Reduces to Set Cover Claim. VERTEX-COVER  P SET-COVER. Pf. Given a VERTEX-COVER instance G = (V, E), k, we construct a set cover instance whose size equals the size of the vertex cover instance. Reduction: On input < G = (V, E), k>  Output SET-COVER instance: – k = k, U = E, Sv = {e  E : e incident to v } Correctness claim:  Set-cover of size  k iff vertex cover of size  k.  a d b e f c VERTEX COVER k = 2 e1 e2 e3 e5 e4 e6 e7Reductions by Encoding with Gadgets Basic reduction strategies.  Reduction by simple equivalence.  Reduction from special case to general case.  Reduction by encoding with gadgets.Ex: Yes: x1 = true, x2 = true x3 = false. Literal: A Boolean variable or its negation. Clause: A disjunction (OR) of literals. Conjunctive normal form: A propositional formula  that is the conjunction (AND) of clauses. SAT: Given CNF formula , does it have a satisfying truth assignment? 3-SAT: SAT where each clause contains exactly 3 literals. Satisfiability each corresponds to a different variable3 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. Reduction: On input <  >,  Let G contain 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.  k = || \\ k=# of clauses in   Output <G, k> k = 3 G3 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.  k = 3 G and any other variables in a consistent


View Full Document

PSU CSE 565 - Computational Intractability

Download Computational Intractability
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Computational Intractability and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Computational Intractability 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?