CSEP 590BSpring Quarter 2006Assignment 5Due Thursday May 4, 2006All solutions should be neatly written or type set. All major steps in proofs and algorithms must bejustified.1. (10 points) In this problem you will explore the connection between “optimization problems” and “de-cision problems”. In an optimization problem, given an input, the output is some object that minimizesor maximizes some quantity. As an example, we have the famous Traveling Salesman Problem (TSP):Input: An undirected graph G with weighted edgesOutput: A tour of the graph with total minimim weight. That is, a path through the graph thatvisits each vertex exactly once and returns to the beginning such that the sum of theweights of the edges on the path is minimized.The complexity theory that we are studying is mostly about decision problems (or equivalently lan-guages). A decision problem is one that has a simple yes or no answer which can be defined by aproperty. The TSP problem above has an corresponding decision problem (DTSP):Input: An undirected graph G with non-negative weighted edges, and a number WProperty: The graph contains a tour with total weight bounded above by W .It is clear that TSP is at least as hard as DTSP in the sense that if one has an algorithm for TSP thenit can be used to solve the DTSP as follows. Given a graph G and number W , use the algorithm forTSP on the graph G to compute a minumum weight tour. Compute the weight W0of the tour found. IfW0≤ W then answer yes to the DTSP problem, else answer no. In some sense DTSP is polynomialtime reducible to TSP because the time to solve DTSP given an oracle for TSP is polynomial. Sincewe know that DTSP is NP-complete, then we say that T SP is NP-hard.Consider the following optimization problem called Maximum CutInput: An undirected graph G = (V, E) with non-negative weighted edgesOutput: A set U ⊆ V which maximizes the sum of the weights of the edges from vertices in Uto vertices in V − U .(a) Design a decision problem for Maximum Cut.(b) Show that your decision problem is polynomial time reducible to the optimization problem, Max-imum Cut.(c) Give a polynomial time verifier for the Maximum Cut decision problem.(d) It is known that the Maximum Cut decision problem is NP-complete, what conclusion can youmake about the optimization problem.12. (10 points) It is well known that the Subset Sum problem is NP-complete (cf. 268-270 of Sipser). TheSubset Sum problem is defined by.Input: A sequence of numbers a1, a2, . . . , anand a number b all written in binary.Property: There is a set S ⊆ {1, 2, . . . , n} such thatPi∈Sai= b.Show that the Equal Partition problem is NP-complete where it is defined by:Input: A sequence of numbers c1, c2, . . . , cnall written in binary.Property: There is a set S ⊆ {1, 2, . . . , n} such thatPi∈Sci=Pj6∈Scj.Part of your proof should be the construction of a polynomial time reduction of Subset Sum to
View Full Document
Unlocking...