2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

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.