1
$\begingroup$

I was thinking about the max-clique problem and the k-independent set problem. You can show that k-independent set is reducible to max-clique easily and you can show that max-clique is reducible to k-independent set (with a simple for loop). And k-independent set is NPC, so wouldn't that mean max-clique is also NPC, but it's not because we can't create a verifier, so I'm terribly confused. What wrong assumption am I making?

$\endgroup$
  • 1
    $\begingroup$ The decision version of max-clique is actually k-clique, which is NP-complete. $\endgroup$ – Albert Hendriks May 31 '18 at 5:50
  • $\begingroup$ @AlbertHendriks So max-clique typically asks for a set of vertices, not a yes or no answer? $\endgroup$ – notorious May 31 '18 at 5:52
  • $\begingroup$ Yes, or the size of the clique, as the current answer indicates. Perhaps there's another decision version that says "Does the max clique contain a specific vertex X?" but then it's not reducible to k-independent set. $\endgroup$ – Albert Hendriks May 31 '18 at 5:55
  • $\begingroup$ @notorious The answer I gave before was downright incorrect; it's been corrected now. Sorry about that! $\endgroup$ – Draconis May 31 '18 at 19:07
1
$\begingroup$

First, note that there are two problems frequently called the "Maximum Clique Problem".

One of them is the Clique Decision Problem: given an undirected graph $G$ and a number $k$, does $G$ contain a clique with at least $k$ vertices? This is one of Karp's 21 Problems, the original list that made NP-completeness famous. The proof involved reducing to it from the Boolean Satisfiability Problem, the very first original NP-complete problem. And a verifier for this is easy to make: check whether the set given as a solution actually does contain $k$ or more vertices, and is actually a clique.

The other is the Maximum Clique Size Problem: given an undirected graph $G$, what is the size of the largest clique in $G$? This can be shown to be NP-hard by reduction from the Clique Decision Problem, by simply comparing the size of the largest clique with $k$. And as you mentioned, it can apparently be shown to be in NP by reduction to the Clique Decision Problem: for every integer from the number of vertices down to 1, check if there's a clique of that size, and if so return that number.

So it would seem that both versions of the problem are NP-complete. But be careful about the definition of NP. NP is defined as a class of decision problems, and the Maximum Clique Size Problem is not a decision problem.

Specifically, NP is the class of decision problems where, if the answer is yes, you can be given extra information of polynomial size that lets you verify that the answer is yes in polynomial time. (If the answer is no, you can't necessarily verify it, unless NP = co-NP.) So for problems which aren't answered with yes or no, trying to put them in NP just doesn't make sense.

So while the Maximum Clique Size Problem is indeed NP-hard, and can be reduced to an NP-complete problem in polynomial time, it is not in fact in NP. And thus it cannot be NP-complete. This is why you can't make a verifier for it (unless NP = co-NP, which is an open question).

$\endgroup$

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.