Problem 1. [15 points] Recall the Subset Sum problem:
Input: A collection S of positive integers s1,s2,,sm and another positive integer t.
Question: Is there a subcollection of S whose sum is equal to t?
As we said in class, the Subset Sum problem can be solved in pseudopolynomial time, but the problem is NP-complete if the numbers are represented in binary as usual.
Use the NP-completeness of the Subset Sum problem to show the NP-completeness of the following Partition Problem:
Input: A collection S of positive integers s1,s2,,sm
Question: Is there a partition of the collection S into two subcollections S1,S2 (where S1S2 , S1S2 S)whosesumsareequal: si si ?
siS1 siS2
Problem 2. [20 points] Let G=(V,E) be a directed graph (without any self-loops). A kernel of G is a subset K of V such that (1) there is no edge (u,v) with both nodes u,v in K (i.e. K is an independent set of nodes), and (2) for every node vK there is a node uK such that (u,v)E, i.e. every node is either itself in K or has an incoming edge from some node in K. Note that some graphs do not have any kernel.
a. Show that if u,v are two nodes of G such that the graph has both edges (u,v) and (v,u) and there are no other edges entering the nodes u,v, then any kernel of G must include exactly one of the two nodes u,v.
b. Show that if three nodes u,v,w form a cycle u v w u in G, then any kernel of G must contain some node x (distinct from u,v,w) that has an edge to at least one of the three nodes u,v,w.
c. Show that it is NP-complete to determine whether a given directed graph has a kernel. (Hint: You can reduce from 3SAT. You can use parts a and b for you variable and clause gadgets respectively.)
Problem 3. [25 points] In the Steiner Tree problem, we are given a set N={1,…,n} of n cities, a subset MN of mandatory cities (the rest are optional), and the pairwise distances d(i,j)>0, 1≤ i,j ≤n between the cities, which are assumed to be positive integers and symmetric (i.e. d(i,j)=d(j,i) for all i,j). The problem is to find a connected graph H=(V,E) that includes all the mandatory cities (and any number of optional cities), i.e. MV,andwhichhasminimumtotaldistance d(H){d(i, j)|(i, j)E}.
1. Show that the optimal graph is a tree (i.e. has no cycles).
2. Formulate the decision version of the Steiner Tree problem.
3. Suppose that we are given a subroutine that solves the decision version in polynomial time. Give a polynomial time algorithm that uses this subroutine to solve the optimization problem, i.e. which returns a Steiner tree with minimum total distance.
(Hint: First compute the value of the optimal Steiner tree; keep in mind that the distances are given in binary. Then compute the optimal Steiner tree itself.)
4. Show that the decision version of the Steiner tree problem is NP-complete even if all the distances are 1 or .
(Hint: You can reduce if you want from the Node Cover or from the Set Cover problem.)
Problem 4. [20 points] A Boolean formula (expression) is in Disjunctive Normal Form (DNF) if it is the disjunction (the OR) of a set of conjunctions (AND’s) of literals. For exampletheformula (x1 x2)(x2 x3 x4)(x1 x3 x4) isinDNF.
(a) Show that the Satisfiability problem for Boolean formulas in DNF is in P.
(b) A Boolean formula is called a tautology if every truth assignment satisfies it.
Show that the problem DNF-TAUT={ DNF formula F | F is a tautology } is coNP- complete.
Problem 5. [20 points] Consider optimization problems with solutions that are polynomially bounded and polynomially verifiable, and with polynomially computable integer values. More specifically, instances of and solutions are represented, as usual, as strings over some alphabet. There is a polynomially balanced and polynomially verifiable binary relation S that relates instances to solutions, i.e. S(x,y) holds for strings x,y iff y is a solution for the instance x of (recall that “S is polynomially balanced” means that S(x,y) implies that |y|≤p(|x|) for some polynomial p, and “S is polynomially verifiable” means that there is a polynomial-time algorithm which given x,y as input determines whether S(x,y) holds or not). There is a polynomially computable integer- valued function f(x,y) that gives the value of solution y for the instance x.
Let 1 be a minimization problem and 2 a maximization problem as above, with the same set of instances; the two problems have their own sets of solutions specified by
relations S1 , S2 , and their own value functions f1, f2 . We say that 1 and 2 are dual of each other if for every instance x they have equal optimal values, i.e. min{ f1(x, y)| y is a solutionofinstancexof 1}=max{ f2(x,y)|yisasolutionofinstancexof 2}. Suppose that 1 , 2 are dual problems as above.
1. Show that the following Optimality Testing problem is in NPcoNP for both 1 , 2 :
Input: Instance x, solution y.
Question: Is y an optimal solution for x?
2. Show that the decision version of both optimization problems is in NPcoNP.
(Note: Duality is an important property of many optimization problems. Examples include Linear Programming, Max Flow-Min Cut and a number of others.)