Algorithm Design and Analysis December 5, 2008Pennsylvania State University CSE 565, Fall 2008Adam Smith Handout 15Homework 12 – Due Friday, December 12, 2008Please refer to the general information handout for the full homework policy and options.Reminders• Your solutions are due before the lecture. Late homework will not b e acc epted.• Collaboration is permitted, but you must write the solutions by yourself without assistance,and be ready to explain them orally to a member of the course staff if asked. You must alsoidentify your collaborators. Getting solutions from outside sources such as the Web or studentsnot enrolled in the class is strictly forbidden.• To facilitate grading, pleas e write down your solution to each problem on a separate sheet ofpaper. Make sure to include all identifying information and your collaborators on each sheet.Your solutions to different problems will be graded separately, possibly by different people, andreturned to you independently of each other.• For problems that require you to provide an algorithm, you must give a precise description ofthe algorithm, together with a proof of correctness and an analysis of its running time.You may use algorithms from class as subroutines. You may also use any facts that we provedin class or from the bo ok.Reminder To show that a problem is NP-complete, you must show both that it is in NP and thatit is NP-hard. The easiest way to show that problem X is NP-hard is to prove Y ≤p,KarpX (“there isa Karp reduction from Y to X ” or “Y Karp-reduces to X”), where Y is an NP-hard problem alreadycovered in class.Problems to be handed inPage limits: The answer to each problem should fit in 2 pages (or one double-sided sheet) ofpaper. Longer answers will be penalized.1. You are faced with a new decision problem, code-named X by the secretive government organi-zation for which you are consulting. For each of the following statements, say whether it is (i)true, (ii) false, or (iii) unknown given the current state-of-the-art. For example, the statementP = NP falls into category (iii).Justify your answers briefly (one sentence).(a) If X ≤p,KarpSAT , then X ∈ N P .(b) If X ≤p,CookSAT , then X ∈ N P .(c) If X Karp-reduces to SAT and X is in NP, then X is N P -complete.(d) If SAT ≤p,KarpX and X is in NP, then X is N P -complete.(Continued on next page.)1(e) If X is NP-complete, then X Karp-reduces to perfect bipartite matching.(f) If X is NP-complete, then perfect bipartite matching Karp-reduces to X.2. We saw in class that 3-SAT is NP-complete. Consider instead 2-SAT, in which the input isa formula with at most 2 literals per clause. Show that 2-SAT is in P. (Hint: Reduce to theproblem of testing whether a given graph is bipartite, discussed in Sec tion 3.4.)3. KT book, Chapter 8, problem 8 (Madison’s letters). You can reduce from 3-dimensional match-ing, defined in Sec. 8.6 (although a reduction from any NP-complete problem discussed in thebook will