Is the Clique Problem polynomial time reducible to the graph-Homomorphism Problem and if so what does the reduction look like?

Question

Is the k-Clique Problem (given a Graph G and a natural number k does G kontain a Clique of size k)
polynomial time reduzible to the graph-Homomorphism Problem (given two graphs, G and H, is there a Homomorphism from G to H)

And if so what would the reduction look like?

Since i am a little confused by the subject, is the following correct?

A polynomial time reduction from Clique to graph-Homomorphism is a funktion that can be calculated in polynomial time and for which if you input a yes instance of clique it returns a yes instance of graph-Homomorphism, same for no instances.

Answer 1

The $k$-clique problems asks whether there is a homomorphism from the $k$-clique to a given graph. Therefore in principle, given an instance $\langle G,k \rangle$ of $k$-clique, you can just output $\langle K_k, G \rangle$, which is an instance of graph homomorphism.

However, in general $\langle K_k, G \rangle$ could be much larger than $\langle G,k \rangle$, since encoding $k$ takes $\Theta(\log k)$ bits, whereas encoding $K_k$ probably takes $\Theta(k^2)$ bits (depending on your encoding). Assuming that graphs are encoded as adjacency matrices, the solution is to compare $k$ to the number of vertices in $G$. If $k$ is larger than the number of vertices in $G$, then the answer is No, and so you can output a fixed No instance (say $K_2,K_1$). Otherwise the size of the output instance is polynomial in the size of the input instance, and so there is no problem.