1
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Hi, In the first reduction, are both input k and T for clique and subsetsum are equal to d? $\endgroup$
    – Doralisa
    Jul 25 at 18:07
  • $\begingroup$ Yes, for Clique ask if there is a group larger than k, a group can be size d. And in SubsetSum want the sum of some of the elements to be equal to T. If there is a size d group in Clique you want it to also be the sum of some of the elements in SubsetSum. $\endgroup$
    – dustyeav
    Jul 25 at 18:27
  • 1
    $\begingroup$ Could you please not use code blocks or italics to format your own thinking? It is plenty clear that these are your thoughts and the formatting just makes your text noisy and harder to read. $\endgroup$
    – idmean
    Jul 25 at 18:45
  • 1
    $\begingroup$ I think there is a typo in section B. Shouldn't we sent $f(A,d) = <G,k>$ to clique? meanwhile, I have the same question again here. Is $k$ in the mapped clique the same as $d$ in the input for subset-sum? And I don't see what is the use of $V^*$ and $E^*$ here. Didn't you have miss anything? $\endgroup$
    – Doralisa
    Jul 25 at 18:53
  • $\begingroup$ Yes, you're right, I corrected that. $\endgroup$
    – dustyeav
    Jul 26 at 5:47
1
$\begingroup$

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.

$\endgroup$
11
  • $\begingroup$ Thanks for the answer, regarding the reduction from section B that I accidentally copied, I corrected it. The section A you explained to me, I understood so the answer should be 3, am I right? Regarding the section B I did not understand whether the reduction is polynomial or not. If for example I have in SubsetSum, k numbers, so I might make a group up to $2 ^{k}$ in size in Clique, so the answer should be 4, because the reduction is neither polynomial nor correct? $\endgroup$
    – dustyeav
    Jul 26 at 6:14
  • $\begingroup$ As for the second part, maybe there will be a number valued at $ 2 ^{k }$, so the reduction will be non-polynomial? $\endgroup$
    – dustyeav
    Jul 26 at 6:23
  • $\begingroup$ @dustyeav Yes, 3 is the correct answer for A. Now that you have updated B, I can also say that it is incorrect. No, it won't create $2^k$ but instead the sum of that $k$ numbers many vertices. This is a run-time dependent on the value of the input numbers, not the length (i.e. the count) of the input. Consider the difference between the input of binary numbers "1" and "10" (assume $k=1$). The latter doubles the number of vertices created but we have added only one bit. $\endgroup$
    – idmean
    Jul 26 at 6:26
  • $\begingroup$ You might also want to look at en.wikipedia.org/wiki/Pseudo-polynomial_time. Pseudo-polynomial time can be tricky. $\endgroup$
    – idmean
    Jul 26 at 6:29
  • 1
    $\begingroup$ Yes, that's what I would have chosen if I had taken the test. $\endgroup$
    – idmean
    Jul 26 at 10:32
1
$\begingroup$

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}.$

enter image description here

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.

enter image description here

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

$\endgroup$
2
  • $\begingroup$ Thanks for the answer, as I told idmean, regarding the reduction from section B that I accidentally copied, I corrected it. Regarding the section A, it is clear to me so I conclude that the answer is 3. Regarding the section B I did not understand whether the reduction is polynomial or not. If in subsetSum I have k numbers, then the size of the Clique will be $2 ^{ k}$? $\endgroup$
    – dustyeav
    Jul 26 at 6:17
  • $\begingroup$ As for the section B, I do not know what numbers I will have in the group, maybe there will be a number valued at $ 2 ^ k $, so the reduction will be non-polynomial? $\endgroup$
    – dustyeav
    Jul 26 at 6:21

Your Answer

By clicking β€œPost Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.