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?
