I have a question from a test that I failed to pass, I failed to do the question.

The question is about the reduction between Clique and Subset Sum. I tried to find an explanation for this on the internet and in the books but could not find anything.

Recall the expression problems:

• $Clique(G, k)$ - Is there graph G with clique of size ≥ k?

• $SubsetSum(B, T)$ - Given a set of integers 𝐵 ⊆ ℤ and an integer T ⊆ ℤ, is it possible to find a subgroup 𝐵′ of 𝐵 such that the sum of subgroup 𝐵′ is equal to-𝑇?

We want to show that the problems are of the same degree of difficulty. That is, we see two reductions, in both directions.

The question consists of two sections that are related to each other, so I can not ask each question separately.

section A:

First we see a proposal for a reduction $Clique ≤_P SubetSum$ . Given graph $G = (V,E)$ and number d the group is constructed: $A =\{a_v| v \in V\}$. Also, we will define: $a_v = deg (v)$. That is, for each vertex we create a new element whose size is the number of neighbors it has. Sent to SubsetSum problem the $f(G,k) = \left \langle A,d \right \rangle$

Determine which of the following statements is correct:

1. The reduction is correct and polynomial.
2. Although the reduction is correct, it is not polynomial, in the case where there is a vertex with an exponential rank.
3. Although the reduction is polynomial, it is incorrect.
4. The reduction is incorrect and not polynomial.
5. None of the above claims are true.

I think the correct answer should be 1 or 3. The reduction is polynomial. Because for each vertex it is possible to add a maximum of all the other vertices, that is $| V | ^ 2$. But I do not know if it is a correct reduction, I tried to look for an answer to it on the Internet and found nothing.

1. The reduction is polynomial but I do not know if it is also correct.
2. This is not true
3. Not sure if the reduction is correct.
4. This is not true

section B:

We will now consider the $ 𝑆𝑢𝑏𝑠𝑒𝑡𝑆𝑢𝑚 ≤_𝑃 𝐶𝑙𝑖𝑞𝑢𝑒 $ reduction proposal. Given number group B and number T for the SubsetSum problem, a new graph G* was constructed as to:

• For each $b_i \in B$ element, $b_i$ vertices $v_{i,1}, \cdots , v_{i,b_i}$ are constructed. For example, $b_2 = 5$ constructed the vertices $v_{2,1}, v_{2,2} , v_{2,3}, v_{2,4}, v_{2,5} $.
• All these vertices are connected in the edges to each other.
• The collection of all vertices from all the $b_i$ is V*
• The collection of all edges is E*

Sent to SubsetSum problem the $f(G,k) = \left \langle A,d \right \rangle$

Determine which of the following statements is correct:

1. The reduction is correct and polynomial.
2. Although the reduction is correct, it is not polynomial.
3. Although the reduction is polynomial, it is incorrect, for each member from B a clique is created on its own, but the cliques are not connected to each other.
4. The reduction is incorrect and not polynomial, for each member from B a clique is created on its own, but the cliques are not connected to each other.
5. None of the above claims are true.

I can not see how the reduction works and leads to a solution in Clique. In terms of runtime, I can not calculate it, it seems complex.

Maybe the correct answer is 4, but I'm not sure why, it just seems very complex.

I have a question from a test that I failed to pass, I failed to do the question.

The question is about the reduction between Clique and Subset Sum. I tried to find an explanation for this on the internet and in the books but could not find anything.

Recall the expression problems:

• $Clique(G, k)$ - Is there graph G with clique of size ≥ k?

• $SubsetSum(B, T)$ - Given a set of integers 𝐵 ⊆ ℤ and an integer T ⊆ ℤ, is it possible to find a subgroup 𝐵′ of 𝐵 such that the sum of subgroup 𝐵′ is equal to-𝑇?

We want to show that the problems are of the same degree of difficulty. That is, we see two reductions, in both directions.

The question consists of two sections that are related to each other, so I can not ask each question separately.

section A:

First we see a proposal for a reduction $Clique ≤_P SubetSum$ . Given graph $G = (V,E)$ and number d the group is constructed: $A =\{a_v| v \in V\}$. Also, we will define: $a_v = deg (v)$. That is, for each vertex we create a new element whose size is the number of neighbors it has. Sent to SubsetSum problem the $f(G,k) = \left \langle A,d \right \rangle$

Determine which of the following statements is correct:

1. The reduction is correct and polynomial.
2. Although the reduction is correct, it is not polynomial, in the case where there is a vertex with an exponential rank.
3. Although the reduction is polynomial, it is incorrect.
4. The reduction is incorrect and not polynomial.
5. None of the above claims are true.

I think the correct answer should be 1 or 3. The reduction is polynomial. Because for each vertex it is possible to add a maximum of all the other vertices, that is $| V | ^ 2$. But I do not know if it is a correct reduction, I tried to look for an answer to it on the Internet and found nothing.

1. The reduction is polynomial but I do not know if it is also correct.
2. This is not true
3. Not sure if the reduction is correct.
4. This is not true

section B:

We will now consider the $ 𝑆𝑢𝑏𝑠𝑒𝑡𝑆𝑢𝑚 ≤_𝑃 𝐶𝑙𝑖𝑞𝑢𝑒 $ reduction proposal. Given number group B and number T for the SubsetSum problem, a new graph G* was constructed as to:

