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?