# Is it NP-complete to test if a graph contains $t$ $k$-cliques?

Given a graph $$G$$ along with two non-negative integers $$t, k \in \mathbb{N}$$, The instance $$(G,t,k)$$ is a yes instance of the problem if and only if the graph $$G$$ contains $$t$$ cliques with $$k$$ vertices (there are $$t$$ copies of $$K_k$$, a cliques of size $$k$$ in the graph $$G$$). How to prove that $$(G,t,k)$$ is NP-complete?

It is obvious that it is in NP. I have tried to prove that $$k$$-CLIQUE language $$(G,k)$$ is reducible to a $$(G,t,k)$$ language. But I can't get the idea, how to get $$t$$ of $$k$$-CLIQUES.

• Do you mean at least $t$ cliques or exactly $t$ cliques? – xskxzr May 22 '19 at 8:51
• Think about what happens if you have a graph $G$ and make $t$ disjoint copies of it. – Pål GD May 22 '19 at 9:17
• Terminology note / nitpick: a graph can not be NP-complete because a graph is not a language. Similarly, a tuple $(G,k,t)$ can not be NP-complete since it is not a language. What you should mention instead, is the language of all the (encoded) tuples $(G,t,k)$ such that your property holds. – chi May 22 '19 at 10:35

This problem is clearly NP-hard since it is a generalization of many NP-hard problems. The most obvious one is the maximum clique problem, i.e. finding a clique of the maximum size in a graph. The decision version of this problem is a special case of your problem where you set $$t$$ equal to one. (See below for the hardness-proof).
Other example is the triangle packing problem, assuming you are looking for pairwise vertex-disjoint cliques (note that for the maximum clique it does not matter if the cliques have to be vertex disjoint since we chose $$t=1$$). In the triangle packing problem we are looking for a set of $$k'$$ vertex-disjoint triangles ($$K_3$$) in a graph, which is a special case of your problem where we set $$k = 3$$ and $$t = k'$$.