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.
