A Complexity Problem of Cliques

31 Views Asked by At

I've been trying to figure out the Karp Reduction $$CLIQUE(G,k) \preceq IND(G,k),$$ Where $CLIQUE(G,k)$ is the decision problem "Is there a clique of size at least $k$ in the graph $G$" and $IND(G,k)$ is the decision problem ``Is there an independent set of size at least $k$ in the graph $G$." I have a feeling that this reduction has something to do with the edges available in the Graph $G$, but I am also wondering if it would be better to find another decision problem that $CLIQUE(G,k)$ reduces to in the hopes that it will easily reduce to $IND(G,k).$ Any suggestions? Should I consider the vertices in a potential clique in $G$?