# 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? Dec 10 '15 at 5:27
• Of course, the question isn't worded well. Will change ! 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$). 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.

• Thanks for your hint! If the original graph has a clique, I can duplicate it and connect all the corresponding vertices in the copies to one another. This way, the new graph will have an edge between the cliques and hence, the new graph will be a k-dumbbell. But if I am given a k-dumbbell, since it has to have 2 cliques, how do I make sure that the subgraphs have cliques each ( what if the added edges interfere with the cliques )? I'm confused. Dec 10 '15 at 14:02
• @LockStock I haven't given a complete solution since it's your exercise rather than mine. I won't give further hints. Spend a few more hours on the question. Not all questions can be solved immediately. You have to be more patient. Dec 10 '15 at 14:07
• 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 ! Dec 10 '15 at 18:10
• This only shows hardness for containment of a k-dumbbell, not being a k-dumbell. ​ ​
– user12859
Dec 10 '15 at 20:51
• @RickyDemer Which is exactly what we want. Dec 10 '15 at 22:27