# NP-complete reduction for a k-dumbbell graph

A k-dumbbell is a graph that consists of 2 cliques each of size k with one and only one edge between them. How do I show that finding if a graph is a k-dumbbell is NP-complete?

Proof it is in NP: Given the cliques of size k, I can verify if it they are the cliques of size k.

Proof of NP-hardness: If there is only one edge between them, how can I be sure that this is the edge I need for the reduction?

I'm trying to reduce from the k-clique problem as it seems to be the easiest choice.

• A graph is not NP-complete. Perhaps you mean the problem of, given a graph $G$ and a parameter $k$, deciding whether the graph $G$ contains a $k$-dumbbell? – Yuval Filmus Dec 10 '15 at 5:27
• Of course, the question isn't worded well. Will change ! – LockStock Dec 10 '15 at 13:32
• With regards to your edited question, determining whether a graph is a k-dumbbell isn't NP-complete at all (or at least, it isn't, assuming $P\not = NP$). – Tom van der Zanden Dec 10 '15 at 14:28

Hint: Following your idea, you want to reduce the clique problem to the dumbbell problem, to show that the latter is NP-hard. Given an instance $(G,k)$ of the clique problem, it is natural to consider two copies $G',G''$ of your original graph, connected in some way, so that if the original graphs contains a $k$-clique, then the new one contains a $k$-dumbbell.
If the new graph contains a $k$-dumbbell restricted to one of the copies, then the original graph certainly contains a $k$-clique. You want to arrange matters so that if the $k$-dumbbell straddles both copies, then it is composed of a $k$-clique in each one.
This is just a hint, so I'm not giving a full solution. Indeed, there might be several ways of using this idea to get an NP-hardness reduction. Some of them require you to slightly change the value of $k$ from the clique instance to the dumbbell instance.
• I got it now! On duplicating the original graph $G$ and attaching the smiliar vertices, if $G$ has a k-clique, the resulting $G^'$ will be a k-dumbbell. If $G^{'}$ has a k-dumbbell, the newly added edges do not interfere with the clique. Hence, it must have a clique in the subcomponent. However, by our construction, $G^{'}$ has two copies of $G$ so, $G$ must have a clique in it. Thanks for not giving the answer out ! – LockStock Dec 10 '15 at 18:10