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

Question

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.

Answer 1

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

Further reading.

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'$.

Note that the maximum clique problem is one of the Karp's 21 hard problem, which are probably some of the most important/original proven hard problems. In his paper "Reducibility Among Combinatorial Problems" [Karp, 1972], he provides some of the very first hardness reductions using Cook's theorem. Here is a link to the wiki page of the paper where you can find more information and a link to the original paper.