• For each $b_i \in B$ element, $b_i$ vertices $v_{i,1}, \cdots , v_{i,b_i}$ are constructed. For example, $b_2 = 5$ constructed the vertices $v_{2,1}, v_{2,2} , v_{2,3}, v_{2,4}, v_{2,5} $.
• All these vertices are connected in the edges to each other.
• The collection of all vertices from all the $b_i$ is V*
• The collection of all edges is E*

Sent to Clique problem the $f(B,T) = \left \langle G*,T \right \rangle$

Determine which of the following statements is correct:

1. The reduction is correct and polynomial.
2. Although the reduction is correct, it is not polynomial.
3. Although the reduction is polynomial, it is incorrect, for each member from B a clique is created on its own, but the cliques are not connected to each other.
4. The reduction is incorrect and not polynomial, for each member from B a clique is created on its own, but the cliques are not connected to each other.
5. None of the above claims are true.

I can not see how the reduction works and leads to a solution in Clique. In terms of runtime, I can not calculate it, it seems complex.

Maybe the correct answer is 4, but I'm not sure why, it just seems very complex.

The question:

Recall the expression problems:

• 𝐶𝑙𝑖𝑞𝑢𝑒 (𝐺,𝑘) - Is there graph G with clique of size ≥ k?

• 𝑆𝑢𝑏𝑠𝑒𝑡𝑆𝑢𝑚 (𝐵, 𝑇)- Given a set of integers 𝐵 ⊆ ℤ and an integer T ⊆ ℤ, is it possible to find a subgroup 𝐵′ of 𝐵 such that the sum of subgroup 𝐵′ is equal to-𝑇?

section A:

First we see a proposal for a reduction $𝐶𝑙𝑖𝑞𝑢𝑒 ≤_𝑃 𝑆𝑢𝑏𝑠𝑒𝑡𝑆𝑢𝑚$ . Given graph $G = (V,E)$ and number d the group is constructed: A = {$a_v| v \in V$}. Also, we will define: $a_v = deg (v)$. That is, for each vertex we create a new element whose size is the number of neighbors it has. Sent to SubsetSum problem the $f(G,k) = \left \langle A,d \right \rangle$

Determine which of the following statements is correct:

1. The reduction is correct and polynomial.
2. Although the reduction is correct, it is not polynomial, in the case where there is a vertex with an exponential rank.
3. Although the reduction is polynomial, it is incorrect.
4. The reduction is incorrect and not polynomial.
5. None of the above claims are true.

I think the correct answer should be 1 or 3. The reduction is polynomial. Because for each vertex it is possible to add a maximum of all the other vertices, that is $| V | ^ 2$. But I do not know if it is a correct reduction, I tried to look for an answer to it on the Internet and found nothing.

section B:

Sent to SubsetSum problem the $f(G,k) = \left \langle A,d \right \rangle$

Determine which of the following statements is correct:

1. The reduction is correct and polynomial.
2. Although the reduction is correct, it is not polynomial.
3. Although the reduction is polynomial, it is incorrect, for each member from B a clique is created on its own, but the cliques are not connected to each other.
4. The reduction is incorrect and not polynomial, for each member from B a clique is created on its own, but the cliques are not connected to each other.
5. None of the above claims are true.

I can not see how the reduction works and leads to a solution in Clique. In terms of runtime, I can not calculate it, it seems complex.

Maybe the correct answer is 4, but I'm not sure why, it just seems very complex.

Recall the expression problems:

• $Clique(G, k)$ - Is there graph G with clique of size ≥ k?

• $SubsetSum(B, T)$ - Given a set of integers 𝐵 ⊆ ℤ and an integer T ⊆ ℤ, is it possible to find a subgroup 𝐵′ of 𝐵 such that the sum of subgroup 𝐵′ is equal to-𝑇?

section A:

First we see a proposal for a reduction $Clique ≤_P SubetSum$ . Given graph $G = (V,E)$ and number d the group is constructed: $A =\{a_v| v \in V\}$. Also, we will define: $a_v = deg (v)$. That is, for each vertex we create a new element whose size is the number of neighbors it has. Sent to SubsetSum problem the $f(G,k) = \left \langle A,d \right \rangle$

Determine which of the following statements is correct:

1. The reduction is correct and polynomial.
2. Although the reduction is correct, it is not polynomial, in the case where there is a vertex with an exponential rank.
3. Although the reduction is polynomial, it is incorrect.
4. The reduction is incorrect and not polynomial.
5. None of the above claims are true.

I think the correct answer should be 1 or 3. The reduction is polynomial. Because for each vertex it is possible to add a maximum of all the other vertices, that is $| V | ^ 2$. But I do not know if it is a correct reduction, I tried to look for an answer to it on the Internet and found nothing.

section B:

Sent to SubsetSum problem the $f(G,k) = \left \langle A,d \right \rangle$

Determine which of the following statements is correct:

1. The reduction is correct and polynomial.
2. Although the reduction is correct, it is not polynomial.
3. Although the reduction is polynomial, it is incorrect, for each member from B a clique is created on its own, but the cliques are not connected to each other.
4. The reduction is incorrect and not polynomial, for each member from B a clique is created on its own, but the cliques are not connected to each other.
5. None of the above claims are true.

I can not see how the reduction works and leads to a solution in Clique. In terms of runtime, I can not calculate it, it seems complex.

Maybe the correct answer is 4, but I'm not sure why, it just seems very complex.