22
$\begingroup$

Let me start off by noting this is a homework problem, please provide only advice and related observations, NO DIRECT ANSWERS please. With that said, here is the problem I am looking at:

Let HALF-CLIQUE = { $\langle G \rangle$ | $G$ is an undirected graph having a complete subgraph with at least $n/2$ nodes, where n is the number of nodes in $G$ }. Show that HALF-CLIQUE is NP-complete.

Also, I know the following:

  • In terms of this problem a clique, is defined as an undirected subgraph of the input graph, wherein every two nodes are connected by an edge. A $k$-clique is a clique that contains $k$ nodes.
  • According to our textbook, Michael Sipser's "Introduction to the Theory of Computation", pg 268, that the problem CLIQUE = {$\langle G,k\rangle$ | $G$ is an undirected graph with a $k$-clique} is in NP
  • Furthermore, according to the same source (on pg 283) notes that CLIQUE is in NP-Complpete (thus also obviously in NP).

I think I have the kernel of an answer here, however I could use some indication of what is wrong with it or any related points that might be relevant to an answer. This is the general idea I have so far,

Ok, I'd first note that a certificate would simply be a HALF-QLIQUE of $\text{size} \geq n/2$. Now it appears that what I would need to do is to create a verifier that is a polynomial time reduction from CLIQUE (which we know is NP-Complete) to HALF-CLIQUE. My idea would be that this would be done by creating a Turing machine which runs the turing machine verifier in the book for CLIQUE with the additional constraint for HALF-CLIQUE.

This sounds correct to me, but I don't really trust myself yet in this subject. Once again, I would like to remind everyone this is a HOMEWORK PROBLEM so please try to avoid answering the question. Any guidance which falls short of this would be most welcome!

Improve this question
$\endgroup$

3 Answers 3

Reset to default
16
$\begingroup$

Judging by your description and comments, you might be helped the best by an exact description on how reductions can be used to prove NP-completeness:

A problem is NP-complete iff it is in NP and it is NP-hard. This means that any proof of NP-completeness has two parts: a proof that the problem lies in NP and a proof that it is NP-hard.

For the first part, you have to show that YES-instances can be verified in polynomial time using some suitable certificate. Alternatively, you can show the problem can be solved in polynomial time by a non-deterministic Turing machine, but this is not usually done as mistakes are easily made.

In your case, this comes down to proving that for every graph with a $n/2$-clique, you can find some proof that there is indeed such a clique, such that, armed with such a proof, you can check in polynomial time that there is indeed such a clique.

For the second part, you have to show that the problem is NP-hard. This is in nearly all cases shown by proving that your problem is at least as hard as some other NP-hard problem. If HALF-CLIQUE is as least as hard as CLIQUE, it must also be NP-hard.

You do this by proving a reduction FROM CLIQUE, TO HALF-CLIQUE. You 'reduce' the problem, making it 'easier'. You say "Solving CLIQUE is hard, but I have proven that you only need to solve HALF-CLIQUE to solve CLIQUE". (many people, even experts, occasionally say this the wrong way around :))

There are different types of reductions: the reduction that is most commonly used is the one where you map instances of in this case CLIQUE to instances of HALF-CLIQUE whose size is at most polynomially larger, in polynomial time. This means that if we can solve HALF-CLIQUE, then we can also solve CLIQUE by chaining the algorithm and the reduction.

In other words, we must show that we can solve CLIQUE if we can solve HALF-CLIQUE. We do this by showing that for every instance for CLIQUE, we can design an instance of HALF-CLIQUE such that the instance of CLIQUE is a 'yes' instance iff the instance of HALF-CLIQUE is a 'yes' instance.

The proof therefore starts like this: given a graph $G=(V, E)$, I can create some graph $H=(V', E')$ such that $G$ contains a $k$-clique iff $H$ contains a $n/2$-clique. I'll leave this part to you (this is the part that requires creativity, the part that is about the specific problem at hand).

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Excellent set up, I think you did a very good job in providing just enough information to guide without providing an answer and doing so in a eloquent way. Thank you. $\endgroup$
    – BrotherJack
    Apr 10, 2012 at 3:08
  • 1
    $\begingroup$ Something like this should be put in the tag wiki of np-complete for future reference. Would you mind? $\endgroup$
    – Raphael ♦
    Apr 10, 2012 at 7:28
8
$\begingroup$

You seem a little lost. You want to show that HALF-CLIQUE $\ge$ CLIQUE, which means that you are looking for a poly-time algorithm that takes CLIQUE instances as the input and outputs HALF-CLIQUE instances with the property that "yes" inputs map to "yes"es and "no" inputs map to "no"s.

So, basically, the task is to take a graph $G$ and a number $k$ and output a new graph $H$ (and no number) so that $H$ has a clique on at least half of its vertices whenever $G$ has a clique of size $k$.

The spoiler below contains a hint on how to perform this reduction:

Try to make $H$ by attaching (in some way) an appropriately sized clique to $G$, plus some number of vertices not connected to anything.

Improve this answer
$\endgroup$
5
  • $\begingroup$ I'm not understanding what you're saying. What I tried to do was to reduce HALF-CLIQUE to CLIQUE by modifying the varifier used in the book to prove that CLIQUE was NP, have it run on the input graph G, and if it found a CLIQUE checking to see if said CLIQUE contained at least n/2 nodes, where n is the number of nodes in G. Wouldn't such a verifier of HALF-CLIQUE show that the verifier of CLIQUE is a reduced form of it (as in a sub problem of solving HALF-CLIQUE)? $\endgroup$
    – BrotherJack
    Apr 9, 2012 at 22:21
  • $\begingroup$ Or are you saying that I have it backwards and need to prove CLIQUE needs to be reduced to HALF-CLIQUE? I'm also completely not getting your spoiler. Is there any way to explain it without giving away the answer? $\endgroup$
    – BrotherJack
    Apr 9, 2012 at 22:59
  • 3
    $\begingroup$ Yes, to show a problem is NP-complete, you need to (a) show it is in NP and (b) reduce some known NP-hard problem to it. To remember the right direction for the reduction, the point is to use the new problem as a "black box" for efficiently solving a known NP-C problem. $\endgroup$
    – Louis
    Apr 9, 2012 at 23:18
  • $\begingroup$ OK, I think I understand now. Thanks for your help! $\endgroup$
    – BrotherJack
    Apr 10, 2012 at 3:09
  • $\begingroup$ +1 I think I got it. Your hint was very instructive once I understood what I was doing wrong. Thanks again! $\endgroup$
    – BrotherJack
    Apr 10, 2012 at 5:02
0
$\begingroup$

You can reduce from the vertex cover problem. If the complement graph of the given graph has a vertex cover less than n/2 nodes then this graph will have a clique of more than n/2 nodes that is it will be a half clique. Just state that it is difficult to solve the Vertex Cover problem so is this.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ Since you can reduce from any NP-complete problem, this is not terribly useful. Details about the reduction are expected. $\endgroup$
    – Raphael ♦
    Apr 30, 2017 at 11:15
  • 1
    $\begingroup$ This is only a reduction from the special case of finding a vertex cover of size at most $n/2$, not the general vertex cover problem. Although this special case is still NP-hard, you still have to prove this, most likely via a reduction from the general vertex cover problem. This is almost the same question as the original one, only now for vertex cover instead of clique, but the method is very similar. $\endgroup$
    – Discrete lizard ♦
    Apr 30, 2017 at 11:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.