Recall that $G$ has a clique of size $k$ if it has a complete sub graph consisting of $k$ vertices.

Let us define the problem $Clique-k$ as follows: $$\{ \langle G \rangle \mid G \text{ is an undirected graph that contains a clique of size } k\}$$

Question: Find a reduction $f$ from $Clique-6$ to $Clique-3$ such that $f$'s input is a graph $G$ with $n$ vertices, $f(G)$ is a graph with $O(n^2)$ vertices, and $$G \in Clique-6 \Leftrightarrow f(G) \in Clique-3$$

The required time complexity for the computation of $f$ is $O(n^4)$.

I am not sure how to approach this problem, and would be thankful if someone can provide insights \ directions to the solution.


1 Answer 1


Create a new graph whose vertices are pairs of vertices in the original graph (optimization: 2-cliques, i.e. edges, in the original graph), and whose edges correspond to 4-cliques. The new graph has a 3-clique iff the original graph has a 6-clique (why?).

  • $\begingroup$ I was trying to do just that but instead of creating vertices from edges, I created them from triangles (3-cliques) so it did not work. This really helped a lot, thank you! $\endgroup$ Jun 21, 2017 at 17:06

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.