I need some guidance in an assignment I'm doing.
I'm at complete loss, he says the the MAXIMUM INDEPENDENT SET problem is NP-hard and then asks me to prove that there is no polynomial time for the same algorithm and it also guarantees that some inequality holds, which I also don't understand, since $A(G)$ returns the size of a maximal independent set in $G$ and $OBT(G)$ returns the size of an independent set of maximal size for $G$ but isn't the case that a graph could have multiple maximal independent sets? Let's assume that it returns the largest one which reduces the epression to $0 \le K$ which should always holds since $K$ is a natural number?
As for the hint given, I don't see how we can use $H$ if I understand it correctly, it says split $G$ into disjoint sets. Also it says for every instance $G$ which is confusing me.
When I asked the professor she was very reluctant to help me, so please any guidance is appreciated.
The full question: .