Additional NP-complete problemsWhy we want to see more NP-completeness proofsThe NP-completeness of CLIQUEThe VERTEX-COVER problem definedThe NP-completeness of VERTEX-COVER (a)The NP-completeness of VERTEX-COVER (b)The NP-completeness of VERTEX-COVER (c)The NP-completeness of VERTEX-COVER (d)The NP-completeness of VERTEX-COVER (e)The NP-completeness of HAMPATH (a)The NP-completeness of HAMPATH (b)The NP-completeness of HAMPATH (c)The NP-completeness of HAMPATH (d)The NP-completeness of HAMPATH (e)Slide 15The NP-completeness of UHAMPATHThe NP-completeness of SUBSET-SUM (a)The NP-completeness of SUBSET-SUM (b)The NP-completeness of SUBSET-SUM (c)The NP-completeness of SUBSET-SUM (d)Additional NP-complete Additional NP-complete problemsproblemsSection 7.5 Giorgi Japaridze Theory of ComputabilityWhy we want to see more NP-completeness proofs 7.5.aGiorgi Japaridze Theory of Computability For reasons that are not well understood, most naturally occurring NP-problems are known to be either in P or to be NP-complete (the graph isomorphism problem being one notable exception; so was the COMPOSITES problem until a few years ago). So, if you seek a polynomial time algorithm for a new NP-problem, spending part of your effort attempting to prove it NP-complete issensible because doing so may prevent you from wasting time. This explains why we want to exercise more with NP-completeness proofs. Such proofs usually proceed by finding a polynomial reduction from an already known NP-complete language, most typically from 3SAT. When doing so, we look for structures in the language under question that can simulate the variables and clauses of Boolean formulas. For example, when reducing 3SAT to CLIQUE, variables were simulated by vertices, and clauses by triples. Such structures areoften called gadgets.The NP-completeness of CLIQUE 7.5.bGiorgi Japaridze Theory of ComputabilityCorollary 7.43 CLIQUE is NP-complete.Proof. As was already (easily) observed, CLIQUE is in NP. Next, Theorem 7.32 showed that 3SAT is polynomial time reducibleto CLIQUE. In turn, by Corollary 7.42, 3SAT is NP-complete.But Theorem 7.36 says that if an NP-complete language is polynomialtime reducible to an NP-language C, then C is NP-complete.Hence CLIQUE is NP-complete.The VERTEX-COVER problem defined 7.5.cGiorgi Japaridze Theory of ComputabilityIf G is an undirected graph, a vertex cover of G is a subset of the nodes where every edgeof G touches (at least) one of those nodes. 1 2 3 4GVERTEX-COVER = = {<G,k> | G is an undirected graph that has a k-node vertex cover}<G,4>  VERTEX-COVER?<G,3>  VERTEX-COVER?<G,2>  VERTEX-COVER?<G,1>  VERTEX-COVER?The NP-completeness of VERTEX-COVER (a)7.5.dGiorgi Japaridze Theory of ComputabilityTheorem 7.44 VERTEX-COVER is NP-complete.Proof. Obviously VERTEX-COVERNP (why?). Next, we are going to set up a polynomial time reduction from 3SAT to this language. It maps a 3cnf-formula  to a graph G and a value k, such that  is satisfiable iff G has a vertex cover of size k. For each variable x in , we produce a horizontal edge connecting twonodes. We label the two nodes in this gadget x and x. Setting x to beTRUE is going to correspond to selecting the left node for the vertex cover, and setting it to be FALSE correspond to selecting the right node. For example, when  = (x  x  z)  (x  z  z)  (x  z  z),the reduction produces the following two variable gadgets:xx zzThe NP-completeness of VERTEX-COVER (b)7.5.eGiorgi Japaridze Theory of Computability = (x  x  z)  (x  z  z)  (x  z  z)xx zz Next, for each clause, we produce a triangle of (interconnected) nodes,each node of a triangle labeled with the corresponding literal of the corresponding clause. These triangles are clause gadgets.zxxzzxzzx Finally, we connect each variable-gadget node to each clause-gadgetnode with the identical label.The NP-completeness of VERTEX-COVER (c)7.5.fGiorgi Japaridze Theory of Computability = (x  x  z)  (x  z  z)  (x  z  z)xx zz Thus, G has 2m+3l nodes, where m is the number of variables in  and l is the number of clauses. Let k be m+2l. In the present example, k = 2+(23) = 8.zxxzzxzzxClaim.  is satisfiable iff G has a vertex cover of size k.The NP-completeness of VERTEX-COVER (d)7.5.gGiorgi Japaridze Theory of Computability = (x  x  z)  (x  z  z)  (x  z  z)xx zz Suppose  is satisfiable.zxxzzxzzx Include the variable-gadget nodes corresponding to true literals in the VC. Next, for each clause gadget, select a true-literal-labeled node, andinclude the other two nodes in the VC. We got the total of k nodes. All edges within the variable and clause gadgets are obviously covered. And every intergadget edge is covered either by a (true) variable-gadget node, or by one of the two nodes of the clause gadget that have been included in the vertex cover.The NP-completeness of VERTEX-COVER (e)7.5.hGiorgi Japaridze Theory of Computability = (x  x  z)  (x  z  z)  (x  z  z)xx zz Suppose now G has a VC of size k. Clearly it should include at least one node from each variable gadget and at least two nodes from each clause gadget. zxxzzxzzx As this number sums up to k, those nodes are exactly the nodes of the vertex cover. We take the nodes of the variable gadgets that are in the VC and assign TRUE to the corresponding literals. This assignment satisfies  because, if you take any clause gadget, the node which is not in the VC is (has to be) connected with an edge to a true-literal node of a variable gadget, for otherwise that intergadget edge would not be covered.The NP-completeness of HAMPATH (a)7.5.iGiorgi Japaridze Theory of ComputabilityTheorem 7.46 HAMPATH is NP-complete.Proof. That HAMPATH is in NP has already been shown. Now we set up a polynomial time reduction from 3SAT to HAMPATH. Consider an arbitrary 3cnf-formula  with k clauses:  = (p1  q1  r1)  (p2  q2  r2)  …  (pk  qk  rk)c1 c2 … ckWe assume that  contains l variables x1,…,xl. Each such variable will be represented with a diamond-shaped structure with 3k+5 nodes:…xiAnd each clause will be representedwith a single node:cjThe NP-completeness of HAMPATH