0
$\begingroup$

The CLIQUE problem -- problem of finding the maximum clique in a graph -- is NP-complete. That is, CLIQUE is

  1. in NP and
  2. there is an NP complete problem, 3-SAT for one, that reduces to CLIQUE in polynomial time.

Part 2. above is fine -- all over in every resource and very well explained. For Part 1., from what I know, we need to have the following: Given a specific solution instance, we need to show that it can be verified, in polynomial time, that that solution is an answer to this problem. So for instance, given a specific graph and a subgraph of it, we should be able to check whether that subgraph is a clique of maximum size in that graph.

The resources I've read so far are phrasing this Part 1. here as "easy, straightforward, etc" or "it can be shown in $O(n^2)$ time that the given subgraph is a clique/not". However, the verification here is not just whether it's a clique, but also is whether it is a maximum clique in the graph. How can this be decided in polynomial time?

What am I missing here?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

What you're missing is the difference between decision problems and optimization problems. "Finding the maximum clique" is an optimization problem. The corresponding decision problem is "Does there exist a clique of size $\ge k$?". The latter problem is in NP. NP is a class of decision problems, so it doesn't make sense to ask whether an optimization problem is in NP; that's only meaningful for decision problems. Any textbook or standard resource on NP should explain the difference between decision problems vs. optimization problems in more depth.

Improve this answer
$\endgroup$
4
  • $\begingroup$ "Does there exist a clique of size ≥k?" is also the decision problem of the following problem (call it CLIQUE-Z) "Is there a clique of size k or greater in the graph". So you`re saying, the decision problem of CLIQUE is the same as that of CLIQUE-Z above. in that case, how would i know what the "right" decision is to show my problem is NP? $\endgroup$
    – Roam
    Commented Oct 3, 2013 at 0:30
  • $\begingroup$ "Is there a clique of size k or greater in the graph" is telling me the specific solution instance CAN BE a solution but not whether/not it is. Do i have the optimal solution (a maximum clique in the graph) at hand while i'm verifying that solution instance, is that how? $\endgroup$
    – Roam
    Commented Oct 3, 2013 at 0:32
  • $\begingroup$ @Roam, I'll repeat the advice in my question: read a textbook or standard resource on NP. Any good textbook should have a discussion of decision problems, optimization problems, and their relationship. Go do your homework. Then if you still don't understand, you can come back and ask another question -- but if you want to understand this topic, you're going to need to put in some effort on your own. $\endgroup$
    – D.W. ♦
    Commented Oct 3, 2013 at 5:08
  • $\begingroup$ @Roam You comment is barely legible, but it seems as if your were trying to be rude; please be nice instead! D.W. is quite right -- you don't seem to have basic definitions straight. Please check out our reference question; in particular, the posts linked in the comments may be of interest to you. $\endgroup$
    – Raphael
    Commented Oct 6, 2013 at 15:03

Your Answer

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

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