We define the language SUBSET-SUM as follows: SUBSET-SUM = 3 (S, k) : There exists S* C S such that s=k SES*
That is, (S, k) E SUBSET-SUM iff there is a subset of numbers in S such that their sum is
A student would like to prove that the language SUBSET-SUM is NP-Hard by using VERTEX-COVER. They have provided the following reduction but have given no analysis to justify their reduction. As a result, they will gain no points for the analysis of the reduc- tion, but it is still possible that their reduction is correct. As a grader, you need to analyze this reduction to provide the appropriate number of points. The reduction works as follows:
f on input (G= (V, E), k):
(1) Fix an arbitrary ordering on the edges of the graph G.
(2) For each vertex v, generate a number with El + 1 digits where the last digit is 1, and the ith digit is 1 if the įth edge is incident to v. All other digits in this number are 0.
(3) For the ith edge, generate a number with E +1 digits where the ith digit of this number is 1. All other digits in this number are 0.
(4) Output all of the numbers generated and the number 2...2k El copies of 2, followed by k noting that all of the numbers are represented in base k +1.