Solutions to NP-Completeness Homework Problems

Problem 1: Partition-P&N

Reminder: The point of homework in this course is to learn by doing. You will not learn this material by copying the solution from somewhere else so don’t waste your time looking for solutions. DO consult the textbook and the lecture notes. You may discuss the homework with other students if you get stuck, but you must write up solutions yourself. Do NOT exchange written material by you or anyone else with other students. Otherwise you may be commiting plagiarism and subject to academic penalty. These questions are copyrighted by the professor and cannot be shared outside the class without permission. Solutions are graded for correctness and clarity. If you write ”No answer” for a question or subpart of a question, you will receive 20% credit for recognizing that you don’t know the answer. Due Sunday November 28. Late assignments due Monday Nov 29 with 15% penalty. (1) Partition-P&N Input: a set of integers {s1, s2, ..., sn} at least one of which is negative and one of which is positive. Output: Yes iff the integers can be partitioned into two sets, each of which sums to the same number We wish to give a reduction from PARTITION-P&N to PARTITION with only positive integers. i. Prof V says: f first determines m, the smallest (negative) number in the input and then f maps each si to si + |m|. (NOTE: I corrected this to add an extra 1; ok if they didn’t catch this and ended up with a 0 number. ) ii. Prof B says: g maps each number si to its absolute value, |si|. a) For each of f and g, prove that this is a reduction, or give a counterexample to show it isn’t. b) Using PARTITION, prove that PARTITION-P&N is NP-complete. (2) 3SAT-5 Input: a Boolean formula in CNF with exactly 3 literals per clause Output: Yes iff there are at least five satisfying truth assignments Prove that 3-SAT-5 is NP Complete. (3) The HAMILTONIAN PATH PROBLEM is defined on page 11 in Lecture 15. Use the fact that HAMILTONIAN PATH is NP-complete to show the following prob- lem is NP-complete. 1 2  Input: A directed graph G = (V, E) Output: Yes iff there is a directed cycle in which every node appears exactly once. The next questions use the following problem: k-COLOUR PROBLEM Input: a graph G = (V, E) Output: Yes iff there is a way to colour each node {1, 2., , k} so that no two nodes which are endpoints of the same edge have the same colour. (4) Give a polynomial time reduction from 2-COLOUR to 3-COLOUR and prove it is correct. Does this prove 2-COLOUR is NP-Complete? Why not? (5) Show that k-COLOUR is NP-Complete for any k > 2, using the fact that 3- COLOUR is NP-complete. (6) We’re having a party with k people and we want to do a play reading for a play that has n > k roles. Can we give a proper assignment of roles to people, i.e., so that each role is assigned to exactly one person, and there is no scene in which two or more characters in the same scene are assigned to the same person? k-ROLE-PLAY Input: A play with n roles r1, r2, ..., rn, k people p1, p2, ..., pk to enact it, and s1, s2, ..., sm scenes. Output: Yes, iff there is proper assignment of roles to people. Show this problem is NP-complete using k-COLOUR. Hint: Your play may need to have a lot of scenes