Given a set of students $H$ of size $n$, and a set $E subseteq H times H $ of pairs of students that dislike each other, we want to determine whether it’s possible to divide them into $4$ groups such that:

- no two students that dislike each other end up in the same group,
- the size of each group must be at least $frac{n}{5}$.

I want to prove that this problem is NP-complete. I suspect that I could use the NP-completeness of the independence set problem, yet I have some problems with finding an appropriate reduction.

Let $G = (H, E)$ an undirected graph – each edge represents two students that dislike each other.

For the groups to be of the required size, their size must be $k in left (frac{n}{5}, frac{2n}{5} right ) cap mathbb{N}$. I could then try checking whether there is an independence set of size $k$ (which would mean there are $k$ students that potentially like each other), remove its vertices, and repeat for the next $k$. However, I don’t think this would result in a polynomial number of size combinations.

Do you have any advice on constructing this reduction?