1
$\begingroup$

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.

I'm new to this so, if I'm wrong somewhere, please help me out !

$\endgroup$
  • 4
    $\begingroup$ 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? $\endgroup$ – Yuval Filmus Dec 10 '15 at 5:27
  • $\begingroup$ Of course, the question isn't worded well. Will change ! $\endgroup$ – LockStock Dec 10 '15 at 13:32
  • 2
    $\begingroup$ 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$). $\endgroup$ – Tom van der Zanden Dec 10 '15 at 14:28
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – LockStock Dec 10 '15 at 14:02
  • $\begingroup$ @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. $\endgroup$ – Yuval Filmus Dec 10 '15 at 14:07
  • $\begingroup$ 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 ! $\endgroup$ – LockStock Dec 10 '15 at 18:10
  • $\begingroup$ This only shows hardness for containment of a k-dumbbell, not being a k-dumbell. ​ ​ $\endgroup$ – user12859 Dec 10 '15 at 20:51
  • $\begingroup$ @RickyDemer Which is exactly what we want. $\endgroup$ – Yuval Filmus Dec 10 '15 at 22:27

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.