2
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

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?).

Improve this answer
$\endgroup$
1
  • $\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$
    – Phil Spencer
    Jun 21, 2017 at 17:06

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.

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