# Dividing students into 4 groups based on preferences is NP-complete

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?