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?

  • 1
    $\begingroup$ You need to describe a polynomial-time method for converting any given instance of Independent Set into an instance of the Students problem. It's no good solving the IS instance and then using that to construct the Students instance, since no one knows how to solve IS in polynomial time! ;) Hint: Think about transformations that you can make to an arbitrary input graph, and how that would affect the size of the largest IS in it. E.g., what happens if you make several copies of the input graph? $\endgroup$ Jun 3, 2020 at 2:50
  • $\begingroup$ Another kind of transformation would be to replace each vertex in the graph with some multi-vertex subgraph, and transform edges in some corresponding way. $\endgroup$ Jun 3, 2020 at 2:59


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.