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.

  • $\begingroup$ Do you mean at least $t$ cliques or exactly $t$ cliques? $\endgroup$ – xskxzr May 22 '19 at 8:51
  • $\begingroup$ Think about what happens if you have a graph $G$ and make $t$ disjoint copies of it. $\endgroup$ – Pål GD May 22 '19 at 9:17
  • $\begingroup$ 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. $\endgroup$ – 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).

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.


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.