0
$\begingroup$

It can be read on Wikipedia that MIS is NP-hard. However, is it also NP-complete?

This article says:

"Thus, the Maximum Clique Problem(MCP) and the Maximum Independent Set(MIS) Problem are equivalent. In addition, both problems are NP—complete".

However, a professor told me that MIS cannot be NP-complete because only decision problems can be NP-complete. According to him, MIS is an optimization problem, and therefore it is not in NP.

$\endgroup$
2