0
$\begingroup$

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

Improve this question
$\endgroup$
2
  • $\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$
    – Manuel Lafond
    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$
    – Mostfa Mostfa
    Jul 14, 2022 at 12:47

0

Reset to default

Your Answer

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