Reduction between CLIQUE to SUBSET SUM

Question

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.

Answer 1

The reduction from $Clique \leq_P SubsetSum$ is incorrect. Take a graph $G$ with four vertices $(v_1, ..., v_4)$, edges $(v_1, v_2), (v_3, v_4$) and let $d = 4$. Then $A = \{1,1,1,1\}$ (assuming $A$ is a multiset). Clearly there is a subset in $A$ whose sum is 4 but there is no clique of size 4 in $G$.

As for the reduction $SubsetSum \leq_P Clique$, your description doesn't make a whole lot of sense. Which vertices are connected? All of them? Also, you just copied the output of the reduction from the first part, so it's not entirely clear what size of clique the reduction uses.

As far as I can tell, the reduction is performed in $O\left(\left(\sum_{b\in B} b\right)^2\right)$. Note that we are considering numeric values from the input, but not the input length. The reduction is therefore pseudo-polynomial.

Answer 2

I think one of an important parts of reduction for languages like Clique and Subset-sum is the integer we have given next to the input. That is $k$ for Clique which tells us which size of the clique we are looking for and $d$ in Subset-sum that tells us the sum of a collection of numbers.

I have drawn little pictures for you to see how this works. For section A, you have an input like $<G,k>$ and you have to map it to an output like $<S, d>$. If you have a graph as follows and $k=5$, then by the reduction that you have provided in section A, you have the collection $S$. It can be seen that we have some numbers whose sum is $5$ though we don't have a 5-clique in the graph. So the reduction is not correct since we wanted a reduction that $<G,k> \in \textbf{Clique} \iff <S,d> \in \textbf{Subset-sum}.$

And the reduction is indeed polynomial. You just need to look at every vertex to count its degree.

For section B, I did not get the reduction properly but I can think of it in two ways. The first way is to connect all vertices of a number $b_i$ of the collection only. The second way is to connect all vertices of all $b_i$. In the first way for the set $S=\{2,2\}$ we have a graph with two unconnected parts (The black edges only). In the second way, we have a full connected graph (both gray and black edges). In both of these ways, you do not have a correct reduction since in the first way you have $2+2 = 4$ and you do not have a 4-clique graph. In the second way, you do not have numbers that their sum is $3$ but you do have a 3-clique.

And for the complexity of this reduction, I have the same opinion as @idmean described in his answer.