I can't seem to grasp the term of reduction that well.

To explain I will take an example the problem of $$\sqrt{k} - clique $$ such that $$ k \leq \sqrt{V}$$

Solving by reduction with normal k-clique such as $k-clique \leq \sqrt{k}- clique$

The reduction would be function f, such that f(G,k,) = (G',k') where the input is for K-clique.

The solution would be, to copy graph G to G' and add n^2-n individual nodes to G' leaving us with n^2 the size of G', hence we get that k' = k

Now what I what I want to understand is from the definition of reduction, does the normal k-clique algorithm works also on the graph G' in the output of function f? we only added to G, n^2-2 indiviual nodes that aren't connected to any edges, thus the number of clique nodes stays the same as k, coming from that we executed the algorithm of normal k-clique on the square root k clique? That's my understanding of reduction for now

  • $\begingroup$ Can you define $\sqrt{k}$-clique formally? Also, in a reduction, you need to prove a statement of the form "The answer to instance $(G, k)$ is yes if and only if the answer to instance $f(G, k)$ is yes". Can you write what this statement is, concretely, for your problems? This can help clarifying. $\endgroup$ Commented Jul 14, 2022 at 12:14
  • $\begingroup$ @ManuelLafond Bare with me im newly adjusting to the term reduction. My question is similar to this post cs.stackexchange.com/questions/65014/… $\endgroup$ Commented Jul 14, 2022 at 12:47


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.