NP-Complete Problems

Design and Analysis of Algorithms Massachusetts Institute of Technology Profs. Erik Demaine, Srini Devadas and Nancy Lynch April 10, 2015 6.046J/18.410J Recitation 8 NP-Complete Problems 1 Definitions P: The set of all decision problems D for which there exists a polynomial time algorithm A such that A(x) = D(x). We consider a polynomial time algorithm to be “efficient”. NP: The set of all decision problems D for which there exists a polynomial time verification algorithm V such that for all inputs x, D(x) = 1 if and only if there exists a polynomial-length “certificate” y such that V (x, y) = T rue. In order to compare the “hardness” of solving different problems, we use reductions! The idea is that if I have two problems A and B, if I can show that I can solve A by using a black box that solves B, then I can understand the difficulty of solving A in terms of the difficulty of solving B plus the work required to transform a solution of B to the solution of A. “Karp”-Reduction: Let A : X → {0, 1} and B : Y → {0, 1} be decision problems. A is polytime reducible to B, or “A reduces to B” (A ∝ B), if there exists a function R : X → Y that transforms inputs to A into inputs to B such that A(x) = B(R(x)). The following picture shows how this reduction leads to an algorithm for A which simply builds upon the algorithm for B. Solving A is no harder than solving B. In other words, if solving B is “easy” (i.e. B ∈ P ), then solving A is easy (A ∈ P ). Equivalently, if A is “hard”, then B is “hard”. Given an algorithm for B, we can easily construct an algorithm for A. NP-Hard: A decision problem D is NP-Hard if all problems Q in NP are polynomial time re­ ducible to it (Q ∝ D for all Q ∈ N P ). That is, given an efficient algorithm which solves an NP-Hard problem D, we can construct an efficient algorithm for any problem in NP. NP-Complete: A decision problem D is NP-Complete if it is in NP and is NP-Hard. 2 Recitation 8: NP-Complete Problems 2 Reducing Hamiltonian Cycle to Hamiltonian Path Hamiltonian Cycle: Given a directed graph G = (V, E), is there a cycle that visits every vertex exactly once? Hamiltonian Path Given a directed graph G = (V, E), is there a path that visits every vertex exactly once? Given that Hamiltonian Cycle is NP-Complete, we prove that Hamiltonian Path is NP-Complete. 1. Show Hamiltonian Path is ∈ NP To prove this, we need to prove that there exists a verifier V(x, y). Let x = G be a “yes” input. Let y be a path P that satisfies the condition. We can verify that the path traverses every vertex exactly once, then check the path to ensure that every edge in the path is an edge in the graph. Naively, it takes O(n2 ) to check that every vertex is traversed exactly once and O(nm) to check that every edge in the path is in the graph. 2. Show Hamiltonian Path is ∈ NP-Hard. We prove this by giving a Karp-reduction of Hamiltonian Cycle to Hamiltonian Path. (a) Given an instance of Hamiltonian Cycle G, choose an arbitrary node v and split it into two nodes v " and v "" . All directed edges into v now have v " as an endpoint, and all edges leaving v leave v "" instead. We call this new graph G" . The transformation takes at most O(E). (b) If there is a Hamiltonian Cycle in G, there is a Hamiltonian Path on G" . We can use the edges of the cycle on G as the path on G" , but our path must begin on v "" and end on v " . (c) If there is a Hamiltonian Path on on G" , there is a Hamiltonian Cycle on G. The path must begin at v "" and end at v " , since there are no edges into v "" or out of v " . Thus we can use the path on G" as a cycle on G once v " and v "" are remerged. 3. This proves Hamiltonian Cycle reduces to Hamiltonian Path in polynomial time, which means that Hamiltonian Path is at least as hard as Hamiltonian Cycle, so Hamiltonian Path is NP-Complete. Recitation 8: NP-Complete Problems 3 3 Reducing 3 Dimensional Matching to 4 Partition 3DM: Given 3 disjoint sets X, Y, Z, which each contain n elements, and triples T ⊂ X × Y × Z, is there a a subset S ⊂ T such that each element a ∈ X ∪ Y ∪ Z is in exactly one s ∈ S. n 4-Partition: Given n integers 1 , a2 , . . . , an } is there a partition into 4 subsets of 4 elements e {a each with the same sum t = A/ n4 . Each integer ai ∈ ( 5t , 3t ) (which ensures that each subset has exactly 4 elements). Given that 3DM is NP-Complete, we prove that 4-Partition is NP-Complete. 1. Show 4-Partition ∈ NP We can verify a potential solution by checking that the elements in each partition sum to t, and that no element is used more than once. This takes at most O(n2 ) naively. 2. Show 4-Partition ∈ NP We prove this by giving a Karp-reduction of 3DM to 4-Partition. (a) Givene an input X, Y, Z and triples T to 3DM, we create numbers in base r, where r = 100 ∗ (X ∪ Y ∪ Z). We note that N [xi ] denotes the number of times an element xi appears in a triple in T. Then we create the ”actual” numbers as part of our set of n integers. i. For every element xi ∈ X: 10r4 + ir3 + 1 ii. For every element yj ∈ Y : 10r4 + jr2 + 2 iii. For every element zk ∈ Z: 10r4 + kr + 4 We also add the following ”dummy” numbers to our set of n integers. i. For every element xi ∈ X: N [xi ] − 1 copies of the number 11r4 + ir3 + 1 ii. For every element yj ∈ Y : N [yj ] − 1 copies of the number 11r4 + jr2 + 2 iii. For every element zk ∈ z: N [zk ] − 1 copies of the number 8r4 + kr + 4 Finally, we add a ”triple” number for each triple in T . i. For every triple (xi , yj , zk ): 10r4 − ir3 − jr2 − kr + 8 We set our target sum t = 40r4 +15, which can be achieved by adding a ”triple element” 10r4 − ir3 − jr2 − kr + 8 with three ”actual elements” or a ”triple element” with three ”dummy elements”. Additionally, we have chosen r sufficiently large that no other combination of ”actual”, ”dummy”, or ”triple” elements will meet the target sum. (b) If S ⊂ T is a solution to 3DM, we can construct a 4 Partition solution. For every triple (xi , yj , zk ) = s ∈ S, we create a 4 element set out of the corresponding ”triple element” and the three ”actual elements” corresponding to xi , yj , zk which will sum to 40r4 + 15. The remaining matchings will correspond to partitions with a ”triple” element and three ”dummy” elements corresponding to xi , yj , zk which will still sum to 40r4 + 15. Thus we can form sets of 4 elements, and we have a 4 Partition. 4 Recitation 8: NP-Complete Problems (c) Suppose we are given a solution to 4 Partition. Then consider any 4 element set in this 4 Partition. By considering the the sum of the element sizes modulo r, r2 , r3 , r4 , andr5 we show that this set contains one element corresponding to each of the members in a triple, and that all three elements are either ”actual” elements or ”dummy” elements. If the triple contains only ”actual elements”, it is part of the 3DM solution S ⊂ T , otherwise it is not. If B equals the sum of the four elements, we know that B mod r = 15. This is possible only if the 4 elements correspond to a triple element, and one element each from X, Y, and Z. The sum B mod r2 = 0r + 15, which is possible only if the triple element and the dummy or actual element for zk match, ensuring that we use a triple element and the corresponding zk element in our set. The sum B mod r3 = 0r2 + 15, which is possible only if the triple element and the dummy or actual element for yj match, ensuring that we use a triple element and the corresponding yj element in our set. The sum B mod r4 = 0r3 + 15, which is possible only if the triple element and the dummy or actual element for xi match, ensuring that we use a triple element and a xi element in our set. The sum B mod r5 = 40r4 + 15, which is possible only if the triple element and only three dummy elments or three actual elements were used. Thus, we can guarantee that if we have a 4 Partition, each set in the partition corre­ sponds to a 3DM matching in S or an unused matching. 3. This proves 3DM reduces to 4-Partition in polynomial time, which means that 4-Partition is at least as hard as 3DM, so 4-Partition is NP-hard. Recitation 8: NP-Complete Problems 5 4 Reducing Clique to Independent Set Clique: Given graph G = (V, E) and integer k, is there a set of vertices C ⊆ V with |C| = k that form a complete graph? Independent Set: Given graph G = (V, E) and integer k, is there a set of vertices I ⊆ V with |I| = k such that for any u, v ∈ I, (u, v) ∈ / E? Given that Clique is NP-Complete, we prove that Independent Set is NP-complete. 1. Show Independent Set ∈ NP To prove this, we need to prove there exists a verifier V(x, y). Let x = (G, k) be a “yes” input. Let y be I that satisfies the condition. It takes O(|I|) to check that |I| = k. It takes O(|I|2 ) to check that for every u, v ∈ V " , (u, v) ∈ / E. This checks in polynomial time that the certificate y proves that x is a valid input. Therefore, Independent Set is in NP. 2. Show Independent Set ∈ NP-hard We prove this by giving a Karp-reduction of Clique to Independent Set. (a) Given an input x = (G, k) to Clique, create input G" which has the same vertices, but has edge (u, v) if and only if (u, v) ∈ / E. This takes O(|E|) time, so this reduction takes polynomial time. (b) If I is a set of vertices that form a k-Independent Set for G" , then C = I is a k-Clique for G because for u, v ∈ I, Independent Set says that (u, v) ∈ / E " , but this implies that (u, v) ∈ E for the Clique problem due to the method of construction. This shows that there are edges between every pair of nodes in C. In addition |C| = k, and so C is a k-clique. (c) If C is a set of vertices that form a k-Clique in G, then I = C is a k-Independent set for G" . This is because u, v ∈ C implies that (u, v) ∈ E for Clique, and this implies that (u, v) ∈ / E " for Independent Set. Since |I| = |C| = k, this shows that there are k elements in the construction G" that are not adjacent to each other. 3. This proves Clique reduces to Independent Set in polynomial time, which means that Inde­ pendent Set is at least as hard as Clique, so k-Independent Set is NP-hard. 6 Recitation 8: NP-Complete Problems 5 Reducing Vertex Cover to Set Cover Vertex Cover: Given graph G = (V, E) and integer k, does there exist Y ⊆ V such that |Y | = k and for each (u, v) ∈ E, either u ∈ Y or v ∈ Y (or both)? Set Cover: Given a set S of n elements {1, 2, . . . , n} and m sets S1 , . . . , Sm where Si ⊆ S, does there exist a set of k sets Si1 , . . . , Sik such that Si1 ∪ · · · ∪ Sik = S? Given that Vertex Cover is NP-complete, we prove that Set Cover is NP-Complete. 1. Show Set Cover ∈ NP: To prove this, we need to prove there exists a verifier V(x, y). Let x = S, S1 , . . . , Sm be a “yes” input. Let y be Si1 , . . . , Sik that satisfies the condition. In O(k) time, we can figure whether or not we have exactly k sets. In O(kn) time we can determine whether or not all all elements in S is in the union. This proves we have a polynomial time verifier, which means that Set Cover is in NP. 2. Show Set Cover ∈ NP-Hard: To prove this, we reduce Vertex Cover to Set Cover. (a) For an input x = (G, k) to Vertex Cover, we make R(x) = S, S1 , . . . , Sm . Let S be the set of all edges ej ∈ E. For each vi ∈ V , create set Si . This set contains the set of edges ej that touch vi . This new input is polynomial because |S| = |E| and each set Si has size at most |E| and there are |V | sets. (b) If there is a k-Vertex Cover, there is a k-Set Cover. If the vertex vi ∈ V " is part of the vertex cover, then Si is part of the set cover. Since every edge ej ∈ E is incident to some vertex vi ∈ V " , this means that every element ej ∈ S is covered the set Si . (c) If there is a k-Set Cover, there is a k-Vertex Cover. If Si is in the set cover, choose vi to be in the vertex cover. Every element ej is contained in some set Si . By construction, this means every edge ej is incident to the vertex vi that got chosen. Since there are k sets, there will be k vertices chosen for the vertex cover. Recitation 8: NP-Complete Problems 7 6 Prove Max2SAT is NP-Complete: Reducing from Clique Clique(G, k): Given graph G = (V, E) and integer k, is there a set of vertices U ⊆ V with |U | ≥ k that form a complete graph (k-clique)? Max2SAT(C, X, k): Given a CNF formula consisting of clauses C = {c1 , c2 , . . . cn } and lit­ erals X = {x1 , x2 , . . . xk } such that each clause involves exactly two literals, does there exist an assignment of TRUE/FALSE to the literals such that at least k clauses are satisfied? 6.1 Show Max2SAT ∈ NP To prove this, we need to prove there exists a polytime verifier. Given any “yes” input (CNF formula), the “witness/certificate” is an assignment of TRUE/FAlSE to the literals that satisfies at least k clauses. A polytime verifier can simple evaluate each clause of the CNF formula given the assignment, and verify that at least k of them are satisfied. 6.2 Show Max2SAT ∈ NP-Hard: 1. To prove this, we reduce Clique to Max2SAT. Given an input (G, k) to Clique, we will create an input (C, X, k " ) to Max2SAT such that “yes” instances of Clique map to “yes” instances of Max2SAT, and “no” instances of Clique map to “no” instances of Max2SAT. (a) In designing the CNF formula, we use literals x1 , x2 , . . . xn to represent the n vertices in the graph. We want to design clauses that act as constraints to enforce that x1 = TRUE corresponds to vertex 1 being chosen in the clique. (b) Recall that a set of vertices U is a clique if for all i, j ∈ U , (i, j) ∈ E. Equivalently (by the contrapositive), U is a clique if for all i, j ∈ V such that (i, j) ∈ / E, either i ∈ / U or j∈ / U . We will use these constraints to design the clauses in our CNF formula. (c) Therefore, for every “non-edge” (i, j) ∈ / E, we have a clause (¬xi ∨ ¬xj ). This means that for every non-edge, at least one of the endpoints must not be in the clique. (d) However, these clauses could also be satisfied by setting all literals xi to FALSE. In order to encourage choosing cliques with more vertices, for every vertex i we introduce the clauses (xi ∨ z) ∧ (xi ∧ ¬z), where z is a new literal. In order to satisfy these two clauses, xi must be true. (e) Choose k " = number of non-edges + |V | + k. Therefore, the input to Max2SAT is defined by • literals X = V ∪ {z}, • clauses C = {(¬xi ∨¬xj ) for all non-edges (i, j)}∪{(xi ∨z)∧(xi ∧¬z) for all vertices i}, • and k " = |non-edges| + |V | + k. 8 Recitation 8: NP-Complete Problems 2. Show that if Clique is “yes”, then Max2SAT is “yes”. Given a clique U ⊆ V in graph G such that |U | ≥ k, we can use an assigment such that for all i ∈ U , xi is TRUE, for all i∈ / U , xi is FALSE, and z is TRUE. This is an assigment that satisfies at least k " clauses in our CNF formula. First, for all non-edges (i, j), the clause (¬xi ∨ ¬xj ) is satisfied because U is a clique. For all i ∈ U , both (xi ∨ z) and (xi ∧ ¬z) are satisfied. For all ı ∈ / U , (xi ∨ z) is satisfied while (xi ∧ ¬z) is not satisfied. Therefore, the number of satisfied clauses is |non-edges| + 2|U | + |V \ U | = |non-edges| + |V | + |U | ≥ k " . 3. Show that if Max2SAT is ”yes, then Clique is “yes”. Given an assignment for the literals X such that at least k " clauses are satisfied, we will show that we can find a k-clique in the original graph. If for all (i, j) ∈ / E, (¬xi ∨ ¬xj ) is satisfied, then the literals that are set to TRUE form a clique in graph G that has size ≥ k (by construction). However, if the current assignment does not correspond to a clique, then we will show that we can modify the assigment to find a clique of size at least k. For every clause (¬xi ∨ ¬xj ) that is not satisfied, we change xi to FALSE (doesn’t matter which one we pick), thus satisfying this clause. This will cause one of (xi ∨ z) or (xi ∧ ¬z) to become not satisfied. In addition, xi may also appear in other “non-edges” clause. Therefore, the net change is that the number of clauses satisfied can only increase or stay the same by this modification. We continue to choose unsatisfied “non-edge” clauses and modifying the assignment in this way until all the “non-edge” clauses are satisfied. Note that the number of unsatisfied “non-edge” clauses is monotonically decreasing in each modification. Therefore, we obtain an assignment which corresponds to a clique (since all “non-edge” clauses are satisfied). In addition the clique has size at least k because the number of satisfied clauses is still at least k " , since every modification does not decrease the number of satisfied clauses.