程序代写代做代考 algorithm Microsoft Word – hw4

Microsoft Word – hw4

COMS 4236: Introduction to Computational Complexity, Spring 2018

Problem Set 4, due Thursday March 29, 11:59pm on Courseworks

Please follow the homework submission guidelines posted on
Courseworks.

Problem 1. [15 points] Recall the Subset Sum problem:
Input: A collection S of positive integers 1 2, , , ms s s 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 1 2, , , ms s s
Question: Is there a partition of the collection S into two subcollections 1 2,S S (where

1 2 1 2,S S S S S    ) whose sums are equal:
1 2i i

i i
s S s S

s s
 

  ?

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 vK there is a node uK
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 MN 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.
MV, and which has minimum total distance ( ) { ( , ) | ( , ) } 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
example the formula 1 2 2 3 4 1 3 4( ) ( ) ( )x x x x x x x x       is in DNF.
(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 1S , 2S , and their own value functions 1 2,f f . We say that 1 and 2 are dual of
each other if for every instance x they have equal optimal values, i.e. min{ 1( , )f x y | y is a

solution of instance x of 1 } = max{ 2 ( , )f x y | y is a solution of instance x of 2 }.
Suppose that 1 , 2 are dual problems as above.
1. Show that the following Optimality Testing problem is in NPcoNP 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 NPcoNP.

(Note: Duality is an important property of many optimization problems. Examples
include Linear Programming, Max Flow-Min Cut and a number of others.)